Wykres skośno-symetryczny

Rodziny grafów zdefiniowane przez ich automorfizmy
przechodnie na odległość	→	odległość regularna	←	mocno regularny
↓
symetryczny (przechodni łuku)	←	t -przechodnia, t ≥ 2		skośno-symetryczny
↓
(jeśli jest połączony) wierzchołki i krawędzie przechodnie	→	przechodnie krawędziowe i regularne	→	przechodnie krawędziowe
↓		↓		↓
przechodnie wierzchołków	→	regularny	→	(jeśli dwustronny) dwuregularny
↑
Wykres Cayleya	←	zero-symetryczny		asymetryczny

W teorii grafów , gałęzi matematyki, wykres skośno-symetryczny jest skierowanym wykresem , który jest izomorficzny z własnym wykresem transpozycji , wykresem utworzonym przez odwrócenie wszystkich jego krawędzi, pod izomorfizmem, który jest inwolucją bez żadnych punktów stałych . Wykresy skośno-symetryczne są identyczne z wykresami podwójnego pokrywania grafów dwukierunkowych .

Grafy skośno-symetryczne zostały po raz pierwszy wprowadzone pod nazwą digrafów antysymetrycznych przez Tutte'a (1967) , później jako grafy podwójnego pokrywania grafów biegunowych przez Zelinkę (1976b) , a jeszcze później jako grafy podwójnego pokrywania grafów dwukierunkowych przez Zaslavsky'ego (1991) . Powstają przy modelowaniu poszukiwania naprzemiennych ścieżek i naprzemiennych cykli w algorytmach znajdowania dopasowań w grafach, przy testowaniu, czy wzór martwej natury w Grze w życie Conwaya można podzielić na prostsze komponenty, w rysowanie wykresów , oraz w wykresach implikacji wykorzystywanych do efektywnego rozwiązania problemu spełnialności 2 .

Definicja

Jak zdefiniowali np. Goldberg i Karzanov (1996) , skośno-symetryczny graf G jest grafem skierowanym wraz z funkcją σ odwzorowującą wierzchołki G na inne wierzchołki G , spełniającą następujące własności:

1. Dla każdego wierzchołka v , σ( v ) ≠ v ,
2. Dla każdego wierzchołka v σ(σ( v )) = v ,
3. Dla każdej krawędzi ( u , v ), (σ ( v ), σ ( u )) również musi być krawędzią.

Można użyć trzeciej właściwości, aby rozszerzyć σ do funkcji odwracającej orientację na krawędziach G .

Wykres transpozycji G jest wykresem utworzonym przez odwrócenie każdej krawędzi G , a σ definiuje izomorfizm grafu od G do jego transpozycji. Jednak w grafie skośno-symetrycznym dodatkowo wymagane jest, aby izomorfizm łączył każdy wierzchołek z innym wierzchołkiem, zamiast pozwalać na mapowanie wierzchołka na siebie przez izomorfizm lub grupowanie więcej niż dwóch wierzchołków w cyklu izomorfizmu.

Mówimy, że ścieżka lub cykl w grafie skośno-symetrycznym jest regularna , jeśli dla każdego wierzchołka v ścieżki lub cyklu odpowiedni wierzchołek σ( v ) nie jest częścią ścieżki lub cyklu.

Przykłady

Każdy skierowany wykres ścieżkowy z parzystą liczbą wierzchołków jest skośno-symetryczny poprzez symetrię, która zamienia dwa końce ścieżki. Jednak wykresy ścieżek z nieparzystą liczbą wierzchołków nie są skośno-symetryczne, ponieważ symetria tych wykresów polegająca na odwróceniu orientacji odwzorowuje środkowy wierzchołek ścieżki na siebie, co jest niedozwolone w przypadku wykresów skośno-symetrycznych.

Podobnie skierowany wykres cyklu jest skośno-symetryczny wtedy i tylko wtedy, gdy ma parzystą liczbę wierzchołków. W tym przypadku liczba różnych odwzorowań σ realizujących skośną symetrię grafu jest równa połowie długości cyklu.

Wykresy biegunowe/przełączeniowe, wykresy podwójnego pokrycia i wykresy dwukierunkowe

Graf skośno-symetryczny można równoważnie zdefiniować jako podwójny wykres pokrywający wykresu biegunowego lub wykresu przełączającego , który jest grafem nieskierowanym, w którym krawędzie padające na każdy wierzchołek są podzielone na dwa podzbiory. Każdy wierzchołek wykresu biegunowego odpowiada dwóm wierzchołkom wykresu skośno-symetrycznego, a każda krawędź wykresu biegunowego odpowiada dwóm krawędziom wykresu skośno-symetrycznego. Ta równoważność jest używana przez Goldberga i Karzanov (1996) modelować problemy dopasowywania w kategoriach grafów skośno-symetrycznych; w tej aplikacji dwa podzbiory krawędzi w każdym wierzchołku to krawędzie niedopasowane i krawędzie dopasowane. Zelinka (za F. Zitek) i Cook wizualizują wierzchołki wykresu biegunowego jako punkty, w których spotykają się liczne tory toru kolejowego : jeśli pociąg wjeżdża na zwrotnicę po torze nadjeżdżającym z jednego kierunku, musi wyjechać torem w innym kierunku. Problem znalezienia nie przecinających się gładkich krzywych między zadanymi punktami na torze kolejowym pojawia się przy testowaniu, czy pewne rodzaje rysunków wykresów są ważne. i może być modelowany jako poszukiwanie regularnej ścieżki w grafie skośno-symetrycznym.

Ściśle powiązaną koncepcją jest wykres dwukierunkowy lub wykres spolaryzowany , wykres, w którym każdy z dwóch końców każdej krawędzi może być orłem lub ogonem, niezależnie od drugiego końca. Wykres dwukierunkowy można interpretować jako wykres biegunowy, pozwalając na określenie podziału krawędzi w każdym wierzchołku przez podział punktów końcowych w tym wierzchołku na głowy i ogony; jednakże zamiana ról orłów i reszek w jednym wierzchołku („zamiana” wierzchołka) daje inny wykres dwukierunkowy, ale ten sam wykres biegunowy.

₀ Aby utworzyć graf podwójnego pokrycia (tj. odpowiedni wykres skośno-symetryczny) z wykresu biegunowego G , utwórz dla każdego wierzchołka v z G dwa wierzchołki v i v ₁ , i niech σ( v _i ) = v _{1 − i} . Dla każdej krawędzi e = ( u , v ) z G utwórz dwie skierowane krawędzie w grafie pokrywającym, jedną zorientowaną od u do v i jedną zorientowaną od v ₀₀₀₀ do ciebie _ Jeśli e jest w pierwszym podzbiorze krawędzi w punkcie v , te dwie krawędzie są od u do v i od v ₁ do u ₁ , natomiast jeśli e jest w drugim podzbiorze, krawędzie są od u do v ₁ i od v do u ₁ . W przeciwnym kierunku, biorąc pod uwagę wykres skośno-symetryczny G , można utworzyć graf biegunowy, który ma jeden wierzchołek dla każdej odpowiedniej pary wierzchołków w G i jedną krawędź nieskierowaną dla każdej odpowiedniej pary krawędzi w G . Nieskierowane krawędzie w każdym wierzchołku wykresu biegunowego można podzielić na dwa podzbiory zgodnie z tym, z którego wierzchołka wykresu biegunowego wychodzą i do którego wchodzą.

Regularna ścieżka lub cykl grafu skośno-symetrycznego odpowiada ścieżce lub cyklowi w grafie biegunowym, który wykorzystuje co najwyżej jedną krawędź z każdego podzbioru krawędzi w każdym ze swoich wierzchołków.

Dopasowanie

Podczas konstruowania dopasowań w grafach nieskierowanych ważne jest znalezienie naprzemiennych ścieżek , ścieżek wierzchołków zaczynających się i kończących na niedopasowanych wierzchołkach, w których krawędzie w nieparzystych pozycjach na ścieżce nie są częścią danego dopasowania częściowego i w których krawędzie w nawet pozycje na ścieżce są częścią dopasowania. Usuwając dopasowane krawędzie takiej ścieżki z dopasowania i dodając niedopasowane krawędzie, można zwiększyć rozmiar dopasowania. Podobnie, cykle, w których występują naprzemiennie dopasowane i niedopasowane krawędzie, mają znaczenie w problemach z dopasowywaniem ważonym. Naprzemienna ścieżka lub cykl na grafie nieskierowanym może być modelowana jako regularna ścieżka lub cykl na skośno-symetrycznym grafie skierowanym. Tworzenie grafu skośno-symetrycznego z grafu nieskierowanego G z określonym pasującym M , zobacz G jako graf przełączający, w którym krawędzie w każdym wierzchołku są podzielone na dopasowane i niedopasowane krawędzie; naprzemienna ścieżka w G jest wtedy regularną ścieżką na tym wykresie przełączania, a naprzemienny cykl w G jest regularnym cyklem na wykresie przełączania.

Goldberg i Karzanov (1996) uogólnili algorytmy ścieżki przemiennej, aby pokazać, że istnienie regularnej ścieżki między dowolnymi dwoma wierzchołkami grafu skośno-symetrycznego można przetestować w czasie liniowym. Mając dodatkowo nieujemną funkcję długości na krawędziach grafu, która przypisuje tę samą długość dowolnej krawędzi e i σ( e ), najkrótsza regularna ścieżka łącząca daną parę węzłów w grafie skośno-symetrycznym o m krawędziach i n wierzchołków można przetestować w czasie O( m log n ). Jeśli funkcja długości może mieć długości ujemne, istnienie ujemnego cyklu regularnego można przetestować w czasie wielomianowym.

Oprócz problemów ze ścieżkami pojawiających się w dopasowywaniach, zbadano również skośno-symetryczne uogólnienia twierdzenia o maksymalnym przepływie i minimalnym cięciu .

Teoria martwej natury

Cook (2003) pokazuje, że wzór martwej natury w Game of Life Conwaya można podzielić na dwie mniejsze martwe natury wtedy i tylko wtedy, gdy powiązany wykres zmian zawiera regularny cykl. Jak pokazuje, w przypadku grafów przełączanych z co najwyżej trzema krawędziami na wierzchołek można to przetestować w czasie wielomianowym, wielokrotnie usuwając mostki (krawędzie, których usunięcie powoduje rozłączenie grafu) i wierzchołki, w których wszystkie krawędzie należą do jednej partycji, aż nie więcej takie uproszczenia mogą być wykonane. Jeśli wynikiem jest pusty wykres , nie ma regularnego cyklu; w przeciwnym razie regularny cykl można znaleźć w każdym pozostałym elemencie bezmostkowym. Wielokrotne poszukiwanie mostów w tym algorytmie może być skutecznie przeprowadzone przy użyciu dynamicznego algorytmu grafowego Thorupa (2000) .

Podobne techniki usuwania mostków w kontekście dopasowywania rozważali wcześniej Gabow, Kaplan i Tarjan (1999) .

Satysfakcja

Wykres implikacji . Jego skośną symetrię można zrealizować, obracając wykres o kąt 180 stopni i odwracając wszystkie krawędzie.

Przykład problemu spełnialności 2 , to znaczy wyrażenie boolowskie w koniunkcyjnej postaci normalnej z dwiema zmiennymi lub negacjami zmiennych na klauzulę, można przekształcić w wykres implikacji , zastępując każdą klauzulę ${\ Displaystyle \ scriptstyle u \ lor v}$ przez dwie implikacje ${\ Displaystyle \ scriptstyle (\ lnot u) \ Strzałka w prawo v}$ i ${\ Displaystyle \ scriptstyle (\ lnot v) \ Strzałka w prawo u}$ . Ten wykres ma wierzchołek dla każdej zmiennej lub zmiennej zanegowanej oraz skierowaną krawędź dla każdej implikacji; jest z założenia skośno-symetryczny, z korespondencją σ, która odwzorowuje każdą zmienną na jej negację. Jak Aspvall, Plass i Tarjan (1979) , satysfakcjonujące przypisanie do instancji 2-spełnialności jest równoważne podzieleniu tego grafu implikacji na dwa podzbiory wierzchołków, S i σ( S ), tak że żadna krawędź nie zaczyna się w S i kończy się na σ( S ). Jeśli taki podział istnieje, satysfakcjonujące przypisanie można utworzyć, przypisując wartość prawdziwą każdej zmiennej w S i wartość fałszywą każdej zmiennej w σ( S ). Można to zrobić wtedy i tylko wtedy, gdy żadna silnie spójna składowa grafu nie zawiera jednocześnie jakiegoś wierzchołka v i jego komplementarnego wierzchołka σ( v ). Jeśli dwa wierzchołki należą do tego samego silnie połączonego komponentu, odpowiednie zmienne lub zanegowane zmienne są ograniczone, aby były sobie równe w dowolnym satysfakcjonującym przypisaniu instancji spełnialności 2. Całkowity czas testowania silnej łączności i znajdowania partycji grafu implikacji jest liniowy w rozmiarze danego wyrażenia 2-CNF.

Uznanie

jest NP- zupełne , na podstawie wyniku Lalonde (1981), że znalezienie inwolucji odwracającej kolor w grafie dwudzielnym jest NP-zupełne . Taka inwolucja istnieje wtedy i tylko wtedy, gdy graf skierowany jest określony przez orientację każda krawędź z jednej klasy kolorów do drugiej jest skośno-symetryczna, więc testowanie skośno-symetrycznej tego ukierunkowanego wykresu jest trudne. Ta złożoność nie wpływa na algorytmy znajdowania ścieżek dla grafów skośno-symetrycznych, ponieważ algorytmy te zakładają, że struktura skośno-symetryczna jest podawana jako część danych wejściowych algorytmu, a nie wymaga wywnioskowania jej z samego wykresu.

Notatki

• Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E. (1979), „Algorytm czasu liniowego do testowania prawdziwości określonych ilościowo formuł boolowskich”, Information Processing Letters , 8 (3): 121–123, doi : 10.1016/0020-0190 (79) 90002 -4 .
•   Babenko, Maxim A. (2006), „Acykliczne wykresy dwukierunkowe i skośno-symetryczne: algorytmy i struktura”, Informatyka - teoria i zastosowania , Notatki z wykładów z informatyki, tom. 3967, Springer-Verlag, s. 23–34, arXiv : math/0607547 , doi : 10.1007/11753728_6 , ISBN 978-3-540-34166-6 .
• Biggs, Norman (1974), Algebraic Graph Theory , Londyn: Cambridge University Press .
• Cook, Matthew (2003), „Teoria martwej natury”, Nowe konstrukcje w automatach komórkowych , Santa Fe Institute Studies in the Sciences of Complexity , Oxford University Press, s. 93–118 .
• Edmonds, Jack ; Johnson, Ellis L. (1970), „Dopasowywanie: dobrze rozwiązana klasa programów liniowych”, Struktury kombinatoryczne i ich zastosowania: Proceedings of the Calgary Symposium , czerwiec 1969 , Nowy Jork: Gordon and Breach . Przedrukowano w Optymalizacja kombinatoryczna — Eureka, kurczysz się! , Springer-Verlag, Lecture Notes in Computer Science 2570, 2003, s. 27–30, doi : 10.1007/3-540-36478-1_3 .
•   Gabow, Harold N .; Kaplan, Haim; Tarjan, Robert E. (1999), „Unikalne algorytmy maksymalnego dopasowania”, Proc. 31. Symp. ACM. Teoria informatyki (STOC) , s. 70–78, doi : 10.1145/301250.301273 , ISBN 1-58113-067-8 .
• Goldberg, Andrew V .; Karzanov, Alexander V. (1996), „Problemy ze ścieżkami w grafach skośno-symetrycznych”, Combinatorica , 16 (3): 353–382, doi : 10.1007 / BF01261321 .
• Goldberg, Andrew V .; Karzanov, Alexander V. (2004), „Maksymalne skośno-symetryczne przepływy i dopasowania”, Programowanie matematyczne , 100 (3): 537–568, arXiv : math / 0304290 , doi : 10.1007 / s10107-004-0505-z .
• Hui, Piotr; Schaefer, Marcus; Štefankovič, Daniel (2004), „Tory kolejowe i rysunki zbiegu”, Proc. 12. Int. Symp. Rysowanie wykresów , notatki z wykładów z informatyki, tom. 3383, Springer-Verlag, s. 318–328 .
•   Lalonde, François (1981), „Le problem d'étoiles pour graphes est NP-complet”, Discrete Mathematics , 33 (3): 271–280, doi : 10.1016/0012-365X (81) 90271-5 , MR 0602044 .
•   Thorup, Mikkel (2000), „Niemal optymalna, w pełni dynamiczna łączność grafów”, Proc. 32. Sympozjum ACM na temat teorii informatyki , s. 343–350, doi : 10.1145/335305.335345 , ISBN 1-58113-184-4 .
• Tutte, WT (1967), „Dwuznaki antysymetryczne”, Canadian Journal of Mathematics , 19 : 1101–1117, doi : 10.4153/CJM-1967-101-8 .
• Zaslavsky, Thomas (1982), „Podpisane wykresy”, Discrete Applied Mathematics , 4 : 47–74, doi : 10.1016/0166-218X (82) 90033-6 , hdl : 10338.dmlcz/127957 .
• Zaslavsky, Thomas (1991), „Orientacja grafów podpisanych”, European Journal of Combinatorics , 12 (4): 361–375, doi : 10.1016 / s0195-6698 (13) 80118-7 .
• Zelinka, Bohdan (1974), „Wykresy biegunowe i ruch kolejowy”, Aplikace Matematiky , 19 : 169–176 .
• Zelinka, Bohdan (1976a), „Izomorfizmy grafów polarnych i spolaryzowanych”, Czechoslovak Mathematical Journal , 26 : 339–351 .
• Zelinka, Bohdan (1976b), „Analoga twierdzenia Mengera dla wykresów polarnych i spolaryzowanych”, Czechoslovak Mathematical Journal , 26 : 352–360 .