Я вижу гипотезу истинно интуитивно, но математически я не могу доказать. Любая помощь будет оценена по достоинству.Как мы можем доказать, что в Направленном ациклическом графе будет хотя бы вершина с нулевой степенью нуля?
Пусть этот граф имеет n вершин.
Предположим, что мы реверсируем все ребра, тогда мы пытаемся доказать, что существует вершина с нулевой степенью.
Если нет, то просто начинайте в любом месте и перемещайтесь по n ребрам (всегда возможно, как и каждая вершина как ненулевая вне градуса). Поэтому мы посетили n + 1 вершины - поэтому по крайней мере 2 из них должны быть одинаковыми (принцип дыркой), и поэтому мы нашли цикл в вашем ациклическом графе.