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

                                     38
опознаны как элементы C. Это означает, в частности, что если v –
текущая вершина поиска и найдено ребро (v → ω), где ω нумерована, но не
приписана какой-либо компоненте, то v и ω принадлежат одной и той же
компоненте. Доказательство несложно: пусть Уровень(ω) = l, так как ω еще
не приписана, то текущая вершина v должна находиться в уровне l' ≤ l.
Однако, поскольку (v → ω) – ребро графа G, то l' ≥ l. Следовательно, l' = l,
что возможно, лишь, если v и ω относятся к одной компоненте.
   В алгоритме Тарьяна проводится поиск, и каждой вершине v
сопоставляется метка. Последняя состоит из двух чисел, называемых
Номер(v) и Связка(v). Номер(v) определяется в ходе поиска простой
нумерацией вершин от 1 до n = |V| соответственно порядку, в каком они
посещаются. Для произвольной вершины v, не являющейся корнем сильной
компоненты, Связка(v) – это номер некоторой вершины ω из той же, что и
для v, сильной компоненты. Однако, ω нумерована раньше, чем v, т.е.
Связка(v) = Номер(ω) < Номер(v). Для корня r любой сильной компоненты
мы полагаем Связка(r) = Номер(r). Это свойство используется для опознания
корней сильных компонент: если число Связка(v) правильно вычислено, то v
тогда и только тогда будет корнем сильной компоненты, когда
Связка(v)=Номер(v). В ходе поиска вычисления, связанные с признаком
Связка, производятся на следующих шагах:
   Шаг 1 (Инициализация). Если вершина v посещается впервые, то
положить Связка(v) = Номер(v).
   Шаг 2 (Модификация). Если v – текущая вершина и найдено ребро (v →
ω), где ω нумерована раньше, чем v, но еще не приписана какой-либо
компоненте, то положить Связка(v) = min[Связка(v), Связка(ω)].
   Шаг 3 (Возвращение). Если (v → ω) – древесное ребро, причем v и ω
принадлежат одной компоненте и происходит возвращение из ω в v, то
положить Связка(v) = min[Связка(v), Связка(ω)].
   На шаге 1 признаку Связка присваивается максимальное возможное для
данной вершины значение. На шаге 2 Связка(v) переопределяется на меньшее
значение, если найдена связь v с некоторой подходящей вершиной ω.
Вследствие требования Номер(ω) < Номер(v) здесь учитываются только
обратные и поперечные ребра. Кроме того, поскольку ω нумерована, но еще
не приписана какой-либо компоненте, то v и ω должны быть в одной и той
же компоненте. Это устраняет стерильные поперечные ребра, т.е.
поперечные ребра (v → ω), у которых v и ω относятся к разным
компонентам. Далее, Связка(ω) – это номер некоторой вершины из той же
сильной компоненты, какой принадлежат v и ω. Этот номер, возможно,
меньше, чем у ω. Стратегия шага 2 состоит в том, чтобы переопределять
признак Связка(v) на наименьший из известных пока номеров вершин в
данной компоненте.
   На шаге 3 минимальное значение признака Связка спускается вдоль пути
при возвращении. Стратегия этого шага та же, что у шага 2: мы знаем, что v
связана с ω, а ω связана с x = Связка(ω), поэтому v связана с x. Если номер x
меньше, чем текущее значение числа Связка(v), то последнее