Партнерка на США и Канаду по недвижимости, выплаты в крипто
- 30% recurring commission
- Выплаты в USDT
- Вывод каждую неделю
- Комиссия до 5 лет за каждого referral
3. 
только дуга 
. Если по этой дуге мы впервые приходим в 
, то будет древесной дугой, а 
корнем дерева . В противном случае ССК уже выделена (ее вершины вытолкнуты из стека) и поперечную дугу вообще не нужно обрабатывать.
Пути, состоящие из древесных дуг, ведут от предков к потомкам в дереве.
Прямые дуги просто дублируют участки путей на дереве, поэтому их можно вообще не рассматривать.
Пути от потомков к предкам в дереве определяют обратные и, потенциально, поперечные дуги.
Пусть поперечная дуга 
, где 
– потомок 
или 
. Если обратная дуга 
, где 
– потомок или 
, а 
– предок , то вершины 
принадлежат одной ССК.
 |
Для каждой вершины нужно найти ее предка , достижимого из по путям, содержащим обратные и поперечные дуги, и имеющего минимальный номер 
– это корень ССК, содержащей .
Введем функцию «нижняя связь»
: поперечная или обратная дуга из или некоторого потомка в вершину , причем корень ССК, к-рая содержит , является предком .
Лемма:
явл-ся корнем ССК 
.
В приведенной ниже программе используется стек для выделения вершин ССК.
Значения 
вычисляются рекурсивно в массиве LCon.
Для того, чтобы не учитывать поперечные дуги, соединяющие разные ССК, исп-ся массив InS: InS[v] = 1, если v – в стеке.
Подготовка массивов, выделение корней глубинных остовных деревьев, вызов рекурсивной функции поиска в глубину:
sccomp = 0; newnum = 0;
for (k = 1; k <= n; k++) {
Old[k] = 0; InS[k] = 0;
}
for (k = 1; k <= n; k++)
if (Old[k] == 0) search_SCC(k);
Поиск в глубину с выделением ССК:
void search_SCC(int v) { Old[v]=1;
LCon[v]=NV[v]=++newnum; push(v); InS[v]=1;
for (w 
L[v])
if (Old[w] == 0) { // (v, w) - древесная
search_SCC(w);LCon[v]=min(LCon[v],LCon[w]);
}
else if (NV[w]<NV[v] && InS[w]==1) // О\П
LCon[v] = min(LCon[v], NV[w]);
if (LCon[v] == NV[v]) { sccomp++;//v–корень ССК
do x = pop(); InS[x] = 0;
сохранить_вершину(x, sccomp);
while (x!= v);
}
}
Трудоемкость данного алгоритма составляет 
.
Следующий рисунок иллюстрирует результаты работы алгоритма поиска в глубину с расчетом новых номеров NV и значений LCon (красные цифры).
При вычислении значений LCon не учитывались поперечные дуги, ведущие в вершины уже выделенных ССК (удаленные из стека).
2-й алгоритм выделения ССК (Кормен)
Данный алгоритм использует поиск в глубину дважды.
При 1-м поиске для каждой вершины вычисляется ее новый номер, но не в порядке прихода в нее (
), а в порядке завершения поиска (завершения проверки всех дуг, исходящих из данной вершины) – 
.
После этого исходный граф 
«транспонируется», т. е. в нем изменяется направление всех дуг. В результате получается граф 
: 
.
Далее проводится поиск в глубину на 
, причем вершины выбираются в порядке убывания значений , вычисленных при 1-м поиске. Полученные на данном шаге глубинные остовные деревья соответствуют сильно связным компонентам исходного графа 
.
Поиск в глубину с вычислением значений LV:
lastnum = 0; // тек. значение номера
for (k = 1; k <= n; k++) Old[k] = 0;
for (k = 1; k <= n; k++)
if (Old[k] == 0) search(k);
void search(int v) {
Old[v] = 1;
for (w L[v])
if (Old[w] == 0) search(w);
LV[v] = ++lastnum;
}
Иллюстрация работы предыдущего алгоритма (древесные дуги синие, для вершин указаны значения ):
 |
Исходный порядок выбора вершин: 
.
Порядок первого прихода в вершину: 
.
Пусть 
– произвольная пара вершин . Очевидно, что достижима из на графе , тогда и только тогда, когда достижима из на . Поэтому графы и содержат одни и те же сильно связные компоненты (точнее, мн-ва вершин, образующих ССК).
При поиске в глубину все вершины одной ССК образуют одно дерево, т. е. имеют одного общего предка (основная лемма).
Дерево любой ССК является поддеревом некоторого глубинного дерева, и каждая вершина графа принадлежит какой-либо ССК. Поэтому корни глубинных деревьев являются также корнями ССК.
Выберем вершину с максимальным значением
: 
.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 |
Основные порталы (построено редакторами)