@udov

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

0

@Mysterious Light

Достаточно легко:

Допустим, ацикличный граф имеет N вершин. Выбираем любую, имя ей A1.
Если она не имеет ни одного исходящего инцидетного ребра, суждение справедливо.
Если имеет хотя бы одно, то выберем произвольное и последуем вдоль, попадём в вершину A2.
Если A2 не имеет ни одного исходящего ребра, то суждение истинно. Иначе повторяем процедуру и переходим к A3.
Продолжаем построение, но не далее, чем на N шагов.
Возможны N ситуаций: либо мы остановились на A1, либо на A2, либо на A3 и т.д., либо всё-таки дошли до AN.
Прошу обратить внимание, что в любом из первых (N-1) случаев суждение истинно.
В последнем случае последовательность A1,A2,...,AN не имеет повторений в силу ацикличности, а потому множество {A1,A2,...,AN} содержит все вершины графа. Граф ацикличен, а поэтому AN не может иметь исходящего ребра. В этом случае суждение также оказывается истинным.
Вывод: в каждом из N случаев суждение выполняется. Полная индукция нам даёт истинность исходного суждения.

Прошу обратить внимание, что в этом доказательстве использовалась полная (конечная) индукция и рекурсия конечной заведомо известной глубины. Здесь не использовался приём доказательства от противного или что-то другое столь же неочевидно... мне редко попадаются задачи, которые можно было б решить так.

2

Байт

0