Oczekiwany algorytm MST w czasie liniowym

Algorytm oczekiwanego czasu liniowego MST jest losowym algorytmem do obliczania minimalnego rozpinającego lasu grafu ważonego bez izolowanych wierzchołków . Został opracowany przez Davida Kargera , Philipa Kleina i Roberta Tarjana . Algorytm opiera się na technikach z algorytmu Borůvki wraz z algorytmem weryfikacji minimalnego drzewa rozpinającego w czasie liniowym. Łączy paradygmaty projektowania algorytmów dziel i rządź , algorytmów zachłannych i algorytmów losowych , aby osiągnąć oczekiwaną liniową wydajność .

Algorytmy deterministyczne, które znajdują minimalne drzewo rozpinające, obejmują algorytm Prima , algorytm Kruskala , algorytm odwrotnego usuwania i algorytm Borůvki .

Przegląd

Kluczowym wglądem w algorytm jest krok losowego próbkowania, który dzieli wykres na dwa podgrafy poprzez losowe wybieranie krawędzi do uwzględnienia w każdym podgrafie. Algorytm rekurencyjnie znajduje las o minimalnej rozpiętości pierwszego podproblemu i wykorzystuje rozwiązanie w połączeniu z algorytmem weryfikacji w czasie liniowym, aby odrzucić krawędzie grafu, które nie mogą znajdować się w drzewie o minimalnej rozpiętości. Procedura zaczerpnięta z algorytmu Borůvki jest również używana do zmniejszania rozmiaru grafu przy każdej rekurencji .

Krok Borówki

Każda iteracja algorytmu opiera się na adaptacji algorytmu Borůvki, zwanej krokiem Borůvki :

 Dane wejściowe: Graf  G  bez izolowanych wierzchołków 1 Dla każdego wierzchołka  v  wybierz najjaśniejszą krawędź padającą na  v  2 Utwórz skrócony graf  G'  , zastępując każdy składnik  G  połączony krawędziami wybranymi w kroku 1 pojedynczym wierzchołkiem 3 Usuń wszystkie izolowane wierzchołki, pętle własne i nieminimalne powtarzające się krawędzie z  G'  Dane wyjściowe: Krawędzie wybrane w kroku 1 i skrócony graf  G'  

Krok Borůvki jest równoważny wewnętrznej pętli algorytmu Borůvki, która działa w czasie O ( m ), gdzie m jest liczbą krawędzi w G . Ponadto, ponieważ każdą krawędź można wybrać co najwyżej dwa razy (raz na każdy incydentny wierzchołek), maksymalna liczba odłączonych komponentów po kroku 1 jest równa połowie liczby wierzchołków. Zatem krok Borůvki zmniejsza liczbę wierzchołków w grafie co najmniej dwukrotnie i usuwa co najmniej n /2 krawędzi, gdzie n jest liczbą wierzchołków w G .

Przykład wykonania kroku Borůvka

Obraz	Opis
	Najjaśniejsza krawędź incydentu na każdym wierzchołku jest podświetlona na zielono.
	Graf jest skracany, a każdy komponent połączony krawędziami wybranymi w kroku 1 jest zastępowany pojedynczym wierzchołkiem. Spowoduje to utworzenie dwóch superwęzłów. Wszystkie krawędzie z oryginalnego wykresu pozostają.
	Krawędzie tworzące własne pętle do superwęzłów są usuwane.
	Nieminimalne nadmiarowe krawędzie między superwęzłami są usuwane.
	Wynikiem jednego Kroku Borůvki na przykładowym grafie jest graf z dwoma superwęzłami połączonymi pojedynczą krawędzią.

Krawędzie F-heavy i F-light

W każdej iteracji algorytm usuwa krawędzie o określonych właściwościach, które wykluczają je z minimalnego drzewa rozpinającego . Są to tak zwane krawędzie ciężkie F i są zdefiniowane w następujący sposób. Niech F będzie lasem na grafie H . Krawędź F-ciężka to krawędź e łącząca wierzchołki u , v , której waga jest ściśle większa niż waga najcięższej krawędzi na ścieżce od u do v w F . (Jeśli ścieżka nie istnieje w F, uważa się, że ma nieskończoną wagę). Każda krawędź, która nie jest F-ciężka, jest F-lekka . Jeśli F jest podgrafem G , to żadna krawędź F-ciężka w G nie może znajdować się w minimalnym drzewie rozpinającym G według właściwości cycle . Biorąc pod uwagę las, krawędzie F-heavy mogą być obliczane w czasie liniowym przy użyciu algorytmu weryfikacji minimalnego drzewa rozpinającego.

Algorytm

Dane wejściowe: Graf G bez izolowanych wierzchołków

1. Jeśli G jest pusty, zwróć pusty las
2. Utwórz skrócony graf G' , wykonując dwa kolejne kroki Borůvki na G
3. Utwórz podgraf H , wybierając każdą krawędź w G' z prawdopodobieństwem 1/2. Rekurencyjnie zastosuj algorytm do H , aby uzyskać jego minimalny las rozpinający F .
4. Usuń wszystkie ostre krawędzie F z G' (gdzie F jest lasem z kroku 3) za pomocą algorytmu weryfikacji drzewa rozpinającego w czasie liniowym.
5. Rekurencyjnie zastosuj algorytm do G', aby uzyskać jego minimalny las rozpinający.

Wynik: Las o minimalnej rozpiętości G' i skrócone krawędzie ze stopni Borůvka

Poprawność

Poprawność dowodzi się przez indukcję po liczbie wierzchołków grafu. Przypadek podstawowy jest trywialnie prawdziwy. Niech T* będzie minimalnym drzewem rozpinającym G . Każda krawędź wybrana w kroku Borůvki jest w T* przez właściwość cut i żadna z krawędzi usuniętych w celu utworzenia skróconego wykresu nie jest w T* przez właściwość cut (dla nadmiarowych krawędzi) i właściwość cycle (dla pętli własnych). Pozostałe krawędzie T* , które nie zostały wybrane w kroku 2, tworzą minimalne drzewo rozpinające grafu skróconego według właściwości cięcia (niech każde przecięcie będzie superwęzłem). Każda krawędź F-heavy nie znajduje się w minimalnym drzewie rozpinającym według właściwości cycle . Ostatecznie F' jest minimalnym drzewem rozpinającym grafu skróconego według hipotezy indukcyjnej. W ten sposób F' i krawędzie skurczone krawędzie stopni Borůvki tworzą minimalne drzewo rozpinające.

Wydajność

Oczekiwana wydajność jest wynikiem etapu losowego próbkowania. Skuteczność etapu losowego próbkowania jest opisana przez następujący lemat, który ogranicza liczbę światła F w G , ograniczając w ten sposób rozmiar drugiego podproblemu.

Lemat o losowym próbkowaniu

Lemat — Niech H będzie podgrafem G utworzonym przez włączenie każdej krawędzi G niezależnie z prawdopodobieństwem p i niech F będzie minimalnym lasem rozpinającym H . Oczekiwana liczba krawędzi F-light w G to co najwyżej np , gdzie n to liczba wierzchołków w G

Aby udowodnić lemat, zbadaj krawędzie G podczas dodawania ich do H . Liczba F-light w G jest niezależna od kolejności, w jakiej wybierane są krawędzie H , ponieważ minimalny las obejmujący H jest taki sam dla wszystkich rzędów wyboru. Ze względu na dowód rozważ wybranie krawędzi dla H , biorąc krawędzie G pojedynczo w kolejności od najlżejszej do najcięższej. Niech e będzie rozważaną bieżącą krawędzią. Jeśli punkty końcowe e znajdują się w dwóch rozłączonych komponentach H , to e jest najlżejszą krawędzią łączącą te komponenty, a jeśli zostanie dodana do H , będzie w F przez właściwość cut . Oznacza to również, że e jest F-lekkie, niezależnie od tego, czy jest dodawane do H , czy nie , ponieważ później brane są pod uwagę tylko cięższe krawędzie. Jeśli oba punkty końcowe e znajdują się w tej samej składowej H , to jest (i zawsze będzie) F-ciężkie według właściwości cyklu . Krawędź e jest następnie dodawana do H z prawdopodobieństwem p .

Maksymalna liczba krawędzi F-light dodanych do H wynosi n -1, ponieważ każde minimalne drzewo rozpinające H ma n -1 krawędzi. Po dodaniu n -1 krawędzi F-light do H żadna z kolejnych branych pod uwagę krawędzi nie jest F-light według właściwości cyklu . Zatem liczba krawędzi F-light w G jest ograniczona przez liczbę krawędzi F-light branych pod uwagę dla H przed dodaniem n -1 krawędzi F-light do H . Ponieważ dowolna krawędź światła F jest dodawana z prawdopodobieństwem p , jest to równoważne z rzucaniem monetą z prawdopodobieństwem p wypadnięcia orła, dopóki nie pojawi się n -1 orłów. Całkowita liczba rzutów monetą jest równa liczbie krawędzi F-light w G . Rozkład liczby rzutów monetą jest określony przez odwrotny rozkład dwumianowy z parametrami n -1 i p . Dla tych parametrów oczekiwaną wartością tego rozkładu jest ( n -1)/ p .

Oczekiwana analiza

Pomijając pracę wykonaną w podproblemach rekurencyjnych, całkowita ilość pracy wykonanej w jednym wywołaniu algorytmu jest liniowa pod względem liczby krawędzi w grafie wejściowym. Krok 1 zajmuje stały czas. Kroki Borůvki mogą być wykonywane w czasie liniowo w stosunku do liczby krawędzi, jak wspomniano w dotyczącej kroku Borůvka . Krok 3 przechodzi przez krawędzie i rzuca pojedynczą monetą dla każdej z nich, tak aby liczba krawędzi była liniowa. Krok 4 można wykonać w czasie liniowym przy użyciu zmodyfikowanego algorytmu weryfikacji minimalnego drzewa rozpinającego w czasie liniowym. Ponieważ praca wykonana w jednej iteracji algorytmu jest liniowa pod względem liczby krawędzi, praca wykonana w jednym pełnym przebiegu algorytmu (włączając wszystkie wywołania rekurencyjne) jest ograniczona przez stały współczynnik pomnożony przez całkowitą liczbę krawędzi w pierwotnym problemie i wszystkie podproblemy rekurencyjne.

Każde wywołanie algorytmu generuje co najwyżej dwa podproblemy, więc zbiór podproblemów tworzy drzewo binarne . Każdy krok Borůvki zmniejsza liczbę wierzchołków co najmniej dwukrotnie, więc po dwóch krokach Borůvki liczba wierzchołków została zmniejszona czterokrotnie. Tak więc, jeśli oryginalny graf ma n wierzchołków i m krawędzi, to na głębokości d drzewa każdy podproblem znajduje się na grafie złożonym z co najwyżej n /4 ^d wierzchołków. Również drzewo ma co najwyżej log ₄ n poziomów.

Lewe ścieżki drzewa binarnego są zaznaczone na niebiesko

Aby uzasadnić drzewo rekurencji, niech lewy problem potomny będzie podproblemem w wywołaniu rekurencyjnym w kroku 3, a prawy problem potomny będzie podproblemem w wywołaniu rekurencyjnym w kroku 5. Policz całkowitą liczbę krawędzi w pierwotnym problemie i wszystkich podproblemach licząc liczbę krawędzi w każdej lewej ścieżce drzewa. Ścieżka lewa zaczyna się od prawego dziecka lub korzenia i obejmuje wszystkie węzły, do których można dotrzeć ścieżką lewych dzieci. Lewe ścieżki drzewa binarnego są zaznaczone na niebiesko na diagramie po prawej stronie.

Każda krawędź w problemie lewego dziecka jest wybierana z krawędzi problemu macierzystego (pomniejszona o krawędzie skrócone w krokach Borůvki ) z prawdopodobieństwem 1/2. Jeśli problem macierzysty ma x krawędzi, to oczekiwana liczba krawędzi w problemie lewego dziecka wynosi co najwyżej x /2. Jeśli x zostanie zastąpione zmienną losową X , to przez liniowość oczekiwań oczekiwana liczba krawędzi w problemie lewego dziecka Y jest dana przez ${\ Displaystyle E [Y] \ równoważnik E [X]/2}$ . Zatem jeśli oczekiwana liczba krawędzi w problemie na górze lewej ścieżki wynosi k , to suma oczekiwanej liczby krawędzi w każdym podproblemie na lewej ścieżce wynosi co najwyżej ${\ displaystyle \sum _{d=0}^{\infty}{\frac {k}{2^{d}}}=2k}$ (patrz Szeregi geometryczne ). Pierwiastek ma m krawędzi, więc oczekiwana liczba krawędzi jest równa 2 m plus dwukrotność oczekiwanej liczby krawędzi w każdym prawym podproblemie.

Oczekiwana liczba krawędzi w każdym prawym podproblemie jest równa liczbie krawędzi F-light w problemie macierzystym, gdzie F jest minimalnym drzewem rozpinającym lewego podproblemu. Liczba krawędzi F-light jest mniejsza lub równa dwukrotności liczby wierzchołków w podproblemie według lematu o próbkowaniu . Liczba wierzchołków w podproblemie na głębokości d wynosi n / 4 ^d , więc całkowita liczba wierzchołków we wszystkich właściwych podproblemach jest określona wzorem ${\ Displaystyle \ suma _ {d=1}^{\infty}{\frac {2^{d-1}n}{4^{d}}}=n/2}$ . Zatem oczekiwana liczba krawędzi w pierwotnym problemie i wszystkich podproblemach wynosi co najwyżej 2 m + n . Ponieważ n co najwyżej 2 m dla grafu bez izolowanych wierzchołków, algorytm działa w oczekiwanym czasie O ( m ).

Analiza najgorszego przypadku

Czas wykonania najgorszego przypadku jest równoważny czasowi wykonania algorytmu Borůvki . Dzieje się tak, jeśli wszystkie krawędzie są dodawane do lewego lub prawego podproblemu przy każdym wywołaniu. W tym przypadku algorytm jest identyczny z algorytmem Borůvki , który działa w O (min{ n ² , m log n }) na grafie o n wierzchołkach i m krawędziach.

Dalsza lektura

• Minimalna weryfikacja drzewa rozpinającego w czasie liniowym