Toroidní graf - Toroidal graph

Image
Kubický graf s 14 vrcholy vložené na torus
Image
Heawoodův graf a související mapa vložené do prstence.

V matematice , je toroidní graf je graf , který může být vložen na torus . Jinými slovy, vrcholy grafu lze umístit na torus tak, aby se nepřekřížily žádné hrany.

Příklady

Jakýkoli graf, který lze vložit do roviny, lze také vložit do torusu. Toroidní graf rodu 1 může být vložen do torusu, ale ne do roviny. Heawoodův graf je úplný graf K 7 (a tím i K 5 a K 6 ), přičemž Petersen graf (a tedy i kompletní dvojdílný graf K 3,3 , protože Petersen graf obsahuje dělení ní), jeden z snarks Blanuša a všechny Möbiovy žebříky jsou toroidní. Obecněji řečeno, jakýkoli graf s křížením číslo 1 je toroidní. Některé grafy s většími čísly křížení jsou také toroidní: například Möbius-Kantorův graf má křížení číslo 4 a je toroidní.

Vlastnosti

Libovolný toroidní graf má chromatické číslo maximálně 7. Celý graf K 7 poskytuje příklad toroidního grafu s chromatickým číslem 7.

Jakýkoli toroidní graf bez trojúhelníků má chromatické číslo nejvýše 4.

Výsledkem analogickým Fáryho teorému může být jakýkoli toroidní graf nakreslen rovnými hranami v obdélníku s periodickými okrajovými podmínkami . V tomto případě dále platí analogie Tutteho jarní věty . Toroidní grafy mají také vložení knih s maximálně 7 stránkami.

Překážky

Podle věty Robertson – Seymour existuje konečná množina H minimálních netoroidních grafů, takže graf je toroidní právě tehdy, pokud nemá v H žádný minoritní graf . To znamená, že H tvoří soubor zakázaných nezletilých pro toroidní grafy. Kompletní sada H není známa, ale má alespoň 17 523 grafů. Alternativně existuje nejméně 250 815 netoroidních grafů, které jsou v topologickém minoritním uspořádání minimální . Graf je toroidní, právě když nemá žádný z těchto grafů jako topologickou minoritu.

Galerie

Viz také

Poznámky

Reference

  • Chartrand, Gary ; Zhang, Ping (2008), Chromatic graph theory , CRC Press, ISBN 978-1-58488-800-0.
  • Endo, Toshiki (1997), „The number of toroidal graphs is at most seven“, 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), „Diskrétní jednoformáty na sítích a aplikacích pro parametrizaci 3D sítí“ (PDF) , Computer Aided Geometric Design , 23 (2): 83–112, doi : 10,1016 / j.cagd.2005.05.002 , MR  2189438.
  • Heawood, PJ (1890), „Věty o zbarvení mapy“, Quarterly Journal of Mathematics , první řada, 24 : 322–339.
  • Kocay, W .; Neilson, D .; Szypowski, R. (2001), „Drawing graphs on the torus“ (PDF) , Ars Combinatoria , 59 : 259–277, MR  1832459 , archivovány z původního (PDF) dne 24. 12. 2004 , vyvoláno 2018-09- 06.
  • Kronk, Hudson V .; White, Arthur T. (1972), „ Čtyřbarevná věta pro toroidní grafy“, 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), „Pozoruhodný generalizovaný Petersenův graf G (8,3)“ , Math. Slovaca , 50 : 117–121.
  • Myrvold, Wendy ; Woodcock, Jennifer (2018), „A big set of torus obstructions and how they were identified “, Electronic Journal of Combinatorics , 25 (1): P1.16, doi : 10.37236 / 3797
  • Neufeld, Eugene; Myrvold, Wendy (1997), „Praktické testování toroidality“, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pp. 574–580.
  • Orbanić, Alen; Pisanski, Tomaž ; Randić, Milán ; Servatius, Brigitte (2004), "Blanuša double", Math. Commun. , 9 (1): 91–103.