Twierdzenie Fáry'ego

W matematycznej dziedzinie teorii grafów twierdzenie Fáry'ego stwierdza, że każdy prosty , planarny wykres można narysować bez przecięć, tak aby jego krawędzie były odcinkami linii prostych . Oznacza to, że możliwość rysowania krawędzi wykresu jako krzywych zamiast odcinków linii prostych nie pozwala na rysowanie większej klasy wykresów. Twierdzenie nosi imię Istvána Fáry'ego , chociaż zostało udowodnione niezależnie przez Klausa Wagnera ( 1936 ), Fáry'ego ( 1948 ) i Shermana K. Steina ( 1951 ).

Dowód

Krok indukcyjny dla dowodu twierdzenia Fáry'ego.

Jednym ze sposobów udowodnienia twierdzenia Fáry'ego jest użycie indukcji matematycznej . Niech $G$ będzie prostym grafem płaskim z $n$ wierzchołkami; w razie potrzeby możemy dodać krawędzie, aby $G$ był maksymalnie płaskim wykresem. Jeśli $n$ < 3, wynik jest trywialny. Jeśli $n$ ≥ 3, to wszystkie ściany $G$ muszą być trójkątami, ponieważ moglibyśmy dodać krawędź do dowolnej ściany o większej liczbie boków, zachowując jednocześnie planarność, co jest sprzeczne z założeniem o maksymalnej planarności. Wybierz trzy wierzchołki $a, b, c$ tworzące trójkątną ścianę $G$ . Udowodnimy przez indukcję względem $n$ , że istnieje proste kombinatorycznie izomorficzne ponowne osadzenie $G$ , w którym trójkąt $abc$ jest zewnętrzną ścianą osadzenia. ( Izomorficzny kombinatorycznie oznacza, że wierzchołki, krawędzie i ściany na nowym rysunku mogą odpowiadać wierzchołkom na starym rysunku, tak że zachowane są wszystkie instancje między krawędziami, wierzchołkami i ścianami — nie tylko między wierzchołkami i krawędziami. ) W przypadku podstawowym wynik jest trywialny, gdy $n = 3$ i $a$ , $b$ i $c$ są jedynymi wierzchołkami w $G$ . Możemy więc założyć, że $n$ ≥ 4.

Zgodnie ze wzorem Eulera dla grafów planarnych $G$ ma $3 n - 6$ krawędzi; równoważnie, jeśli zdefiniujemy niedobór wierzchołka $v$ w $G$ na $6 - deg (v)$ , suma braków wynosi $12$ . Ponieważ $G$ ma co najmniej cztery wierzchołki, a wszystkie ściany $G$ są trójkątami, wynika z tego, że każdy wierzchołek w $G$ ma stopień co najmniej trzy. Dlatego każdy wierzchołek w $G$ ma co najwyżej trzy niedobory, więc są co najmniej cztery wierzchołki z dodatnim niedoborem. W szczególności możemy wybrać wierzchołek $v$ z co najwyżej pięcioma sąsiadami, który różni się od $a$ , $b$ i $c$ . Niech $G'$ zostanie utworzone przez usunięcie $v$ z $G$ i ponowne trójkątowanie ściany $f$ utworzonej przez usunięcie $v$ . Przez indukcję $G'$ ma kombinatorycznie izomorficzną linię prostą, w której $abc$ jest zewnętrzną ścianą. Ponieważ ponowne osadzenie $G'$ było kombinatorycznie izomorficzne z $G'$ , usunięcie z niego krawędzi, które zostały dodane w celu utworzenia $G'$ pozostawia powierzchnię $f$ , która jest teraz wielokątem $P$ z co najwyżej pięcioma bokami. Aby uzupełnić rysunek do prostego kombinatorycznie izomorficznego ponownego osadzania $G$ , $v$ należy umieścić w wielokącie i połączyć liniami prostymi z wierzchołkami wielokąta. Zgodnie z twierdzeniem o galerii sztuki istnieje punkt wewnętrzny $P$ , w którym można umieścić $v$ tak, że krawędzie od $v$ do wierzchołków $P$ nie przecinają żadnych innych krawędzi, co kończy dowód.

Krok indukcyjny tego dowodu jest przedstawiony po prawej stronie.

Powiązane wyniki

De Fraysseix, Pach i Pollack pokazali, jak znaleźć w czasie liniowym rysunek linii prostej w siatce o wymiarach liniowych w rozmiarze wykresu, dając uniwersalny zbiór punktów o rozmiarze kwadratowym. Podobną metodę zastosował Schnyder, aby udowodnić wzmocnione granice i charakterystykę planarności w oparciu o częściowy porządek padania. Jego praca podkreślała istnienie szczególnego podziału krawędzi maksymalnego grafu planarnego na trzy drzewa znane jako drewno Schnydera .

Twierdzenie Tutte'a o sprężystości głosi, że każdy 3-spójny graf planarny można narysować na płaszczyźnie bez przecięć, tak aby jego krawędzie były odcinkami linii prostych, a ściana zewnętrzna była wielokątem wypukłym (Tutte 1963). Nazywa się to tak, ponieważ takie osadzenie można znaleźć jako położenie równowagi dla układu sprężyn reprezentujących krawędzie wykresu.

Twierdzenie Steinitza mówi, że każdy 3-połączony graf planarny można przedstawić jako krawędzie wypukłego wielościanu w przestrzeni trójwymiarowej. Osadzanie w $płaszczyznę$ prostej typu opisanego przez twierdzenie Tutte'a można utworzyć przez rzutowanie takiej wielościennej reprezentacji na

Twierdzenie o pakowaniu okręgów stwierdza, że każdy wykres planarny może być przedstawiony jako wykres przecięcia zbioru nie przecinających się okręgów na płaszczyźnie. Umieszczenie każdego wierzchołka wykresu w środku odpowiedniego okręgu prowadzi do reprezentacji linii prostej.

Nierozwiązany problem z matematyki :

Czy każdy graf planarny ma reprezentację w postaci linii prostej, w której wszystkie długości krawędzi są liczbami całkowitymi?

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

Heiko Harborth zadał pytanie, czy każdy graf planarny ma prostą reprezentację, w której wszystkie długości krawędzi są liczbami całkowitymi. Prawdziwość hipotezy Harbortha pozostaje nieznana od 2014 r. Jednak wiadomo, że dla grafów sześciennych istnieją osadzenia linii prostych na odległość całkowitą .

Sachs (1983) postawił pytanie, czy każdy graf z osadzeniem bez powiązań w trójwymiarowej przestrzeni euklidesowej ma osadzanie bez powiązań, w którym wszystkie krawędzie są reprezentowane przez odcinki linii prostych, analogicznie do twierdzenia Fáry'ego dla osadzeń dwuwymiarowych.

Zobacz też

Minimalizacja zgięć

Notatki

Fáry, István (1948), „O reprezentacji grafów planarnych w linii prostej”, Acta Sci. Matematyka (Szeged) , 11 : 229-233, MR 0026311 .
de Fraysseix, Hubert; Pach, János ; Pollack, Richard (1988), „Małe zestawy wspierające osadzanie grafów planarnych Fary'ego” , Twentieth Annual ACM Symposium on Theory of Computing , s. 426–433, doi : 10.1145/62212.62254 , ISBN 0-89791-264-0 , S2CID 15230919 .
de Fraysseix, Hubert; Pach, János ; Pollack, Richard (1990), „Jak narysować wykres planarny na siatce”, Combinatorica , 10 : 41–51, doi : 10.1007/BF02122694 , MR 1075065 , S2CID 6861762 .
Geelen, Jim ; Guo, Anjie; McKinnon, David (2008), „Osadzanie linii prostych sześciennych grafów planarnych o całkowitych długościach krawędzi” (PDF) , Journal of Graph Theory , 58 (3): 270–274, doi : 10.1002 / jgt.20304 .
Harborth, H.; Kemnitz, A.; Moller, M.; Sussenbach, A. (1987), "Ganzzahlige planare Darstellungen der platonischen Korper", Elem. Matematyka , 42 : 118–122 .
Kemnitz, A.; Harborth, H. (2001), „Plane całkowe rysunki grafów planarnych”, Discrete Mathematics , 236 (1–3): 191–195, doi : 10.1016 / S0012-365X (00) 00442-8 .
Mohar, Bojan (2003), Problemy z książki Graphs on Surfaces .
Mohar, Bojan ; Thomassen, Carsten (2001), Wykresy na powierzchniach , Johns Hopkins University Press, s. Roblem 2.8.15, ISBN 0-8018-6689-8 .
Sachs, Horst (1983), "O przestrzennej analogii twierdzenia Kuratowskiego o grafach planarnych - problem otwarty", w: M. Horowiecki; Kennedy'ego, JW; Sysło MM (red.), Graph Theory: Proceedings of a Conference odbyła się w Łagowie, Polska, 10-13 lutego 1981 , Lecture Notes in Mathematics, tom. 1018, Springer-Verlag, s. 230–241, doi : 10.1007/BFb0071633 , ISBN 978-3-540-12687-4 .
Schnyder, Walter (1990), „Osadzanie grafów planarnych na siatce” , Proc. 1. sympozjum ACM / SIAM na temat algorytmów dyskretnych (SODA) , s. 138–148, ISBN 9780898712513 .
Stein, SK (1951), „Mapy wypukłe”, Proceedings of the American Mathematical Society , 2 (3): 464–466, doi : 10.2307/2031777 , JSTOR 2031777 , MR 0041425 .
Tutte, WT (1963), „Jak narysować wykres”, Proceedings of the London Mathematical Society , 13 : 743–767, doi : 10.1112/plms/s3-13.1.743 , MR 0158387 .
Wagner, Klaus (1936), „Bemerkungen zum Vierfarbenproblem” , Jahresbericht der Deutschen Mathematiker-Vereinigung , 46 : 26–32 .