Дискретная математика: графы и автоматы. Альпин Ю.А - 27 стр.

§ 1. Взаимодостижимость, компоненты и конденсация                     27


упр. 1 §1 гл. 1), но для орграфов нумерация имеет большее значе-
ние. Пример такой нумерации содержит следующее
    Предложение 1. Пусть орграф не содержит контуров. Тогда
существует нумерация вершин, при которой дуга ведёт из вершины
i в вершину j, только если i > j, то есть, матрица смежности —
нижняя нильтреугольная.
    Д о к а з а т е л ь с т в о. В орграфе без контуров существует
минимальная вершина, то есть вершина, из которой не выходят ду-
ги (подумайте, почему?). Присвоим минимальной вершине u номер 1.
Рассмотрим множество вершин V \{u}. Оно содержит вершину v, из
которой не выходят дуги в другие вершины этого множества. При-
своим этой вершине номер 2. Затем по тому же принципу выделим
в множестве V \{u, v} вершину w и так далее. В итоге получим ну-
мерацию u 7→ 1, v 7→ 2, . . . , z 7→ n, которая, как нетрудно убедиться,
обладает нужным свойством. ¤
    Поскольку на компоненты орграфа мы можем смотреть как на
вершины конденсации, то из теоремы 1 и предложения 1 вытекает
    Теорема 2. Существует такая нумерация компонент
                             V1 , V2 , . . . , V s ,                 (1)
что если начало дуги орграфа лежит в Vi , а конец — в Vj , то i > j.
    Компонента графа называется минимальной, если из неё не вы-
ходят дуги в другие компоненты. В списке (1) компонента V1 — за-
ведомо минимальная, но необязательно единственная минимальная
компонента.
    Задача 2. Назовём множество вершин орграфа замкнутым, ес-
ли из него не выходят дуги в вершины, не принадлежащие этому мно-
жеству. Докажите, что непустое множество вершин орграфа образует
минимальную компоненту тогда и только тогда, когда оно замкнуто
и не содержит собственных замкнутых подмножеств.
    Нумерацию компонент, описанную в теореме 2, назовём нормаль-
ной, если, дополнительно, минимальные компоненты перечислены в
ней в первую очередь. Нумерацию вершин графа будем считать нор-
мальной, если она согласована с некоторой нормальной нумерацией
(1) компонент в том смысле, что при этой нумерации первые номе-
ра получают вершины из V1 , затем нумеруются вершины из V2 и так
далее.
    Вершина графа называется невозвратной, если из неё есть путь
в такую вершину, из которой она недостижима. Докажите самостоя-
тельно