Партнерка на США и Канаду по недвижимости, выплаты в крипто
- 30% recurring commission
- Выплаты в USDT
- Вывод каждую неделю
- Комиссия до 5 лет за каждого referral
Условие обратного ребра при поиске в глубину:
, если 
и 
не является отцом 
.
Выделение компонент связности (номера компонент – в массиве P), нумерация вершин в порядке обхода (массив NV), граф задан списками смежных вершин L[1…n]:
comp = 0; newnum = 0; // NN компонент и вершин
for (k = 1; k <= n; k++) P[k] = 0;
for (k = 1; k <= n; k++)
if (P[k] == 0) //k–корень очередной компоненты
{ comp++; search(k); }
void search(int v) {
P[v] = comp; NV[v] = ++newnum;
for (j 
L[v])
if (P[j] == 0) search(j);
}
Трудоемкость: 
при исп-нии матрицы смежности,
при исп-нии списков смежных вершин.
Двусвязные компоненты
Задан связный неориентированный граф 
.
является двусвязным, если он остается связным при выбрасывании любой его вершины с инцидентными ребрами.
содержит точку сочленения 
, если для некоторой пары вершин и все пути из в проходят через .
Удаление точки сочленения (точки разрыва) разбивает граф, по крайней мере, на 2 несвязные части.
 |
На мн-ве ребер 
графа можно определить отношение эквивалентности: 
, если 
или оба ребра лежат в одном цикле.
Пусть 
– классы эквивалентности (
) и 
– соответствующие им множества вершин. Тогда 
– это двусвязные компоненты .
Лемма, определяющая двусвязные компоненты, точки сочленения и их свойства (Ахо):
1. Графы 
– двусвязные 
.
2. 
мн-во 
содержит не более одной вершины.
3. – точка сочленения 
для некоторых 
.
=> Точки сочленения разделяют двусвязные компоненты.
Лемма (Ахо). Пусть построено глубинное остовное дерево. Вершина будет точкой сочленения тогда и только тогда, когда выполняется одно из условий:
1. – корень и имеет более 1 сына (поддеревья связаны только через ).
2. – не корень и для некоторого его сына 
нет обратных ребер, соединяющих и\или ее потомков с предками .
 |
Пусть при поиске в глубину вершинам присвоена новая нумерация в порядке их обхода. Тогда, если – потомок , 
– обратное ребро и 
, то – предок .
Определим функцию «нижний» 
:
обратное ребро , где – потомок (или 
), а – предок (не отец при , т. к. – обратное ребро).
 |
(На рисунке значения 
– черные, 
– красные).
Значения функции 
нужно определять рекурсивно, вместе с поиском в глубину, как минимальное из 3 значений:
1. 
(начальное значение).
2. 
, где – сын .
3. 
, если обратное ребро 
.
Следствие последней леммы:
– не корень и точка сочленения 
, где – сын .
При поиске в глубину будем помещать все выделенные ребра (древесные и обратные) в стек и выталкивать оттуда мн-ва ребер, принадлежащих отдельным двусвязным компонентам. Для этого достаточно при рекурсивном подъеме находить древесные ребра 
, для которых : все ребра от и выше в стеке одной компоненте.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 |
Основные порталы (построено редакторами)