Методы работы с разреженными матрицами произвольного вида. Глушакова Т.Н - 26 стр.

                                         26
(или же оно заходит в C), если v⌠ Vc, а ω0Vc. Так как сильная компонента –
это частичный граф, то входы и выходы не принадлежат никакой сильной
компоненте.
    Если G допускает разбиение, то должна существовать хотя бы одна
сильная компонента, не имеющая выходов. Действительно, если бы каждая
компонента имела выход, то мы смогли бы проследить путь от одной
компоненты к другой, затем к третьей и т.д., пока, наконец, не достигли бы
одной из компонент, где уже были прежде. Цикл, полученный таким
образом, противоречит определению сильных компонент. В общем случае
может существовать несколько компонент без выходов. Будем говорить, что
все сильные компоненты без выходов принадлежат уровню 1.
    Продолжая рассуждать подобным образом, мы можем заключить, что
среди оставшихся сильных компонент G должна существовать хотя бы одна
такая, что каждое исходящие из нее ребро заходит в некоторую компоненту
уровня 1. Вообще говоря, таких компонент может быть несколько, и мы
будем говорить, что все они принадлежат уровню 2. Среди компонент G, не
входящих ни в уровень 1, ни в уровень 2, должна быть хотя бы одна, из
которой все выходы ведут в уровни 1 и 2. По крайней мере, один из этих
выходов должен заходить в уровень 2, иначе компонента принадлежала бы
уровню 2, а по нашему предположению, это не так. Названная компонента и,
если найдутся, все другие с теми же свойствами образуют уровень 3.
Заметим, что у компонент уровня 3 могут отсутствовать выходы, ведущие в
уровень 1. Если продолжить описанную процедуру, то будет получена
структура уровней связности, где:
                         L1 = {Ci | Ci не имеет выходов },
 Ll = {Ci | если (u → v) – выход из Ci и v0Cj, то Cj0Ll', где l' < l}, l = 2, 3, …, m.
    Определение подразумевает, что любая сильная компонента уровня l > 1
должна иметь, по меньшей мере, один выход, ведущий в уровень l – 1. Число
m называется длиной разбиения. Структура уровней связности орграфа
единственна. Будем говорить, что вершина v графа G находится в уровне l
или что Уровень (v)=l, если v принадлежит сильной компоненте уровня l.
Если (v → ω) – ребро орграфа, то Уровень (v) = Уровень (ω) тогда и только
тогда, когда v и ω принадлежат одной и той же сильной компоненте, в
противном случае, Уровень (ω) < Уровень (v). Сильная компонента уровня l
может быть достигнута только ребрами, исходящими из уровней l + 1, …, m,
однако может случиться, что сильная компонента не имеет входов, даже если
ее уровень l < m.
    Другую структуру уровней связности можно определить, помещая в
уровень 1 все компоненты, не имеющие входов, и продолжая
вышеописанный процесс с заменой слова «выход» на слово «вход». Говорят,
что две структуры уровней являются двойственными.
    Орграф называется ациклическим, если он не имеет циклов: если путь
начинается в произвольной вершине v, он никогда в v не вернется. Это
значит, что каждая вершина ациклического орграфа представляет собой
сильную компоненту. Поэтому число сильных компонент ациклического