Докажите, что любой направленный ациклический граф содержит по крайней мере одну вершину с нулевой степенью захода. Воспользуйтесь этим результатом, чтобы построить другой алгоритм, осуществляющий топологическую сортировку.

1. Доказательство существования вершины с нулевой степенью захода

Дано: Граф $G = (V, E)$, который является ациклическим (DAG). Найти: Доказать, что существует вершина $v \in V$, такая что входящая степень $d_{in}(v) = 0$.

Доказательство:

1. Предположим обратное: пусть в графе $G$ нет вершин с нулевой степенью захода. Это означает, что для каждой вершины $v \in V$ выполняется условие $d_{in}(v) \geq 1$.
2. Рассмотрим произвольный путь в графе, который начинается в некоторой вершине $v_1$. Так как $d_{in}(v_1) \geq 1$, мы можем найти вершину $v_0$, из которой идет ребро в $v_1$. Продолжая этот процесс «назад», мы будем получать последовательность вершин $\dots, v_{-2}, v_{-1}, v_0, v_1$...