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

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


     На орграфы естественным образом переносятся такие понятия,
как подграф, в частности, подграф, порождённый множеством вер-
шин, изоморфизм графов, факторграф. Например, факторграф гра-
фа G по разбиению множества вершин определяется так: его вершины
— это классы разбиения, причём из класса S в класс T ведёт дуга,
если S 6= T и в исходном графе существует дуга с началом в S и
концом в T .
     Очевидным образом распространяется на орграфы понятие мат-
рицы смежности и булевой матрицы смежности. После соответству-
ющей замены терминов остаются верными предложения 1, 2 и 3 из
§1 гл.1 и их доказательства. Советуем читателю убедиться в этом.
Разумеется, матрица смежности орграфа уже не обязана быть сим-
метричной и иметь нулевую диагональ, а может быть какой-угодно
(0, 1)-матрицей.
     Говорят, что вершина v достижима из вершины u, если u = v
или существует (u, v)-путь. Достижимые друг из друга вершины u и
v называются взаимодостижимыми. Если любые две вершины ор-
графа взаимодостижимы, то он называется сильно связным. В про-
тивном случае граф называется приводимым. Взаимодостижимость
— рефлексивное, симметричное и транзитивное бинарное отношение,
то есть, отношение эквивалентности. Оно разбивает множество вер-
шин графа на классы взаимодостижимых вершин. Класс взаимодо-
стижимости, как и сильно связный подграф, им порождённый, будем
называть компонентой орграфа.
    Задача 1. Сформулируйте для орграфов утверждения задачи 2
§1 гл. 1 и убедитесь, что они остаются верными.
    Конденсацией орграфа называется его факторграф по разбиению
на компоненты.
   Теорема 1. Конденсация не содержит контуров.
   Д о к а з а т е л ь с т в о. Если предположить существование
контура
                     S → T → . . . → U → S,
то, очевидно, вершины различных компонент, входящих в этот кон-
тур, взаимодостижимы и, следовательно, лежат в одной компоненте.
Противоречие. ¤
   Замечание 1. Аналогом сильно связного орграфа является в
неориентированном случае скорее лист, а не связный граф. Действи-
тельно, любая дуга сильно связного орграфа принадлежит контуру