Свързаност в графики

Съдържание

1 Основни определения

Нека е дадена (насочена или ненасочена) графика [math]G = (V, E)[/math]. The sequence [math]P(u, v)[/math] of edges [math]e_1 = (u, w_1)[/math] , [math]e_2 = (w_1, w_2)[/math] , …, [math]e_k = (w_, v)[/math] is called apathfrom [math]u[/math] to [math]v[/math] . В този случай [math]v[/math]е достъпенот [math]u[/math] . Смята се, че празен път [math]P(u, u)[/math] води от върха [math]u[/math] до себе си, тоест всеки връх е достижим от себе си. Непразният път [math]P(u, u)[/math] се наричацикъл(затворено преминаване).

Неориентиранграф есвързан, ако всички негови върхове са достижими от някакъв връх (еквивалентно, от всеки от неговите върхове).

Ориентиранаграфа се нарича

слабо свързанако съответният неориентиран граф е свързан;
силно свързанако някой [math]v[/math] връх е достъпен от всеки друг [math]v[/math] връх.

Свързаният компонентна неориентиран граф е максимален (по отношение на включването) свързан подграф.

Силно свързан компонентна насочен граф е силно свързан подграф, който е максимален по отношение на включването. С други думи, това е подграф, всеки два от чиито върхове принадлежат на някакъв цикъл и съдържа всички такива цикли за своите върхове.

Моств графика е ребро, чието премахване увеличава броя на свързаните компоненти.

Пантав графа е връх, премахването на който увеличава броя на свързаните компоненти.

За свързан граф се казва, че евърх-[math]k[/math]-свързан(или просто [math]k[/math]-свързан), акоима повече от [math]k[/math] върха и след премахване на всички [math]k-1[/math] от тях остава свързан. Максималният такъв брой [math]k[/math] се наричавърхова свързаност(или простосвързаност) на графиката. 1-свързан граф се нарича свързан, 2-свързан граф се нарича двойно свързан.

Казва се, че свързан график еedge-[math]k[/math]-свързан, ако остане свързан след премахване на всички [math]k-1[/math] ребра. Максималното такова число [math]k[/math] се наричакрайна свързаностна графиката.

Двусвързаният компонентна граф е максимален (по отношение на включването) двойносвързан подграф.

2 свойства

Еквивалентни дефиниции на свързан компонент:

всички върхове, достижими от всеки избран връх;
набор от върхове, които са достижими един от друг и не са достижими от други върхове.

Релацията „върхът [math]v[/math] е достижим от върха [math]u[/math] ” е релация на еквивалентност. По този начин търсенето на свързани компоненти на графа е същото като възстановяването на пълна релация на еквивалентност за неговата част.

Алтернативни определения за мост:

ръбът е мост, ако не участва в никакъв цикъл;
Ребро [math]e[/math] е мост, ако съществува двойка върхове [math](u, v)[/math] от един и същ свързан компонент, всеки път [math]P(u, v)[/math] между които минава през ръба [math]e[/math] .

Панта разделя двойно свързаните компоненти (ако два двойно свързани компонента имат общ връх, тогава това е шарнир).

Всеки от върховете на моста е шарнир (освен когато мостът е единственият ръб на този връх).

Силно свързан компонент е обединението на всички цикли, минаващи през неговите върхове.

3 Алгоритми

Компонентите за свързване могат да бъдат намерени:

последователно прилагане на алгоритъма за търсене в ширина във времето [math]O(m)[/math] ;
използване на система от несвързани множества[1] във времето [math]O(m \alpha(m, n))[/math] , с възможност за ефективна многопоточна реализация [2] ;
паралелен алгоритъм на Shiloah-Vishkin[3] във времето [math]O(\ln n)[/math] на [math]n + 2m[/math] процесори.

Силно свързани компоненти могат да бъдат намерени:

Мостовете могат да бъдат намерени:

чрез алгоритъма[8] на Тарян (по време на търсене в дълбочина) във времето [math]O(m)[/math] ;
паралелен алгоритъм на Тарян-Вишкин[9] във времето [math]O(\ln n)[/math] на [math]O(m + n)[/math] процесори;
Онлайн алгоритъм на Уестбрук-Тарян [10] във времето [math]O(m \alpha(m, n))[/math] .

Компонентите за двусвързаност могат да бъдат намерени:

чрез алгоритъма на Тарян[4] (по време на търсене в дълбочина) във времето [math]O(m)[/math] (алгоритъмът намира и съответните панти);
паралелен алгоритъм на Тарян-Вишкин[11] във времето [math]O(\ln n)[/math] на [math]O(m + n)[/math] процесори (алгоритъмът може също да намира мостове);
Онлайн алгоритъм на Уестбрук-Тарян [10] във времето [math]O(m \alpha(m, n))[/math] .

Свързването на ръба на графика може да бъде намерено чрез алгоритъма на Габов [13] във времето [math]O(k m \ln (n^2/m))[/math] за насочен график и [math]O(m + k^2 n \ln (n/k))[/math] за неориентиран график. Проверката на свойството [math]k[/math] -свързване чрез същия алгоритъм може да се направи за време [math]O(m + n \ln n)[/math] .