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

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


(докажите это), и любое ребро листа принадлежит циклу. Очевидно
также сходство теоремы 1 и теоремы 1 из §4 гл.1.
                                    µ            ¶
                                      1 2 3 4 5
    Пример 1. Орграф отображения                   выглядит так:
                                      2 5 2 5 1




                                Рис. 1

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




                                Рис. 2

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

     Пример 3.




                                Рис. 4


    При подходящей нумерации вершин матрица смежности отража-
ет строение графа. Это верно и в неориентированном случае (см.