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

                                   27
орграфа равно числу его вершин, хотя бы одна из вершин имеет
нулевую полустепень исхода и, по крайней мере, у одной вершины
полустепень захода равна нулю.
   Разбиение произвольного орграфа на сильные компоненты удобно
изображать посредством соответствующего факторграфа или конденсации,
вершинами которого являются сильные компоненты. Конденсация орграфа –
это ациклический орграф, который, как и всякий ациклический орграф, имеет
хотя бы одну вершину с нулевой полустепенью исхода, т.е. хотя бы одну
сильную компоненту без выходов.
   Пусть теперь G – орграф, ассоциированный с несимметричной матрицей
A. Разобьем G на сильные компоненты и построим структуру уровней, как
описано выше. Пусть вершины G упорядочены, и упорядочение совместимо
с разбиением на компоненты и монотонно относительно уровней, т.е. все
вершины каждой компоненты нумеруются последовательными числами и все
компоненты каждого уровня l, l = 1, 2, …, m – 1, нумеруются раньше любой
компоненты уровня l' > l. Тогда соответствующая симметрично
переупорядоченная матрица будет блочной нижней треугольной. Каждой
сильной компоненте с ni вершинами отвечает квадратный диагональный блок
порядка ni, внедиагональные блоки соответствуют связям между сильными
компонентами.

      3.2 Исследование стратегий для несимметричных
      разреженных матриц
      3.2.1 Поиск в глубину на орграфе
     Поиск в глубину – это процедура обхода вершин и ребер графа:
начинают с произвольной вершины s1 и пытаются по возможности
придерживаться последовательности вершина – ребро – вершина – ребро …,
если в текущей вершине больше нет неисследованных ребер, то
возвращаются к предыдущей вершине. Рассмотрим структуры, получаемые
при выполнении поиска в глубину на орграфе, где фиксировано направление,
в котором можно исследовать каждое ребро. Предположим, что всякая
вершина содержит петлю. Пусть v – текущая вершина. Мы вошли в v либо
впервые (и тогда v – последняя посещенная вершина), либо повторно при
возвращении. Пусть исследуется ребро (v → ω), причем ω не посещалась
прежде. Тогда ω становится текущей вершиной, а ребро (v → ω)
квалифицируется как древесное. Если сохранять только древесные ребра и
пренебрегать всеми остальными, то будет получено дерево с корнем в
начальной вершине s1. Поскольку ребра ориентированы, то продолжение
поиска может оказаться невозможным еще до того, как посещены все
вершины. Так заведомо произойдет, если, например, s1 принадлежит сильной
компоненте C, не имеющей выхода: и исследование ребер, и возвращение
будут всегда приводить к вершинам из C, и дерево с корнем s1 будет точным
остовом C.