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

                                     29
потомок v, то Номер(v)<Номер(ω). Кроме того, все вершины Tv будут
посещены до возвращения через v. В частности, если v – корень сильной
компоненты, то номер v меньше номера любой другой вершины этой
компоненты, и все вершины последней будут посещены, прежде чем
покинуть ее возвращением через v.
    Рассмотрим теперь некоторый шаг поиска. Пусть v – текущая вершина, (v
→ ω) – ребро, не являющееся древесным. Это означает, что ω посещалась до
того, как v стала текущей вершиной. Следовательно, в этот момент
определены и Номер(v), и Номер(ω). Кроме того, если v относится к
некоторому уровню l, то, уровень l' вершины ω должен удовлетворять
условию l' ≤ l, знак равенства достигается только, если v и ω принадлежат
одной и той же сильной компоненте. Если обнаружено недревесное ребро (v
→ ω), то существуют следующие возможности:
    (1) ω – предок для v. В этом случае Номер(ω) < Номер(v), а ребро (v → ω)
называется обратным. Поскольку уже существует путь из ω в v,
образованный древесными ребрами, то роль обратного ребра состоит в
замыкании цикла. Таким образом, v и ее предки вплоть до (и включая) ω
принадлежат одной и той же сильной компоненте.
    (2) ω – потомок v. В этом случае Номер(ω) > Номер(v), а ребро (v → ω)
называется лишним древесным ребром. Лишнее древесное ребро соединяет
две вершины, уже связанные путем из древесных ребер. Следовательно, оно
не помогает поиску сильных компонент, и если наша цель состоит именно в
этом, им можно пренебречь.
    (3) ω – ни потомок, ни предок для v. Ребро (v → ω) называется
поперечным. Рассмотрим поддерево Tv с корнем v, содержащее все потомство
v. В ходе поиска, после прихода в v, посещаются и нумеруются все вершины
Tv и только они, пока Tv не будет покинуто возвращением через v. Вершина ω
не принадлежит Tv, но номер ей был присвоен раньше, чем v стала текущей
вершиной. Это значит, что ω получила номер еще до того, как мы впервые
вошли в v, следовательно, Номер(ω)<Номер(v). Вершины v и ω могут
принадлежать одной или разным сильным компонентам. В первом случае
Уровень(ω) = Уровень(v), во втором – Уровень(ω) < Уровень(v).
    Структура, составленная из остовного леса и добавочных ребер, которые
могут быть обратными, лишними древесными и поперечными, называется
джунглями.
Если поиск в глубину проводится на ациклическом орграфе, где каждая
вершина является сильной компонентой, то получится более простая
структура. Каждая вершина остовного леса – корень своей собственной
сильной компоненты. Нет ни обратных, ни активных поперечных ребер
(активным называется поперечное ребро, концы которого принадлежат
одной и той же сильной компоненте). Все ребра будут либо древесными,
либо стерильными поперечными (стерильным называется поперечное ребро,
концы которого принадлежат разным сильным компонентам).