Leksykograficzne przeszukiwanie wszerz

W informatyce leksykograficzne przeszukiwanie wszerz lub Lex-BFS to liniowy algorytm czasu służący do porządkowania wierzchołków grafu . Algorytm ten różni się od przeszukiwania wszerz , ale generuje kolejność zgodną z przeszukiwaniem wszerz.

Algorytm przeszukiwania leksykograficznego wszerz jest oparty na idei udoskonalania partycji i został po raz pierwszy opracowany przez Donalda J. Rose, Roberta E. Tarjana i George'a S. Luekera ( 1976 ). Bardziej szczegółowe badanie tego tematu przedstawia Corneil (2004) . Został użyty jako podprogram w innych algorytmach grafów, w tym w rozpoznawaniu wykresów akordowych i optymalnym kolorowaniu wykresów dziedzicznych od odległości .

Tło

Algorytm przeszukiwania wszerz jest zwykle definiowany przez następujący proces:

• Zainicjuj kolejkę wierzchołków grafu, z początkowym wierzchołkiem grafu jako jedynym elementem kolejki.
• Gdy kolejka nie jest pusta, usuń (usuń z kolejki) wierzchołek v z kolejki i dodaj do kolejki (umieść w kolejce) wszystkie inne wierzchołki, do których można dotrzeć krawędzią z v , które nie zostały jeszcze dodane we wcześniejszych krokach.

Jednak zamiast definiować wierzchołek do wyboru na każdym kroku w sposób imperatywny , jak ten utworzony przez operację usunięcia kolejki z kolejki, można deklaratywnie zdefiniować tę samą sekwencję wierzchołków na podstawie właściwości tych wierzchołków. Oznacza to, że standardowe przeszukiwanie wszerz jest wynikiem wielokrotnego stosowania tej reguły:

• Wielokrotnie wyprowadzaj wierzchołek v , wybierając w każdym kroku wierzchołek v , który nie został jeszcze wybrany i który ma poprzednika (wierzchołek, który ma krawędź do v ) tak wcześnie, jak to możliwe.

W niektórych przypadkach to uporządkowanie wierzchołków według pozycji wyjściowych ich poprzedników może mieć powiązania — dwa różne wierzchołki mają tego samego najwcześniejszego poprzednika. W takim przypadku kolejność wyboru tych dwóch wierzchołków może być dowolna. Dane wyjściowe leksykograficznego przeszukiwania wszerz różnią się od standardowego przeszukiwania wszerz tym, że mają spójną regułę zrywania takich więzi. W leksykograficznym przeszukiwaniu wszerz kolejność danych wyjściowych to kolejność, która zostałaby utworzona przez regułę:

• Wielokrotnie wyprowadzaj wierzchołek v , wybierając w każdym kroku wierzchołek v , który nie został jeszcze wybrany i którego cały zestaw już wygenerowanych poprzedników jest tak mały, jak to możliwe w porządku leksykograficznym .

Tak więc, gdy dwa wierzchołki v i w mają tego samego najwcześniejszego poprzednika, wcześniej niż jakiekolwiek inne niewybrane wierzchołki, standardowy algorytm przeszukiwania wszerz uporządkuje je arbitralnie. Zamiast tego w tym przypadku algorytm LexBFS wybierałby między v i w na podstawie kolejności wyjściowej ich drugich najstarszych poprzedników. Jeśli tylko jeden z nich ma drugiego najstarszego poprzednika, który został już wydrukowany, ten jest wybrany. Jeśli zarówno v, jak i w mają tego samego drugiego najstarszego poprzednika, wtedy remis rozstrzyga się, biorąc pod uwagę ich trzeci najwcześniejszy poprzednik i tak dalej.

Zastosowanie tej reguły bezpośrednio poprzez porównanie wierzchołków zgodnie z tą regułą prowadziłoby do nieefektywnego algorytmu. Zamiast tego leksykograficzne przeszukiwanie wszerz wykorzystuje strukturę danych partycjonowania zestawu w celu wydajniejszego tworzenia tego samego uporządkowania, tak jak standardowe przeszukiwanie wszerz wykorzystuje strukturę danych kolejki do wydajnego generowania uporządkowania.

Algorytm

Algorytm przeszukiwania leksykograficznego wszerz zastępuje kolejkę wierzchołków standardowego przeszukiwania wszerz uporządkowaną sekwencją zestawów wierzchołków. Zbiory w sekwencji tworzą podział pozostałych wierzchołków. W każdym kroku wierzchołek v z pierwszego zestawu w sekwencji jest usuwany z tego zestawu, a jeśli to usunięcie powoduje, że zestaw staje się pusty, to zestaw jest usuwany z sekwencji. Następnie każdy zestaw w sekwencji jest zastępowany dwoma podzbiorami: sąsiadami v i nie-sąsiadami v . Podzbiór sąsiadów jest umieszczany wcześniej w sekwencji niż podzbiór elementów niebędących sąsiadami. W pseudokodzie algorytm można wyrazić w następujący sposób:

• Zainicjuj sekwencję Σ zbiorów, aby zawierała pojedynczy zbiór zawierający wszystkie wierzchołki.
• Zainicjuj sekwencję wyjściową wierzchołków, aby była pusta.
• Podczas gdy Σ jest niepuste:
  • Znajdź i usuń wierzchołek v z pierwszego zbioru w Σ
  • Jeśli pierwszy zestaw w Σ jest teraz pusty, usuń go z Σ
  • Dodaj v na końcu sekwencji wyjściowej.
  • Dla każdej krawędzi vw takiej, że w nadal należy do zbioru S w Σ:
    • Jeśli zbiór S zawierający w nie został jeszcze zastąpiony podczas przetwarzania v , utwórz nowy pusty zbiór zastępczy T i umieść go przed S w sekwencji; w przeciwnym razie niech T będzie zbiorem poprzedzającym S .
    • Przenieś w z S do T , a jeśli to spowoduje, że S stanie się puste, usuń S z Σ.

Każdy wierzchołek jest przetwarzany raz, każda krawędź jest badana tylko wtedy, gdy przetwarzane są jej dwa punkty końcowe i (przy odpowiedniej reprezentacji zbiorów w Σ, która pozwala na przenoszenie elementów z jednego zbioru do drugiego w stałym czasie) każda iteracja pętli wewnętrznej zajmuje tylko stały czas. Dlatego, podobnie jak prostsze algorytmy przeszukiwania grafów, takie jak przeszukiwanie wszerz i przeszukiwanie w głąb , algorytm ten wymaga czasu liniowego.

Algorytm nazywa się przeszukiwaniem leksykograficznym wszerz, ponieważ tworzony przez niego porządek jest uporządkowaniem, które można również uzyskać przez przeszukiwanie wszerz, oraz ponieważ jeśli porządkowanie jest używane do indeksowania wierszy i kolumn macierzy sąsiedztwa grafu następnie algorytm sortuje wiersze i kolumny w porządku leksykograficznym .

Aplikacje

Wykresy akordowe

Graf G jest definiowany jako akordowy , jeśli jego wierzchołki mają doskonały porządek eliminacji , taki porządek, że dla dowolnego wierzchołka v sąsiedzi, którzy występują później w porządku, tworzą klikę. W grafie akordowym odwrotność porządku leksykograficznego jest zawsze doskonałym porządkiem eliminacji. Dlatego można sprawdzić, czy wykres jest akordowy w czasie liniowym za pomocą następującego algorytmu:

• Użyj przeszukiwania leksykograficznego wszerz, aby znaleźć uporządkowanie leksykograficzne G
• Dla każdego wierzchołka v :
  • Niech w będzie sąsiadem v występującym przed v , jak najbliżej v w sekwencji
    • (Kontynuuj do następnego wierzchołka v , jeśli nie ma takiego w )
  • Jeśli zbiór wcześniejszych sąsiadów v (z wyłączeniem samego w ) nie jest podzbiorem zbioru wcześniejszych sąsiadów w , wykres nie jest akordowy
• Jeśli pętla kończy się bez wykazania, że ​​wykres nie jest akordowy, to jest akordowy.

Ta aplikacja była pierwotną motywacją, która skłoniła Rose, Tarjana i Luekera (1976) do opracowania pierwszego algorytmu przeszukiwania leksykograficznego.

Kolorowanie wykresów

graf G jest doskonale uporządkowany , jeśli istnieje ciąg jego wierzchołków z tą właściwością, że dla każdego indukowanego podgrafu G algorytm zachłannego kolorowania , który koloruje wierzchołki w indukowanym porządku sekwencji, gwarantuje uzyskanie optymalnego kolorowania.

W przypadku wykresu akordowego idealne uporządkowanie eliminacji jest doskonałym uporządkowaniem: numer koloru użytego dla dowolnego wierzchołka jest wielkością kliki utworzonej przez ten wierzchołek i jego wcześniejszych sąsiadów, więc maksymalna liczba użytych kolorów jest równa rozmiarowi największa klika na wykresie, a żadne kolorowanie nie może używać mniejszej liczby kolorów. Indukowany podgraf wykresu akordowego jest akordowy, a indukowana podsekwencja jego idealnego uporządkowania eliminacji jest doskonałym uporządkowaniem eliminacji na podgrafie, więc wykresy akordowe są doskonale uporządkowane, a do ich optymalnego pokolorowania można zastosować przeszukiwanie leksykograficzne wszerz.

Ta sama właściwość jest prawdziwa dla większej klasy grafów, grafów dziedzicznych od odległości : grafy dziedziczne od odległości są doskonale uporządkowane, z doskonałym uporządkowaniem wynikającym z odwrotności porządku leksykograficznego, więc przeszukiwanie leksykograficzne wszerz może być używane w połączeniu z chciwymi algorytmami kolorowania, aby optymalnie pokolorować je w czasie liniowym.

Inne aplikacje

Bretschera i in. (2008) opisują rozszerzenie leksykograficznego przeszukiwania wszerz, które zrywa wszelkie dodatkowe powiązania przy użyciu wykresu dopełnienia grafu wejściowego. Jak pokazują, można to wykorzystać do rozpoznawania kografów w czasie liniowym. Habiba i in. (2000) opisują dodatkowe zastosowania leksykograficznego przeszukiwania wszerz, w tym rozpoznawanie grafów porównywalności i grafów interwałowych .

Zamawianie LexBFS

Mówimy, że wyliczenie wierzchołków grafu jest uporządkowaniem LexBFS, jeśli jest możliwym wynikiem zastosowania LexBFS do tego grafu.

Niech będzie wykresem z $\$ . $Displaystyle G = (V, E)}$ Przypomnijmy, że jest zbiorem sąsiadów $v)}$$displaystyle N ($ . Niech ${\ Displaystyle \ sigma = (v_ {1}, \ kropki, v_ {n})}$ będzie wyliczeniem wierzchołków ${\ displaystyle V}$ . Wyliczenie jest uporządkowaniem LexBFS (ze źródłem $)$$\ Displaystyle v_ {1}}$ , jeśli dla wszystkich ${\ Displaystyle 1 \ równoważnik i <j < k \ równoważnik n}$ z ${\ Displaystyle v_ {i} \ w N (v_ {k}) \ setminus N (v_ {j})}$ istnieje ${\ Displaystyle m <i}$ takie, że ${\ Displaystyle v_ {m} \ w N (v_ {j}) \ setminus N (v_ {k})}$ .

Notatki

•   Brandstädt, Andreas ; Le Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X .
•   Bretscher, Anna; Korneil, Derek ; Habib, Michel; Paul, Christophe (2008), „Prosty algorytm rozpoznawania kografów LexBFS w czasie liniowym” , SIAM Journal on Discrete Mathematics , 22 (4): 1277–1296, CiteSeerX 10.1.1.188.5016 , doi : 10.1137/060664690 .
• Corneil, Derek G. (2004), „Najpierw przeszukiwanie leksykograficzne wszerz - ankieta”, Graph-Theoretic Methods in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Niemcy, 21-23 czerwca 2004, Revised Papers, Wykład Notatki z informatyki, tom. 3353, Springer-Verlag, s. 1–19, doi : 10.1007/978-3-540-30559-0_1 .
• Habib, Michel; McConnell, Ross; Paweł, Krzysztof; Viennot, Laurent (2000), „Lex-BFS i udoskonalanie partycji, z zastosowaniami do orientacji przechodniej, rozpoznawania wykresów interwałowych i testowania kolejnych”, Theoretical Computer Science , 234 (1–2): 59–84, doi : 10.1016 / S0304 -3975(97)00241-7 .
• Róża, DJ; Tarjan, RE ; Lueker, GS (1976), „Algorytmiczne aspekty eliminacji wierzchołków na wykresach”, SIAM Journal on Computing , 5 (2): 266–283, doi : 10.1137/0205021 .