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

                                     28
    В более общем случае при произвольном выборе s1 будет
получено дерево с корнем s1, остовное лишь для некоторых сильных
компонент графа. Тогда поиск возобновляется из новой начальной вершины
s2, которая пока что не посещалась и, следовательно, не принадлежит
никакой из сильных компонент, натянутых на первое дерево. Снова
пренебрегая всяким недревесным ребром, построим второе дерево с корнем в
s2, остовное для новой группы сильных компонент. Процедура продолжается,
пока не будут посещены все вершины. Результатом будет семейство
несвязных деревьев, называемое остовным лесом, которое содержит все
вершины орграфа и ребра, квалифицированные как древесные. Кроме того,
при поиске нумеруются узлы в том порядке, в каком они посещаются. Будем
обозначать через Номер(v) номер, приписанный вершине v в ходе поиска. В
технологии разреженных матриц это упорядочение и соответствие между
деревьями леса и сильными компонентами используются алгоритмами,
приводящими матрицу к блочной нижней треугольной форме.
    Исследуем более детально связь между деревьями и натянутыми на них
сильными компонентами. Пусть s – начальная вершина, T – дерево с корнем
s, построенное посредством поиска в глубину. Покажем, что T можно разбить
на несвязанные поддеревья, каждое из которых служит остовом ровно одной
сильной компоненты. Пусть C = (Vc, Ec) – одна из сильных компонент,
натянутых на T, и пусть Tc – наименьшее поддерево T, содержащее все
вершины C. Пусть v0Vc – корень Tc. Легко показать, что дереву Tc
принадлежит только вершины из C. Действительно, предположим, что ω⌠ Vc
– вершина Tc. Вершина ω не является корнем Tc, не может она быть и
конечной вершиной, так как по предположению Tc – наименьшее поддерево,
содержащее все вершины C. Тогда v – предок для ω, и ω должна иметь
потомка (скажем, x) в C. В Tc имеется путь из v в x, содержащий ω, поскольку
C – сильная компонента, то в C существует путь из x в v. Оба пути образуют
цикл, которому принадлежит ω, но тогда ω должна быть вершиной C
вопреки нашему предположению.
    Таким образом, T можно разбить на несвязные поддеревья, каждое из
которых остовное ровно для одной сильной компоненты. Корень поддерева –
это первая вершина соответствующей компоненты, посещаемая в ходе
поиска. Он называется корнем сильной компоненты. В частности, начальная
вершина s является корнем той сильной компоненты, которой принадлежит.
Следовательно, задача отыскания сильных компонент орграфа сводится к
задаче отыскания корней поддеревьев. Будем говорить, что поддерево
относится к уровню l, если соответствующая компонента находится в уровне
l структуры уровней связности данного орграфа.
Исследуем соотношения между недревесными ребрами, с одной стороны, и
деревьями леса и сильными компонентами орграфа – с другой. Это будет
сделано с учетом следующих существенных свойств поиска в глубину. Пусть
Т – одно из деревьев леса, v – произвольная вершина T, Tv – поддерево с
корнем v, содержащее v и всех ее потомков в T. Тогда v – первая вершина Tv,
посещаемая при поиске, поэтому она имеет наименьший номер в Tv: если ω –