Связность и связные подграфы (клики)

(a) Предположим, что вершина принадлежит двум различным сильно связным графам и Тогда для любых и существуют пути и Следовательно, и достижимы друг из друга, что означает — сильно связный. Таким образом, если вершина лежит в нескольких разных компонентах сильной связности, то получаем противоречие с максимальностью.

(b) Докажем утверждение индукцией по числу вершин

База индукции: Для утверждение очевидно — вершине присваивается номер

Индукционный переход: Предположим, что для любого ацикличного графа с вершинами утверждение верно. Рассмотрим граф с вершиной.

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

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

Таким образом, нумерация корректна для вершин.

(c) Рассмотрим граф компонент сильной связности (КСС), вершины это КСС, ребра это наличие ребра между КСС в исходном графе. Этот граф ацикличен, ведь иначе мы смогли бы увеличить КСС. Применим к нему пункт (b), присвоив КСС номера Все рёбра между КСС направлены от меньшего номера к большему, а внутри КСС сохраняются.