Słaby komponent

W teorii grafów słabe składowe grafu skierowanego dzielą wierzchołki grafu na podzbiory, które są całkowicie uporządkowane według osiągalności . Tworzą one najlepszą partycję zbioru wierzchołków, który jest całkowicie uporządkowany w ten sposób.

Definicja

Słabe komponenty zostały zdefiniowane w artykule z 1972 roku przez Ronalda Grahama , Donalda Knutha i (pośmiertnie) Theodore'a Motzkina , przez analogię do silnie połączonych składowych grafu skierowanego, które tworzą możliwie najlepszy podział wierzchołków grafu na podzbiory, które są częściowo uporządkowane według osiągalności. Zamiast tego zdefiniowali słabe komponenty jako najdokładniejszy podział wierzchołków na podzbiory, które są całkowicie uporządkowane według osiągalności.

Bardziej szczegółowo, Knuth (2022) definiuje słabe składowe poprzez kombinację czterech symetrycznych relacji na wierzchołkach dowolnego skierowanego wykresu, oznaczonych tutaj jako ${\ Displaystyle \ Leftrightarrow}$ , ${\ Displaystyle \ równoległy}$ , ${\ Displaystyle \ około}$ i $\ Displaystyle \ asimp}$ { :

Dla dowolnych dwóch wierzchołków ${$ $\ displaystyle u} i v {\$ , gdy jest osiągalny z drugiego: istnieją ścieżki na wykresie u $v$ } od ${\ displaystyle u}$ do ${\ displaystyle v}$ i od ${\ displaystyle v}$ do ${\ displaystyle u}$ . Relacja to ${\ displaystyle \ Leftrightarrow}$ relacja równoważności i jej klasy równoważności służą do definiowania silnie powiązanych składowych grafu.
Dla dowolnych dwóch wierzchołków $gdy żaden wierzchołek nie jest$ i tylko wtedy, $\$ z drugiego: $u \ równoległy v}$ Displaystyle wykres w dowolnym kierunku między i $v}$ . $displaystyle$
Dla dowolnych dwóch wierzchołków wykresu ${$ $u \ około v}$ $\ Displaystyle$ wtedy i tylko wtedy, gdy $Leftrightarrow v}$ \ lub ${\ displaystyle u \ równoległy v}$ . Oznacza to, że między tymi wierzchołkami może istnieć połączenie dwukierunkowe lub mogą one być wzajemnie nieosiągalne, ale mogą nie mieć połączenia jednokierunkowego.
Relacja jest zdefiniowana jako domknięcie $\ w przybliżeniu}$ . przechodnie $displaystyle$ To znaczy, $v$ istnieje sekwencja wierzchołków, zaczynając od u ≈ ${\ displaystyle v}$ , $Displaystyle u \ około \ cdots \ około v}$ $\ Displaystyle u \ asymp v}$ tak, że każda kolejna para w sekwencji jest powiązana przez ${\ displaystyle \ około}$ .

Wtedy ${\ displaystyle \ asymp}$ jest relacją równoważności : każdy wierzchołek jest powiązany ze sobą przez (ponieważ może dotrzeć do siebie w obu kierunkach ścieżkami o długości zero), dowolne dwa wierzchołki, które są powiązane przez ≍ {\ displaystyle \ $asymp$ $asymp}$ $\$ $Displaystyle \$ zamienić na siebie bez zmiany tej relacji (ponieważ jest zbudowany z relacji symetrycznych i $}$ ), a $przechodnią$ relacją (ponieważ jest przechodnim zamknięciem innej relacji) . Podobnie jak w przypadku każdej relacji równoważności, można jej użyć do podzielenia wierzchołków wykresu na klasy równoważności , podzbiory wierzchołków takie, że dwa wierzchołki są powiązane przez ${\ Displaystyle \ asymp}$ wtedy i tylko wtedy, gdy należą do tej samej klasy równoważności . Te klasy równoważności są słabymi składnikami danego wykresu.

Oryginalna definicja Grahama, Knutha i Motzkina jest równoważna, ale sformułowana nieco inaczej. sol $G}$ . $uwagę$ wykres $^$ , skierowany najpierw konstruują kolejny wykres jako wykres dopełnienia przechodniego domknięcia Jak opisuje Tarjan (1974) , krawędzie w reprezentują ścieżki niebędące ścieżkami ${\ displaystyle {\ hat {G}}}$ , pary wierzchołków, które nie są połączone ścieżką w ${\ displaystyle G}$ . Następnie dwa wierzchołki należą do tego samego słabego komponentu, gdy albo należą do $}}$ . tego samego silnie połączonego komponentu, albo $displaystyle {\ hat {G$ Jak dowodzą Graham, Knuth i Motzkin, warunek ten definiuje relację równoważności, taką samą, $powyżej$ zdefiniowano .

Zgodnie z tymi definicjami graf skierowany jest nazywany słabo spójnym , jeśli ma dokładnie jeden słaby składnik. Oznacza to, że jego wierzchołki nie mogą być podzielone na dwa podzbiory, tak że wszystkie wierzchołki w pierwszym podzbiorze mogą dotrzeć do wszystkich wierzchołków w drugim podzbiorze, ale tak, że żaden z wierzchołków w drugim podzbiorze nie może dotrzeć do żadnego z wierzchołków w pierwszym podzbiorze. Różni się od innych pojęć słabej łączności w literaturze, takich jak łączność i komponenty w podstawowym niepowiązanym grafie, dla którego Knuth sugeruje alternatywną terminologię niekierowane komponenty .

Nieruchomości

Jeśli $mogą$ są dwoma słabymi składnikami skierowanego wykresu, to albo wszystkie wierzchołki w $dotrzeć$ do wszystkich wierzchołków w $Y}$ displaystyle ścieżkami na wykresie $\ displaystyle X}$ lub wszystkie wierzchołki w mogą dotrzeć do wszystkich wierzchołków w $\ displaystyle X$ . $}$ Jednak między tymi dwoma komponentami nie mogą istnieć relacje osiągalności w obu kierunkach. Dlatego możemy zdefiniować uporządkowanie słabych komponentów, zgodnie z którym $,$ gdy w $wszystkie$ wierzchołki $.$ osiągnąć Z definicji ${\ Displaystyle X \ n mniej X}$ . To jest relacja asymetryczna (dwa elementy mogą być powiązane tylko w jednym kierunku, a nie w drugim) i dziedziczy właściwość bycia relacją przechodnią z przechodniości osiągalności. Dlatego definiuje całkowite uporządkowanie słabych komponentów. Jest to najlepszy możliwy podział wierzchołków na całkowicie uporządkowany zbiór wierzchołków zgodny z osiągalnością.

To uporządkowanie słabych składowych można alternatywnie interpretować jako $<v}$ uporządkowanie samych wierzchołków, z tą właściwością, że gdy słabym uporządkowaniu koniecznie istnieje ścieżka od $}$ $\ displaystyle u$ $\$ do , ale nie od $displaystyle v}$ do $\ displaystyle u}$ . Nie jest to jednak pełna charakterystyka tego słabego uporządkowania, ponieważ dwa wierzchołki $displaystyle$ $u}$ i mogą mieć taką samą kolejność osiągalności, jednocześnie należąc do tego samego słabego komponentu, co .

Każdy słaby komponent jest połączeniem silnie połączonych komponentów. Jeśli silnie połączone składowe dowolnego danego grafu są skrócone do pojedynczych wierzchołków, tworząc skierowany graf acykliczny ( kondensacja danego grafu), a następnie ta kondensacja jest topologicznie posortowana , to każda słaba składowa koniecznie pojawia się jako kolejny podsekwencja topologicznego Kolejność silnych składników.

Algorytmy

Algorytm obliczania słabych składowych danego grafu skierowanego w czasie liniowym został opisany przez Pacaulta (1974) , a następnie uproszczony przez Tarjana (1974) i Knutha (2022) . Jak zauważa Tarjan, silnie połączony algorytm komponentów Tarjana opiera się na przeszukiwaniu w głąb wyświetli silnie połączone komponenty w (odwrotnej) kolejności posortowanej topologicznie. Algorytm dla słabych składowych generuje silnie połączone składowe w tej kolejności i zachowuje podział składowych, które zostały wygenerowane do tej pory na słabe składowe ich indukowanego podgrafu . Po wygenerowaniu wszystkich składowych ten podział będzie opisywał słabe składowe całego grafu.

Wygodne jest utrzymywanie bieżącego podziału na słabe komponenty w stosie , przy czym każdy słaby komponent zachowuje dodatkowo listę swoich źródeł , silnie połączonych komponentów, które nie mają przychodzących krawędzi z innych silnie połączonych komponentów w tym samym słabym komponencie, z ostatnio najpierw wygenerowane źródło. Każdy nowo wygenerowany silnie połączony komponent może samodzielnie utworzyć nowy słaby komponent lub może zostać połączony z niektórymi wcześniej skonstruowanymi słabymi komponentami w pobliżu szczytu stosu, dla których nie może dotrzeć do wszystkich źródeł .

W ten sposób algorytm wykonuje następujące kroki:

Zainicjuj pusty stos słabych komponentów, z których każdy jest powiązany z listą komponentów źródłowych.
Użyj algorytmu silnie spójnych składowych Tarjana do wygenerowania silnie spójnych składowych danego grafu w odwrotności porządku topologicznego. Po wygenerowaniu każdego silnie połączonego komponentu wykonaj z nim następujące kroki: ${\ displaystyle S}$ $S$
- Podczas gdy stos nie jest pusty i nie ma krawędzi do górnego słabego składnika stosu, zdejmij ten składnik ze $.$
- Jeśli stos nadal nie jest pusty, a niektóre źródła jego górnego słabego składnika nie są uderzane przez krawędzie $z$ ponownie zdejmij ten składnik ze stosu.
- $komponent$ nowy słaby $i$ , zawierający jako źródła i wszystkie nie trafione źródła z górnego komponentu, który został wyrzucony, $na$ .

Każdy test na to, czy jakiekolwiek krawędzie od uderzenia w słaby $komponent$ można przeprowadzić w stałym czasie, gdy znajdziemy krawędź od ostatnio wygenerowanego wcześniej silnie połączonego komponentu, porównując docelowy komponent ${\ displaystyle S$ tej krawędzi do pierwszego źródła składnika drugiego od góry na stosie.