Věta o Hanani – Tutte - Hanani–Tutte theorem
v teorie topologických grafů, Věta o Hanani – Tutte je výsledek na parita z přechody hran v kreslení grafu. Uvádí, že každý výkres v rovině a nerovinný graf obsahuje dvojici nezávislých hran (ne obě sdílejících koncový bod), které se navzájem protínají lichým počtem opakování. Ekvivalentně jej lze formulovat jako kritérium rovinnosti: graf je rovinný právě tehdy, má-li výkres, ve kterém každá dvojice nezávislých hran protíná rovnoměrně (nebo vůbec).[1]
Dějiny
Výsledek je pojmenován po Haim Hanani, který v roce 1934 dokázal, že každá kresba těchto dvou minimální nerovinné grafy K.5 a K.3,3 má pár hran s lichým počtem křížení,[2] a poté W. T. Tutte, který uvedl úplnou větu výslovně v roce 1970.[3] Souběžný vývoj podobných myšlenek v EU algebraická topologie byl připsán Egbert van Kampen, Arnold S. Shapiro, a Wu Wenjun.[4][5][6][7][8][9]
Aplikace
Jedním z důsledků věty je, že testování toho, zda je graf rovinný, lze formulovat jako řešení a soustava lineárních rovnic přes konečné pole řádu dva. Tyto rovnice lze vyřešit v polynomiální čas, ale výsledný algoritmy jsou méně účinné než jiné známé testy rovinnosti.[1]
Zobecnění
Pro jiné povrchy S než na rovinu, lze nakreslit graf S bez křížení tehdy a jen tehdy, je-li to možné nakreslit tak, že se všechny páry hran protnou sudým počtem opakování; toto je známé jako slabá Hanani – Tutteova věta pro S. Silná věta Hanani – Tutte, známá pro projektivní rovina stejně jako pro euklidovskou rovinu uvádí, že graf lze nakreslit bez křížení S právě tehdy, když to lze nakreslit tak, že všechny nezávislé dvojice hran protínají sudý počet opakování, bez ohledu na počet křížení mezi hranami, které sdílejí koncový bod.[10]
Stejný přístup, ve kterém jeden ukazuje, že dvojice hran s párným počtem křížení mohou být ignorovány nebo vyloučeny v nějakém typu výkresu grafu a používá tuto skutečnost k nastavení systému lineárních rovnic popisujících existenci výkresu, byl aplikován na několik dalších problémů s kreslením grafů, včetně nahoru rovinné výkresy,[11] kresby minimalizující počet nezkřížených hran,[12][13] a seskupená rovinnost.[14]
Reference
- ^ A b Schaefer, Marcus (2013), „Směrem k teorii rovinnosti: Hanani – Tutte a varianty rovinnosti“, Journal of Graph Algorithms and Applications, 17 (4): 367–440, doi:10,7155 / jgaa.00298, PAN 3094190.
- ^ Chojnacki, Ch. (1934), „Über wesentlich unplättbare Kurven im dreidimensionalen Raume“, Fundamenta Mathematicae, Matematický ústav Polské akademie věd, 23 (1): 135–142, doi:10,4064 / fm-23-1-135-142. Viz zejména (1), s. 137.
- ^ Tutte, W. T. (1970), „Směrem k teorii křížení čísel“, Journal of Combinatorial Theory, 8: 45–53, doi:10.1016 / s0021-9800 (70) 80007-2, PAN 0262110.
- ^ Levow, Roy B. (1972), „O algebraickém přístupu Tutte k teorii křížení čísel“, Proceedings of the Third Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1972), Florida Atlantic Univ., Boca Raton, Florida, str. 315–314, PAN 0354426.
- ^ Schaefer, Marcus, „Hanani – Tutte a související výsledky“, Bárány, I .; Böröczky, K. J .; Tóth, G. F .; et al. (eds.), Geometrie - intuitivní, diskrétní a konvexní - pocta László Fejes Tóth (PDF), Matematické studie společnosti Bolyai, Berlín: Springer
- ^ van Kampen, E. R. (1933), „Komplexe in euklidischen Räumen“, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 9 (1): 72–78, doi:10.1007 / BF02940628, PAN 3069580.
- ^ Wu, Wen-Tsün (1955), „O realizaci komplexů v euklidovských prostorech. I“, Acta Mathematica Sinica, 5: 505–552, PAN 0076334.
- ^ Shapiro, Arnold (1957), „Překážky vnoření komplexu do euklidovského prostoru. I. První překážka“, Annals of Mathematics, Druhá série, 66 (2): 256–269, doi:10.2307/1969998, JSTOR 1969998, PAN 0089410.
- ^ Wu, Wen Jun (1985), "O rovinném uložení lineárních grafů. I", Journal of Systems Science and Mathematical Sciences, 5 (4): 290–302, PAN 0818118. Pokračování v 6 (1): 23–35, 1986.
- ^ Pelsmajer, Michael J .; Schaefer, Marcus; Stasi, Despina (2009), „Silný Hanani-Tutte v projektivní rovině“, SIAM Journal on Discrete Mathematics, 23 (3): 1317–1323, CiteSeerX 10.1.1.217.7182, doi:10.1137 / 08072485X, PAN 2538654.
- ^ Fulek, Radoslav; Pelsmajer, Michael J .; Schaefer, Marcus; Štefanković, Daniel (2013), „Hanani – Tutte, monotónní kresby a rovinná rovinnost“, v Pach, János (vyd.), Třicet esejů o teorii geometrických grafůSpringer, ISBN 978-1-4614-0110-0.
- ^ Pach, János; Tóth, Géza (2000), „O jaké číslo přechodu vlastně jde?“, Journal of Combinatorial Theory, Řada B, 80 (2): 225–246, doi:10.1006 / jctb.2000.1978, PAN 1794693.
- ^ Pelsmajer, Michael J .; Schaefer, Marcus; Štefankovič, Daniel (2007), „Odstranění sudých přechodů“, Journal of Combinatorial Theory, Řada B, 97 (4): 489–500, doi:10.1016 / j.jctb.2006.08.001, PAN 2325793.
- ^ Gutwenger, C .; Mutzel, P.; Schaefer, M., „Praktické zkušenosti s Hanani – Tutte pro testování C-planárnost ", Sborník šestnáctého workshopu o algoritmickém inženýrství a experimentech (ALENEX) z roku 2014, str. 86–97, doi:10.1137/1.9781611973198.9.