Kryterium płaskości Mac Lane'a

W teorii grafów kryterium planarności Mac Lane'a jest charakterystyką grafów planarnych pod względem ich przestrzeni cykli , nazwanej na cześć Saundersa Mac Lane'a , który opublikował je w 1937 r. Stwierdza ono, że skończony graf nieskierowany jest planarny wtedy i tylko wtedy, gdy przestrzeń cykli wykres (wzięty modulo 2) ma podstawę cyklu , w której każda krawędź wykresu uczestniczy w co najwyżej dwóch wektorach bazowych.

Oświadczenie

Dla dowolnego cyklu c na grafie G można utworzyć m -wymiarowy wektor 0-1, który ma 1 w pozycjach współrzędnych odpowiadających krawędziom w c i 0 w pozostałych pozycjach współrzędnych. Przestrzeń cyklu C ( G ) wykresu jest przestrzenią wektorową utworzoną przez wszystkie możliwe kombinacje liniowe wektorów utworzonych w ten sposób. W charakterystyce Mac Lane'a C ( G ) jest przestrzenią wektorową nad polem skończonym GF(2) z dwoma elementami; to znaczy w tej przestrzeni wektorowej wektory są dodawane współrzędnymi modulo dwa. Podstawa 2 G jest bazą C ( G ) z tą właściwością, że dla każdej krawędzi e w G co najwyżej dwa wektory bazowe mają niezerowe współrzędne w pozycji odpowiadającej e . Następnie, stwierdzając bardziej formalnie, charakterystyka Mac Lane'a polega na tym, że grafy planarne są dokładnie grafami, które mają podstawę 2.

Istnienie bazy 2 dla grafów planarnych

Jeden kierunek charakteryzacji stwierdza, że ​​każdy graf planarny ma podstawę 2. Taką bazę można znaleźć jako zbiór granic ścian ograniczonych płaskiego osadzania danego grafu G .

Jeśli krawędź jest mostem G , pojawia się dwukrotnie na granicy pojedynczej ściany i dlatego ma zerową współrzędną w odpowiednim wektorze. Zatem jedyne krawędzie, które mają niezerowe współrzędne, to te, które oddzielają dwie różne ściany; krawędzie te pojawiają się raz (jeśli jedna ze ścian jest nieograniczona) lub dwa razy w zbiorze granic ścian ograniczonych. Pozostaje udowodnić, że cykle te tworzą podstawę. Jednym ze sposobów udowodnienia tego przez indukcję. W przypadku podstawowym G jest drzewem, więc nie ma ścian ograniczonych i C ( G ) jest zerowymiarowa i ma pustą bazę. W przeciwnym razie usunięcie krawędzi z nieograniczonej ściany G zmniejsza zarówno wymiar przestrzeni cyklu, jak i liczbę ograniczonych ścian o jeden i następuje indukcja.

Alternatywnie, można użyć wzoru Eulera , aby pokazać, że liczba cykli w tym zbiorze jest równa randze obwodu G , który jest wymiarem przestrzeni cykli. Każdy niepusty podzbiór cykli ma sumę wektorów, która reprezentuje granicę sumy ścian ograniczonych w podzbiorze, która nie może być pusta (suma zawiera co najmniej jedną ścianę ograniczoną i wyklucza ścianę nieograniczoną, więc muszą istnieć jakieś krawędzie oddzielające ich). Dlatego nie ma podzbioru cykli, których wektory sumują się do zera, co oznacza, że ​​wszystkie cykle są liniowo niezależne . Jako liniowo niezależny zbiór o takim samym rozmiarze jak wymiar przestrzeni, ten zbiór cykli musi stanowić podstawę.

Konieczność planarności, gdy istnieje podstawa 2

O'Neil (1973) dostarczył następującego prostego argumentu przemawiającego za innym kierunkiem charakteryzacji, opartego na twierdzeniu Wagnera charakteryzującym grafy planarne za pomocą zabronionych drugorzędnych . Jak zauważa O'Neill, właściwość posiadania podstawy 2 jest zachowana w przypadku mniejszych grafów : jeśli skróci się krawędź, to samo skrócenie można wykonać w wektorach bazowych, jeśli usunie się krawędź, która ma niezerową współrzędną w jednym wektor bazowy, to ten wektor można usunąć z bazy, a jeśli usunie się krawędź, która ma niezerową współrzędną w dwóch wektorach bazowych, to te dwa wektory można zastąpić ich sumą (modulo dwa). Dodatkowo jeśli C ( G ) jest bazą cykliczną dla dowolnego grafu, to musi on pokryć pewne krawędzie dokładnie raz, bo inaczej jego suma byłaby równa zeru (niemożliwe dla bazy), więc C ( G ) można powiększyć o jeszcze jeden cykl składający się z te pojedynczo pokryte krawędzie z zachowaniem właściwości polegającej na tym, że każda krawędź jest pokryta co najwyżej dwa razy. Jednak pełny graf K ₅ nie ma podstawy 2: C ( G ) jest sześciowymiarowy, każdy nietrywialny wektor w C ( G ) ma niezerowe współrzędne dla co najmniej trzech krawędzi, więc każda rozszerzona baza miałaby co najmniej 21 niezerowych, przekraczając 20 niezerowych, które byłyby dozwolone, gdyby każda z dziesięciu krawędzi była różna od zera w co najwyżej dwóch wektorach bazowych. Na podstawie podobnego rozumowania pełny graf dwudzielny K _3,3 nie ma podstawy 2: C ( G ) jest czterowymiarowy, a każdy nietrywialny wektor w C ( G ) ma niezerowe współrzędne dla co najmniej czterech krawędzi, więc każda rozszerzona baza miałaby co najmniej 20 wartości niezerowych, przekraczając 18 wartości niezerowych, które byłyby dozwolone, gdyby każda z dziewięciu krawędzi była różna od zera w co najwyżej dwóch wektorach bazowych. Ponieważ właściwość posiadania podstawy 2 jest domknięta na drobne i nie jest prawdziwa dla dwóch mniejszych i minimalnych grafów niepłaskich K ₅ i K _3,3 , nie jest również prawdziwa dla żadnego innego grafu nieplanarnego.

Lefschetz (1965) dostarczył innego dowodu, opartego na topologii algebraicznej . Używa nieco innego sformułowania kryterium planarności, zgodnie z którym graf jest planarny wtedy i tylko wtedy, gdy ma zbiór (niekoniecznie prostych) cykli pokrywających każdą krawędź dokładnie dwa razy, tak że jedyna nietrywialna relacja między tymi cyklami w C ( G ) jest to, że ich suma wynosi zero. Jeśli tak jest, to pominięcie któregokolwiek z cykli daje podstawę spełniającą sformułowanie kryterium Mac Lane'a. Jeśli graf planarny jest osadzony na kuli, jego cykle twarzy wyraźnie spełniają właściwość Lefschetza. I odwrotnie, jak pokazuje Lefschetz, ilekroć wykres G ma zestaw cykli o tej właściwości, z konieczności tworzą one cykle twarzy osadzenia wykresu na kuli.

Aplikacja

Ja'Ja' i Simon (1982) wykorzystali kryterium planarności Mac Lane'a jako część algorytmu równoległego do testowania planarności grafów i znajdowania płaskich osadzeń. Ich algorytm dzieli graf na trójpołączone składowe , po czym następuje unikalne płaskie osadzenie (do wyboru zewnętrznej powierzchni) i można założyć, że cykle w podstawie 2 są wszystkimi cyklami peryferyjnymi grafu . Ja'Ja' i Simon zaczynają od podstawowej podstawy cyklu wykresu (podstawa cyklu wygenerowana z drzewa rozpinającego tworząc cykl dla każdej możliwej kombinacji ścieżki w drzewie i krawędzi na zewnątrz drzewa) i przekształcić go w 2-podstawowe cykle peryferyjne. Cykle te tworzą ściany płaskiego osadzania danego grafu.

Kryterium planarności Mac Lane'a pozwala łatwo policzyć liczbę cykli ścian ograniczonych na grafie planarnym, jako rangę obwodu wykresu. Ta właściwość jest używana do definiowania współczynnika zazębienia wykresu, znormalizowanego wariantu liczby cykli ścian ograniczonych, który jest obliczany przez podzielenie rzędu obwodu przez 2 n - 5 , maksymalną możliwą liczbę ścian ograniczonych grafu planarnego z ten sam zestaw wierzchołków ( Buhl i in. 2004 ).

•   Buhl, J.; Gautrais, J.; Podeszwa, RV; Kuntz, P.; Valverde, S.; Deneubourg, JL; Theraulaz, G. (2004), „Wydajność i solidność w sieciach mrówek galerii”, The European Physical Journal B , Springer-Verlag, 42 (1): 123–129, Bibcode : 2004 EPJB… 42..123B , doi : 10.1140/epjb/e2004-00364-9 , S2CID 14975826 .
•   Ja'Ja', Józef; Simon, Janos (1982), „Algorytmy równoległe w teorii grafów: testowanie planarności”, SIAM Journal on Computing , 11 (2): 314–328, doi : 10.1137/0211024 , MR 0652905 .
•      Lefschetz, Solomon (1965), „Wykresy planarne i tematy pokrewne”, Proceedings of the National Academy of Sciences of the United States of America , 54 (6): 1763–1765, Bibcode : 1965PNAS… 54.1763L , doi : 10,1073 /pnas.54.6.1763 , JSTOR 72818 , MR 0189011 , PMC 300546 , PMID 16591326 .
• Mac Lane, S. (1937), „Warunek kombinatoryczny dla grafów planarnych” (PDF) , Fundamenta Mathematicae , 28 : 22–32, doi : 10,4064 / fm-28-1-22-32 .
•    O'Neil, PV (1973), „Krótki dowód twierdzenia o planarności Mac Lane'a”, Proceedings of the American Mathematical Society , 37 (2): 617–618, doi : 10.1090 / S0002-9939-1973-0313098-X , hdl : 2060/19720020939 , JSTOR 2039496 , MR 0313098 .