Niejawny wykres

W badaniu algorytmów grafowych niejawna reprezentacja grafu (lub prościej niejawny wykres ) to graf , którego wierzchołki lub krawędzie nie są reprezentowane jako jawne obiekty w pamięci komputera, ale są określane algorytmicznie na podstawie innych danych wejściowych, na przykład obliczalnego funkcja .

Reprezentacje sąsiedzkie

Pojęcie niejawnego wykresu jest powszechne w różnych algorytmach wyszukiwania , które są opisane w kategoriach wykresów. W tym kontekście niejawny graf można zdefiniować jako zestaw reguł definiujących wszystkich sąsiadów dla dowolnego określonego wierzchołka. Ten typ niejawnej reprezentacji grafu jest analogiczny do listy sąsiedztwa , ponieważ zapewnia łatwy dostęp do sąsiadów każdego wierzchołka. Na przykład w poszukiwaniu rozwiązania zagadki, takiej jak Kostka Rubika , można zdefiniować niejawny wykres, w którym każdy wierzchołek reprezentuje jeden z możliwych stanów sześcianu, a każda krawędź reprezentuje przejście z jednego stanu do drugiego. Łatwo jest wygenerować sąsiadów dowolnego wierzchołka, próbując wszystkich możliwych ruchów w układance i określając stany osiągnięte przez każdy z tych ruchów; konieczna jest jednak niejawna reprezentacja, ponieważ przestrzeń stanów kostki Rubika jest zbyt duża, aby algorytm mógł wyświetlić listę wszystkich jej stanów.

W teorii złożoności obliczeniowej zdefiniowano kilka klas złożoności w związku z grafami niejawnymi, zdefiniowanymi jak powyżej przez regułę lub algorytm wymieniania sąsiadów wierzchołka. Na przykład PPA to klasa problemów, w których jako dane wejściowe podaje się nieskierowany graf niejawny (w którym wierzchołki są n -bitowymi łańcuchami binarnymi, z algorytmem czasu wielomianowego do wyszczególnienia sąsiadów dowolnego wierzchołka) i wierzchołkiem nieparzystego stopnia w grafie i musi znaleźć drugi wierzchołek nieparzystego stopnia. Przez lemat uścisku dłoni , taki wierzchołek istnieje; znalezienie jednego jest problemem w NP , ale problemy, które można zdefiniować w ten sposób, niekoniecznie muszą być NP-zupełne , ponieważ nie wiadomo, czy PPA = NP. PPAD to analogiczna klasa zdefiniowana na niejawnych grafach skierowanych , która przyciągnęła uwagę algorytmicznej teorii gier, ponieważ zawiera problem obliczania równowagi Nasha . Problem testowania osiągalności jednego wierzchołka do drugiego w niejawnym grafie może być również wykorzystany do scharakteryzowania niedeterministycznych klas złożoności ograniczonych przestrzenią, w tym NL (klasa problemów, które można scharakteryzować przez osiągalność w niejawnych grafach skierowanych, których wierzchołkami są O (log n ) -bitowe łańcuchy bitów) , SL (klasa analogiczna dla grafów nieskierowanych) i PSPACE (klasa problemów, które można scharakteryzować osiągalnością w grafach niejawnych z ciągami bitów o długości wielomianu). W tym kontekście teorii złożoności wierzchołki niejawnego grafu mogą reprezentować stany a niedeterministyczna maszyna Turinga , a krawędzie mogą reprezentować możliwe przejścia stanów, ale niejawne grafy mogą być również używane do reprezentowania wielu innych typów struktur kombinatorycznych. PLS , kolejna klasa złożoności, oddaje złożoność znajdowania lokalnych optimów w niejawnym grafie.

Niejawne modele grafów były również wykorzystywane jako forma relatywizacji w celu udowodnienia separacji między klasami złożoności, które są silniejsze niż znane separacje dla modeli niezrelatywizowanych. Na przykład Childs i in. wykorzystał reprezentacje sąsiedztwa grafów niejawnych do zdefiniowania problemu przechodzenia przez graf, który można rozwiązać w czasie wielomianowym na komputerze kwantowym, ale którego rozwiązanie wymaga czasu wykładniczego na dowolnym komputerze klasycznym.

Schematy etykietowania sąsiedztwa

W kontekście efektywnych reprezentacji grafów, JH Muller zdefiniował lokalną strukturę lub schemat etykietowania sąsiedztwa dla grafu G w danej rodzinie F grafów, który miał być przypisaniem O (log n ) -bitowego identyfikatora każdemu wierzchołkowi G , wraz z algorytmem (który może zależeć od F , ale jest niezależny od indywidualnego grafu G ), który przyjmuje jako dane wejściowe dwa identyfikatory wierzchołków i określa, czy są one punktami końcowymi krawędzi w G . Oznacza to, że ten typ reprezentacji niejawnej jest analogiczny do macierzy sąsiedztwa : łatwo jest sprawdzić, czy dwa wierzchołki sąsiadują ze sobą, ale znalezienie sąsiadów dowolnego wierzchołka może wymagać przejścia przez wszystkie wierzchołki i sprawdzenia, które z nich są sąsiadami.

Rodziny wykresów ze schematami etykietowania sąsiedztwa obejmują:

Grafy stopni ograniczonych

Jeśli każdy wierzchołek w G ma co najwyżej d sąsiadów, można ponumerować wierzchołki G od 1 do n i niech identyfikatorem wierzchołka będzie ( d + 1) -krotka jego własnej liczby i liczb jego sąsiedzi. Dwa wierzchołki sąsiadują ze sobą, gdy pierwsze liczby w ich identyfikatorach pojawiają się później w identyfikatorze drugiego wierzchołka. Mówiąc bardziej ogólnie, to samo podejście można zastosować do zapewnienia niejawnej reprezentacji grafów z ograniczoną arborycznością lub ograniczoną degeneracją , w tym grafy planarne i grafy z dowolnej rodziny grafów drugorzędnych zamkniętych .

Wykresy przecięć

Wykres interwałowy to wykres przecięcia zestawu odcinków linii rzeczywistej . Można podać schemat etykietowania sąsiedztwa, w którym punkty będące końcami odcinków są ponumerowane od 1 do 2 n a każdy wierzchołek wykresu jest reprezentowany przez liczby dwóch punktów końcowych odpowiadającego mu przedziału. Dzięki tej reprezentacji można sprawdzić, czy dwa wierzchołki sąsiadują ze sobą, porównując reprezentujące je liczby i sprawdzając, czy liczby te definiują nakładające się przedziały. To samo podejście działa w przypadku innych grafów przecięć geometrycznych, w tym wykresów ograniczonej pudełkowatości i wykresów kołowych oraz podrodzin tych rodzin, takich jak grafy dziedziczne odległości i kografy . Jednak reprezentacja wykresu przecięcia geometrycznego nie zawsze implikuje istnienie schematu etykietowania sąsiedztwa, ponieważ może wymagać więcej niż logarytmicznej liczby bitów, aby określić każdy obiekt geometryczny. Na przykład przedstawienie wykresu jako wykresu dysku jednostkowego może wymagać wykładniczo wielu bitów dla współrzędnych środków dysków.

Niskowymiarowe grafy porównywalności

Graf porównywalności dla zbioru częściowo uporządkowanego ma wierzchołek dla każdego elementu zbioru i krawędź między dwoma elementami zbioru, które są powiązane częściowym porządkiem. Wymiar zamówienia rzędu częściowego to minimalna liczba rzędów liniowych, których przecięcie jest danym rzędem częściowym. Jeśli porządek częściowy ma ograniczony wymiar porządku, to schemat etykietowania sąsiedztwa dla wierzchołków na jego grafie porównywalności można zdefiniować, oznaczając każdy wierzchołek jego pozycją w każdym z definiujących rzędów liniowych i określając, że dwa wierzchołki sąsiadują, jeśli każda odpowiednia para liczb w ich etykietach ma taką samą relację kolejności jak każda inna para. W szczególności pozwala to na schemat etykietowania sąsiedztwa dla wykresów porównywalności akordów , które pochodzą z częściowych rzędów wymiaru co najwyżej czterech.

Hipoteza grafów niejawnych

Nierozwiązany problem z matematyki :

Czy każda wolno rosnąca dziedziczna rodzina grafów ma niejawną reprezentację?

(więcej nierozwiązanych problemów z matematyki)

Nie wszystkie rodziny grafów mają struktury lokalne. W przypadku niektórych rodzin prosty argument zliczania dowodzi, że schematy oznaczania sąsiedztwa nie istnieją: tylko O ​​( n log n ) bitów można użyć do przedstawienia całego grafu, więc reprezentacja tego typu może istnieć tylko wtedy, gdy liczba n -wierzchołków grafów w danej rodzinie F wynosi co najwyżej 2 ^{O ( n log n )} . Rodziny grafów, które mają większą liczbę grafów niż ta, takie jak grafy dwudzielne lub grafy bez trójkątów , nie mają schematów etykietowania sąsiedztwa. Jednak nawet rodziny grafów, w których liczba grafów w rodzinie jest niewielka, mogą nie mieć schematu oznaczania sąsiedztwa; na przykład rodzina grafów z mniejszą liczbą krawędzi niż wierzchołków ma 2 ^{O ( n log n )} n -grafów wierzchołków, ale nie ma schematu etykietowania sąsiedztwa, ponieważ każdy dany graf można przekształcić w większy graf w tej rodzinie, dodając nowy izolowany wierzchołek dla każdej krawędzi, bez zmiany możliwości etykietowania. Kannan i in. zapytał, czy mając zabroniona charakterystyka podgrafów i posiadanie co najwyżej 2 ^{O ( n log n )} n - wierzchołków grafów są razem wystarczające, aby zagwarantować istnienie schematu etykietowania sąsiedztwa; to pytanie, które Spinrad powtórzył jako przypuszczenie, pozostaje otwarte. Wśród rodzin grafów, które spełniają warunki przypuszczenia i dla których nie jest znany schemat etykietowania sąsiedztwa, znajdują się rodzina grafów dyskowych i grafów przecięcia odcinków linii.

Schematy etykietowania i indukowane grafy uniwersalne

Jeśli rodzina grafów F ma schemat oznaczania sąsiedztwa, to grafy n -wierzchołków w F mogą być reprezentowane jako indukowane podgrafy wspólnego indukowanego uniwersalnego grafu wielomianu, graf składający się ze wszystkich możliwych identyfikatorów wierzchołków. I odwrotnie, jeśli można skonstruować indukowany graf uniwersalny tego typu, wówczas tożsamości jego wierzchołków można wykorzystać jako etykiety w schemacie etykietowania sąsiedztwa. W przypadku tego zastosowania niejawnych reprezentacji grafów ważne jest, aby etykiety wykorzystywały jak najmniej bitów, ponieważ liczba bitów w etykietach przekłada się bezpośrednio na liczbę wierzchołków indukowanego grafu uniwersalnego. Alstrup i Rauhe wykazali, że każde drzewo ma schemat etykietowania sąsiedztwa z log ₂ n + O ( log * n ) bitów na etykietę, z czego wynika, że ​​każdy graf z arborycznością k ma schemat z k log ₂ n + O ( log * n ) bitów na etykietę i graf uniwersalny z n ^k 2 ^{O ( log * n )} wierzchołki. W szczególności grafy planarne mają arboryczność co najwyżej trzy, więc mają uniwersalne grafy z prawie sześcienną liczbą wierzchołków. Ta granica została poprawiona przez Gavoille'a i Labourela, którzy wykazali, że grafy planarne i rodziny grafów zamkniętych w mniejszym stopniu mają schemat etykietowania z 2 log ₂ n + O ( log log n ) bitami na etykietę, a grafy o ograniczonej szerokości drzewa mają schemat etykietowania z log ₂ n + O (log log n ) bitów na etykietę. Ograniczenie dla grafów planarnych zostało ponownie ulepszone przez Bonamy'ego, Gavoille'a i Piliczuka, którzy wykazali, że grafy planarne mają schemat etykietowania z (4/3+o(1))log ₂ n bitów na etykietę. Wreszcie Dujmović i in. wykazali, że grafy planarne mają schemat etykietowania z (1+o(1))log ₂ n bitów na etykietę, co daje graf uniwersalny z n ^1+o(1) wierzchołkami.

Unikanie

Hipoteza Aanderaa – Karpa – Rosenberga dotyczy grafów niejawnych podanych jako zbiór oznaczonych wierzchołków z regułą czarnej skrzynki do określania, czy dowolne dwa wierzchołki sąsiadują ze sobą. Ta definicja różni się od schematu etykietowania sąsiedztwa tym, że reguła może być specyficzna dla konkretnego wykresu, a nie być regułą ogólną, która ma zastosowanie do wszystkich wykresów w rodzinie. Z powodu tej różnicy każdy wykres ma niejawną reprezentację. Na przykład regułą może być wyszukiwanie pary wierzchołków w oddzielnej macierzy sąsiedztwa. Jednak algorytm, który otrzymuje jako dane wejściowe graf niejawny tego typu, musi na nim działać tylko poprzez niejawny test sąsiedztwa, bez odniesienia do sposobu implementacji testu.

Właściwość wykresu jest pytaniem, czy graf należy do danej rodziny grafów; odpowiedź musi pozostać niezmienna w przypadku zmiany etykiet wierzchołków. W tym kontekście pytanie, które należy ustalić, brzmi: ile par wierzchołków należy przetestować pod kątem sąsiedztwa, w najgorszym przypadku, zanim można będzie określić, czy interesująca nas właściwość jest prawdziwa, czy fałszywa dla danego niejawnego grafu. Rivest i Vuillemin udowodnili, że każdy algorytm deterministyczny dla dowolnej nietrywialnej właściwości grafu musi testować kwadratową liczbę par wierzchołków. Pełna hipoteza Aanderaa – Karpa – Rosenberga jest taka, że ​​​​każdy algorytm deterministyczny dla właściwości wykresu monotonicznego (takiego, który pozostaje prawdziwy, jeśli do grafu z tą właściwością zostanie dodanych więcej krawędzi) musi w niektórych przypadkach przetestować każdą możliwą parę wierzchołków. Udowodniono, że kilka przypadków przypuszczenia jest prawdziwe - na przykład wiadomo, że jest prawdziwe dla grafów z pierwszą liczbą wierzchołków - ale pełne przypuszczenie pozostaje otwarte. Zbadano również warianty problemu dla algorytmów losowych i algorytmów kwantowych.

Bender i Ron wykazali, że w tym samym modelu użytym do hipotezy unikania, możliwe jest odróżnienie skierowanych grafów acyklicznych od grafów, którym bardzo daleko do acykliczności, tylko w stałym czasie. W przeciwieństwie do tego, tak szybki czas nie jest możliwy w niejawnych modelach grafów opartych na sąsiedztwie,

Zobacz też

• Grupa czarnej skrzynki , niejawny model algorytmów teorii grup
• Matroid wyrocznia , niejawny model algorytmów matroidów