8 группа/

             Ориентированные графы
   Во многих теоретических и прикладных задачах полезно исполь-

зовать графы, рёбра которых имеют направление. В связи с этим введём новый тип графов.

   Ориентированным графом (орграфом) называется пара (V, E),

где V непустое множество вершин, E ⊆ V Ч V множество ориен- тированных рёбер или дуг. Таким образом, дуга это упорядоченная пара вершин. Если e = (u, v), то вершина u начало дуги e, вершина v её конец. Говорят, что дуга e выходит из u и входит в v. Гово- рят также, что e инцидентна вершинам u и v. Дуга (v, v) называется петлёй. На рисунке дуги графа изображаются стрелками. Иногда в тексте вместо выражения “дуга ведёт из вершины i в вершину j ” бу- дем писать i → j. Вершины орграфа смежны, если они соединены дугой.

   Путём длины k в орграфе называют любую последовательность

вершин

                          v1 , v2 , . . . , vk+1 ,

такую, что (vi , vi+1 ) дуга, i = 1, . . . , k. Говорят, что v1 начало, vk+1 конец пути. Когда хотят указать начало и конец пути, пишут: (v1 , vk+1 )-путь.

     Простой путь это путь, в котором все вершины различны, кро-

ме, возможно, первой и последней. Если v1 = vk+1 , то путь (простой путь) называется контуром (простым контуром).

     Приведём леммы, аналогичные леммам 1 и 2 из §1 гл.1. Их доказа-

тельства в ориентированном случае даже упрощаются. Рекомендуем доказать их самостоятельно.

  Лемма 1. Если существует (u, v)-путь, то существует и про-

стой (u, v)-путь.

  Лемма 2. Всякий контур содержит простой контур, причём

каждая вершина и дуга контура принадлежат некоторому просто- му контуру. На орграфы естественным образом переносятся такие понятия, как подграф, в частности, подграф, порождённый множеством вер- шин, изоморфизм графов, факторграф. Например, факторграф гра- фа G по разбиению множества вершин определяется так: его вершины

  это классы разбиения, причём из класса S в класс T ведёт дуга,

если S = 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. Аналогом сильно связного орграфа является в

неориентированном случае скорее лист, а не связный граф. Действи- тельно, любая дуга сильно связного орграфа принадлежит контуру


26 Глава 2. Ориентированные графы


(докажите это), и любое ребро листа принадлежит циклу. Очевидно также сходство теоремы 1 и теоремы 1 из §4 гл.1.

                                        1 2 3 4 5
    Пример 1. Орграф отображения                        выглядит так:
                                        2 5 2 5 1



                               Рис. 1

На этом примере виден и общий принцип построения графа отобра- жения множества в себя. Для нашего примера компоненты и конден- сация таковы:



                               Рис. 2
   Если отображение биекция (перестановка), то граф распадает-

ся на простые контуры, его конденсация пустой граф.

    Пример 2.
             На рис. 3 изображён пример турнира. Так называют-
             ся орграфы, в которых любые две вершины соединены
             единственной дугой. В данном случае турнир не содер-
             жит контуров, и его конденсация совпадает с ним самим.
    Рис. 3
    Пример 3.



                               Рис. 4


   При подходящей нумерации вершин матрица смежности отража-

ет строение графа. Это верно и в неориентированном случае (см.


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


упр. 1 §1 гл. 1), но для орграфов нумерация имеет большее значе- ние. Пример такой нумерации содержит следующее

   Предложение 1. Пусть орграф не содержит контуров. Тогда

существует нумерация вершин, при которой дуга ведёт из вершины i в вершину j, только если i > j, то есть, матрица смежности нижняя нильтреугольная.

   Д о к а з а т е л ь с т в о. В орграфе без контуров существует

минимальная вершина, то есть вершина, из которой не выходят ду- ги (подумайте, почему?). Присвоим минимальной вершине u номер 1. Рассмотрим множество вершин V \{u}. Оно содержит вершину v, из которой не выходят дуги в другие вершины этого множества. При- своим этой вершине номер 2. Затем по тому же принципу выделим в множестве V \{u, v} вершину w и так далее. В итоге получим ну- мерацию u → 1, v → 2, . . . , z → n, которая, как нетрудно убедиться, обладает нужным свойством.

   Поскольку на компоненты орграфа мы можем смотреть как на

вершины конденсации, то из теоремы 1 и предложения 1 вытекает

   Теорема 2. Существует такая нумерация компонент
                            V1 , V2 , . . . , V s ,              (1)

что если начало дуги орграфа лежит в Vi , а конец в Vj , то i > j.

   Компонента графа называется минимальной, если из неё не вы-

ходят дуги в другие компоненты. В списке (1) компонента V1 за- ведомо минимальная, но необязательно единственная минимальная компонента.

   Задача 2. Назовём множество вершин орграфа замкнутым, ес-

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

   Нумерацию компонент, описанную в теореме 2, назовём нормаль-

ной, если, дополнительно, минимальные компоненты перечислены в ней в первую очередь. Нумерацию вершин графа будем считать нор- мальной, если она согласована с некоторой нормальной нумерацией (1) компонент в том смысле, что при этой нумерации первые номе- ра получают вершины из V1 , затем нумеруются вершины из V2 и так далее.

   Вершина графа называется невозвратной, если из неё есть путь

в такую вершину, из которой она недостижима. Докажите самостоя- тельно


28 Глава 2. Ориентированные графы


  Предложение 2. Невозвратные вершины      это в точно-

сти те вершины, которые принадлежат неминимальным компо- нентам.

  Назовём простой путь максимальным, если он не имеет простого

продолжения. Докажите самостоятельно

  Предложение 3. Конец простого максимального пути всегда

принадлежит минимальной компоненте.

        § 2. Нормальная форма матрицы смежности
                    приводимого графа
  Квадратную матрицу A (булеву матрицу или матрицу над полем)

называют приводимой, если она перестановочно подобна матрице ви- да

                            B 0
                                    ,                       (1)
                            C D

где B, D квадратные матрицы. В противном случае говорят, что A

 неприводимая матрица. Приводимая матрица A имеет нормальную

форму, если она блочно-треугольная:

                                                  
                   A1
                        ...                       
                                                  
                               Al                 
           A=   Al+1,1 . . . Al+1,l Al+1
                                                   
                                                          (2)
                 .              .     .           
                 . .            .
                                 .     .
                                       .   ...     
                   As,1 . . . As,l As,l+1 . . . As

причём A1 , A2 , . . . , As (1 ≤ l ≤ s) неприводимые матрицы, а в каждой строке, начиная с (l + 1)-го (при l < s), имеются ненулевые блоки, расположенные левее диагонали.

   Предложение 1. Орграф сильно связен тогда и только то-

гда, когда его матрица смежности неприводима. Если граф приво- дим, то существует нумерация вершин, при которой его матрица смежности имеет нормальную форму.

   Д о к а з а т е л ь с т в о. Допустим, что орграф сильно связен,

но его матрица смежности приводима. Это значит, что при некото- рой нумерации вершин графу соответствует матрица смежности вида (1). Но тогда выходит, что из вершин с номерами 1, . . . , k нельзя пе- рейти в вершины с номерами k + 1, . . . , n (где k порядок B), противоречие с сильной связностью.