Silna orientacja - Strong orientation
W teorii wykres , A silne ukierunkowanie o nieukierunkowane wykresu jest przypisanie kierunku na każdej krawędzi (e orientacji ), która sprawia, że w silnie połączony wykresie .
Przy projektowaniu sieci dróg jednokierunkowych zastosowano silne orientacje. Zgodnie z twierdzeniem Robbinsa grafy o silnych orientacjach są dokładnie grafami bez mostków . Orientacje Eulera i dobrze wyważone orientacje dostarczają ważnych szczególnych przypadków silnych orientacji; z kolei silne orientacje mogą być uogólnione na całkowicie cykliczne orientacje odłączonych grafów. Zbiór silnych orientacji grafu tworzy częściowy sześcian , przy czym sąsiednie orientacje w tej strukturze różnią się orientacją pojedynczej krawędzi. Możliwe jest znalezienie pojedynczej orientacji w czasie liniowym, ale #P-zupełne obliczanie liczby silnych orientacji danego wykresu.
Aplikacja do kontroli ruchu
Robbins (1939) wprowadza problem silnej orientacji opowieścią o mieście, którego ulice i skrzyżowania reprezentuje dany wykres G . Zgodnie z historią Robbinsa, mieszkańcy miasta chcą mieć możliwość naprawy dowolnego odcinka drogi w dni powszednie, jednocześnie umożliwiając dojazd do dowolnej części miasta z dowolnej innej części, wykorzystując pozostałe drogi jako ulice dwukierunkowe. W weekendy wszystkie drogi są otwarte, ale z powodu dużego natężenia ruchu chcą zmienić wszystkie drogi na ulice jednokierunkowe i ponownie umożliwić dojazd do dowolnej części miasta z dowolnej innej części. Twierdzenie Robbinsa mówi, że system dróg nadaje się do napraw w dni powszednie wtedy i tylko wtedy, gdy nadaje się do konwersji na system jednokierunkowy w weekendy. Z tego powodu jego wynik jest czasami nazywany twierdzeniem o ulicy jednokierunkowej .
Po pracy Robbinsa, w serii artykułów Robertsa i Xu dokładniej modelowano problem przekształcenia siatki dwukierunkowych ulic miejskich w jednokierunkowe i badano wpływ tej konwersji na odległości między parami punktów w siatce. Jak pokazali, tradycyjny układ jednokierunkowy, w którym równoległe ulice zmieniają się w kierunkach, nie jest optymalny, jeśli chodzi o utrzymanie jak najmniejszych odległości w parach. Jednak ulepszone orientacje, które znaleźli, obejmują punkty, w których ruch z dwóch bloków jednokierunkowych spotyka się czołowo, co można uznać za wadę ich rozwiązań.
Powiązane typy orientacji
Jeśli graf nieskierowany ma trasę Eulera , orientację Eulera grafu (orientację, dla której każdy wierzchołek ma stopień wejściowy równy stopniowi zewnętrznemu) można znaleźć, konsekwentnie orientując krawędzie wokół trasy. Te orientacje są automatycznie silnymi orientacjami.
Twierdzenie Nasha-Williamsa ( 1960 , 1969 ) stwierdza, że każdy nieskierowany graf G ma dobrze zrównoważoną orientację . Jest to orientacja z tą właściwością, że dla każdej pary wierzchołków u i v w G , liczba parami rozłącznych ścieżek skierowanych od u do v w otrzymanym grafie skierowanym wynosi co najmniej , gdzie k jest maksymalną liczbą ścieżek w zestawie rozłącznych krawędziowo nieskierowanych ścieżek od u do v . Orientacje Nasha-Williamsa mają również tę właściwość, że są one jak najbardziej zbliżone do orientacji Eulera: w każdym wierzchołku stopień wejściowy i stopień zewnętrzny znajdują się w sobie. Istnienie dobrze zrównoważonych orientacji, wraz z twierdzeniem Mengera , implikuje natychmiast twierdzenie Robbinsa: według twierdzenia Mengera, graf dwukrawędziowy ma co najmniej dwie rozłączne krawędziowe ścieżki między każdą parą wierzchołków, z których wynika, że każdy dobrze wyważona orientacja musi być mocno połączona. Mówiąc bardziej ogólnie, wynik ten implikuje, że każde 2 k grafu nieskierowanego połączonego krawędziowo może być zorientowane tak, aby utworzyć graf skierowany k - krawędziowo.
Całkowicie cykliczny orientacji grafu G ma pozycji, w której każda krawędź należy do skierowanej cyklu. W przypadku połączonych grafów jest to to samo, co silna orientacja, ale całkowicie cykliczne orientacje można również zdefiniować dla grafów rozłączonych i są to orientacje, w których każdy połączony składnik G staje się silnie połączony. Twierdzenie Robbinsa można powtórzyć, mówiąc, że graf ma całkowicie cykliczną orientację wtedy i tylko wtedy, gdy nie ma mostka. Orientacje całkowicie cykliczne są orientacjami dualnymi do orientacji acyklicznych (orientacje, które zamieniają G w skierowany graf acykliczny ) w tym sensie, że jeśli G jest grafem planarnym , a orientacje G są przenoszone do orientacji płaskiego grafu podwójnego G poprzez obrócenie każdej krawędzi 90 stopni zgodnie z ruchem wskazówek zegara, wtedy całkowicie cykliczna orientacja G odpowiada w ten sposób acyklicznej orientacji podwójnego wykresu i odwrotnie. Liczba różnych położeniach całkowicie cyklicznych dowolnego wykresu G jest T G (0,2) , gdzie T G IS wielomianu TUTTE wykresu i podwójnie liczbę alifatycznych orientacji jest T G (2,0) . W konsekwencji twierdzenie Robbinsa implikuje, że wielomian Tutte ma pierwiastek w punkcie (0,2) wtedy i tylko wtedy, gdy graf G ma mostek.
Jeśli silna orientacja ma tę właściwość, że wszystkie skierowane cykle przechodzą przez pojedynczą krawędź st (odpowiednik, jeśli odwrócenie orientacji krawędzi daje orientację acykliczną ), to orientacja acykliczna utworzona przez odwrócenie st jest orientacją bipolarną . Każda orientacja dwubiegunowa jest w ten sposób powiązana z orientacją silną.
Przerzuć wykresy
Jeśli G jest grafem połączonym trzema krawędziami, a X i Y są dowolnymi dwoma różnymi silnymi orientacjami G , to możliwe jest przekształcenie X w Y poprzez zmianę orientacji pojedynczej krawędzi na raz, na każdym kroku zachowując właściwość, że orientacja jest silna. Zatem flipgraph, którego wierzchołki odpowiadają silnym orientacjom G , a krawędzie odpowiadają parom silnych orientacji, które różnią się kierunkiem pojedynczej krawędzi, tworzy częściowy sześcian .
Algorytmy i złożoność
Silną orientację danego bezmostowego grafu nieskierowanego można znaleźć w czasie liniowym , przeprowadzając najpierw przeszukiwanie grafu w głąb, orientując wszystkie krawędzie w drzewie przeszukiwania w głąb najpierw od korzenia drzewa i orientując wszystkie pozostałe krawędzie (co musi koniecznie połączyć przodka i potomka w głębi pierwszego drzewa poszukiwań) od potomka do przodka. Jeśli podany zostanie graf nieskierowany G z mostami, wraz z listą uporządkowanych par wierzchołków, które muszą być połączone ścieżkami skierowanymi, możliwe jest w czasie wielomianowym znalezienie orientacji G, która łączy wszystkie podane pary, jeśli taka orientacja istnieje. Jednak ten sam problem jest NP-zupełny, gdy dane wejściowe mogą być wykresem mieszanym.
Jest # P uzupełniania policzyć silnych orientacji danego grafu G , nawet wtedy, gdy G jest płaska i dwudzielny . Jednak w przypadku grafów gęstych (a dokładniej grafów, w których każdy wierzchołek ma liniową liczbę sąsiadów), liczbę silnych orientacji można oszacować za pomocą schematu aproksymacji losowej w pełni wielomianowej . Problem zliczania silnych orientacji można również rozwiązać dokładnie w czasie wielomianowym dla grafów o ograniczonej szerokości drzewa .
Uwagi
Bibliografia
- Alon, Noga ; Fryz, Alan ; Walijski, Dominic (1995), „Wielomianowy czas randomizowane schematy aproksymacji dla niezmienników Tutte-Gröthendieck: gęsty przypadek”, Struktury losowe i algorytmy , 6 (4): 459-478, doi : 10.1002/rsa.3240060409 , MR 1368847
- Arkin, Esther M .; Hassin, Refael (2002), „Uwaga na temat orientacji wykresów mieszanych” (PDF) , Discrete Applied Mathematics , 116 (3): 271-278, doi : 10.1016/S0166-218X(01)00228-1 , MR 1878572.
- Atallah, Mikhail J. (1984), „Równoległa silna orientacja nieskierowanego wykresu” , Listy przetwarzania informacji , 18 (1): 37-39, doi : 10.1016/0020-0190(84)90072-3 , MR 0742079.
- de Fraysseix, Hubert; Ossona de Mendez, Patrice ; Rosenstiehl, Pierre (1995), "Orientacje bipolarne ponownie", dyskretna matematyka stosowana , 56 (2-3): 157-179, doi : 10.1016/0166-218X (94) 00085-R , MR 1318743.
- Fukuda, Komei ; Prodon, Alain; Sakuma, Tadashi (2001), "Uwagi na temat orientacji acyklicznych i lemat łuskania" , Informatyka teoretyczna , 263 (1-2): 9-16, doi : 10.1016/S0304-3975(00)00226-7 , MR 1846912.
- Koh, KM; Tay, EG (2002), „Optymalne orientacje wykresów i digrafów: ankieta”, Wykresy i kombinatoryka , 18 (4): 745-756, doi : 10.1007/s003730200060 , MR 1964792 , S2CID 34821155.
- Las Vergnas, Michel (1980), "Wypukłość w zorientowanych matroidach", Journal of Combinatorial Theory , Seria B, 29 (2): 231-243, doi : 10.1016/0095-8956 (80) 90082-9 , MR 0586435.
- Nash-Williams, C. St. JA (1960), „O orientacjach, łączności i parzystych wierzchołkach w skończonych wykresach.”, Canadian Journal of Mathematics , 12 : 555-567, doi : 10.4153/cjm-1960-049 -6 , MR 0118684.
- Nash-Williams, C. St. JA (1969), „Dobrze zrównoważone orientacje grafów skończonych i dyskretne parzystości nieparzystych wierzchołków”, „ Recent Progress in Combinatorics” (Proc. Trzecia Konferencja Waterloo na temat kombinatoryki, 1968) , Nowy Jork: Prasa akademicka, s. 133–149, MR 0253933.
- Noy, Marc (2001), „acykliczne i całkowicie cykliczne orientacje na wykresach płaskich”, The American Mathematical Monthly , 108 (1): 66-68, doi : 10.2307/2695680 , JSTOR 2695680 , MR 1857074.
- Robbins, HE (1939), „Twierdzenie o wykresach, z zastosowaniem do problemu kontroli ruchu”, American Mathematical Monthly , 46 (5): 281–283, doi : 10.2307/2303897 , JSTOR 2303897.
- Roberts, Fred S. (1978), „Rozdział 2. Problem ulicy jednokierunkowej ”, Teoria grafów i jej zastosowania w problemach społeczeństwa , CBMS-NSF Regional Conference Series in Applied Mathematics, 29 , Filadelfia, Pensylwania: Society for Matematyka przemysłowa i stosowana (SIAM), s. 7-14, ISBN 9780898710267, MR 0508050.
- Roberts, Fred S.; Xu, Yonghua (1988), „O optymalnych silnie połączonych orientacjach miejskich wykresów ulicznych I. Duże siatki”, SIAM Journal on Discrete Mathematics , 1 (2): 199-222, doi : 10.1137/0401022 , MR 0941351.
- Roberts, Fred S.; Xu, Yonghua (1989), „O optymalnych silnie połączonych orientacjach miejskich wykresów ulicznych. II. Dwie aleje wschód-zachód lub ulice północ-południe”, Networks , 19 (2): 221-233, doi : 10.1002/net. 3230190204 , MR 0984567.
- Roberts, Fred S.; Xu, Yonghua (1992), „O optymalnych silnie połączonych orientacjach miejskich wykresów ulicznych. III. Trzy aleje wschód-zachód lub ulice północ-południe”, Networks , 22 (2): 109–143, doi : 10.1002/net. 3230220202 , MR 1148018.
- Roberts, Fred S.; Xu, Yong Hua (1994), „O optymalnych silnie połączonych orientacjach miejskich wykresów ulicznych IV. Cztery aleje wschód-zachód lub ulice północ-południe”, dyskretna matematyka stosowana , 49 (1-3): 331-356, doi : 10.1016/0166-218X(94)90217-8 , MR 1272496.
- Schrijver, A. (1983), "ograniczenia liczby orientacji Eulera" (PDF) , Combinatorica , 3 (3-4): 375-380, doi : 10.1007/BF02579193 , MR 0729790 , S2CID 13708977.
- Vertigan, DL; Walijski, DJA (1992), „Złożoność obliczeniowa płaszczyzny Tutte: przypadek dwudzielny”, Combinatorics, Probability and Computing , 1 (2): 181-187, doi : 10.1017/S0963548300000195 , MR 1179248.
- Welsh, Dominic (1997), "Liczenie przybliżone", Surveys in Combinatorics, 1997 (Londyn) , London Math. Soc. Lecture Note Ser., 241 , Cambridge: Cambridge Univ. Prasa, s. 287-323, doi : 10.1017/CBO9780511662119.010 , MR 1477750.