Wykres toroidalny
W matematycznej dziedzinie teorii grafów wykres toroidalny to wykres , który można osadzić na torusie . Innymi słowy, wierzchołki wykresu można umieścić na torusie w taki sposób, aby żadne krawędzie się nie przecinały.
Przykłady
Każdy wykres, który można osadzić na płaszczyźnie, można również osadzić w torusie. Wykres toroidalny rodzaju 1 może być osadzony w torusie, ale nie w płaszczyźnie. Graf Heawooda , pełny graf K 7 (a więc K 5 i K 6 ), graf Petersena (a więc pełny graf dwudzielny K 3,3 , ponieważ graf Petersena zawiera jego podpodział), jeden z grafów Blanuša i wszystkie drabiny Möbiusa są toroidalne. Mówiąc bardziej ogólnie, każdy wykres z przecięciem numer 1 jest toroidalny. Niektóre wykresy z większymi liczbami skrzyżowań są również toroidalne: wykres Möbiusa – Kantora ma numer przecięcia 4 i jest toroidalny.
Nieruchomości
Każdy graf toroidalny ma co najwyżej liczbę chromatyczną 7. Pełny graf K 7 stanowi przykład wykresu toroidalnego o liczbie chromatycznej 7.
Każdy graf toroidalny bez trójkątów ma liczbę chromatyczną co najwyżej 4.
Z wyniku analogicznego do twierdzenia Fáry'ego można narysować dowolny wykres toroidalny z prostymi krawędziami w prostokącie z okresowymi warunkami brzegowymi . Ponadto w tym przypadku zastosowanie ma analogia twierdzenia o sprężynie Tutte'a . Wykresy toroidalne mają również osadzone książki z maksymalnie 7 stronami.
Przeszkody
Zgodnie z twierdzeniem Robertsona-Seymoura istnieje skończony zbiór H minimalnych grafów nietoroidalnych, taki że wykres jest toroidalny wtedy i tylko wtedy, gdy nie ma mniejszego wykresu w H . Oznacza to, że H tworzy zbiór zabronionych drugorzędnych dla grafów toroidalnych. Kompletny zestaw H nie jest znany, ale zawiera co najmniej 17 523 wykresów. Alternatywnie, istnieje co najmniej 250 815 grafów nietoroidalnych, które są minimalne w mniejszym topologii zamawianie. Graf jest toroidalny wtedy i tylko wtedy, gdy nie ma żadnego z tych grafów jako drugorzędnego topologicznego.
Galeria
Dwa izomorficzne grafy Cayleya grupy kwaternionów .
Wykres Cayleya grupy kwaternionów osadzonej w torusie.
Wideo przedstawiające wykres Cayleya grupy kwaternionów osadzonej w torusie.
Wykres Heawooda i powiązana mapa osadzone w torusie.
Wykres Pappusa i powiązana mapa osadzone w torusie.
Zobacz też
Notatki
- Chartrand, Gary ; Zhang, Ping (2008), Teoria grafów chromatycznych , CRC Press, ISBN 978-1-58488-800-0 .
- Endo, Toshiki (1997), „Numer stron wykresów toroidalnych wynosi co najwyżej siedem”, Discrete Mathematics , 175 (1–3): 87–96, doi : 10.1016/S0012-365X (96) 00144-6 , MR 1475841 .
- Gortler, Steven J.; Gotsman, Craig; Thurston, Dylan (2006), „Dyskretne jednoformy na siatkach i zastosowaniach do parametryzacji siatki 3D” (PDF) , Computer Aided Geometric Design , 23 (2): 83–112, doi : 10.1016/j.cagd.2005.05.002 , MR 2189438 , S2CID 135438 .
- Heawood, PJ (1890), „Twierdzenia o kolorowaniu map”, Quarterly Journal of Mathematics , pierwsza seria, 24 : 322–339 .
- Kocay, W.; Neilson, D.; Szypowski, R. (2001), „Rysowanie wykresów na torusie” (PDF) , Ars Combinatoria , 59 : 259–277, MR 1832459 , zarchiwizowane z oryginału (PDF) w dniu 2004-12-24 , pobrane 2018-09- 06 .
- Kronk, Hudson V.; White, Arthur T. (1972), „Twierdzenie o 4 kolorach dla wykresów toroidalnych”, Proceedings of the American Mathematical Society , American Mathematical Society , 34 (1): 83–86, doi : 10,2307/2037902 , JSTOR 2037902 , MR 0291019 .
- Marušič, Dragan ; Pisanski, Tomaž (2000), „Niezwykły uogólniony wykres Petersena G (8,3)”, Math. Slovaca , 50 : 117–121, CiteSeerX 10.1.1.28.7183 , hdl : 10338.dmlcz/133137 , MR 1763113 , Zbl 0984.05044 .
- Myrvold, Wendy ; Woodcock, Jennifer (2018), „Duży zestaw przeszkód torusowych i sposób ich odkrycia” , Electronic Journal of Combinatorics , 25 (1): P1.16, doi : 10,37236/3797
- Neufeld, Eugeniusz; Myrvold, Wendy (1997), „Praktyczne testowanie toroidalności” , Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , s. 574–580, ISBN 978-0-89871-390-9 .
- Orbanić, Alen; Pisanski, Tomaž ; Randić, Mediolan ; Servatius, Brigitte (2004), „Blanuša podwójna” (PDF) , Math. Komuna. , 9 (1): 91–103, CiteSeerX 10.1.1.361.2772 .