WikiSort.ru - Не сортированное

Тороида́льный граф — граф, который можно уложить на тор; иными словами, это — граф, вершины которого можно разместить на торе так, что рёбра не будут пересекаться.

Тороидален любой граф с числом пересечений равным 1. В частности, таковы полный граф ${\displaystyle K_{5}}$ и полный двудольный граф ${\displaystyle K_{3,3}}$ (граф «домики и колодцы») и все остальные лестницы Мёбиуса. Некоторые графы с бо́льшим числом пересечений тоже являются тороидальными. Например, полный граф ${\displaystyle K_{7}}$ (с число пересечений 9, и, как следствие, ${\displaystyle K_{6}}$ с числом пересечений 3), граф Петерсена (с числом пересечений 2), граф Хивуда (с числом пересечений 3), граф Мёбиуса — Кантора (имеющий число пересечений, равное 4)^[1], один из снарков Блануши^[2] .

Хроматическое число любого тороидального графа не превышает 7^[3]; пример тороидального графа с хроматическим числом 7 — полный граф ${\displaystyle K_{7}}$ ^[4]. Хроматическое число любого тороидального графа без треугольников не превосходит 4^[5].

По аналогии с теоремой Фари, любой тороидальный граф можно нарисовать с рёбрами в виде отрезков в прямоугольнике с периодическими границами (то есть противоположные границы квадрата отождествляются)^[6]. Кроме того, в этом случае применима теорема Тутте^[en][7].

Тороидальные графы также допускают книжное вложение с максимум 7 листами^[8].

См. также

• Планарный граф
• Топологическая теория графов
• Многогранник Часара

Примечания

Ссылки

• Chartrand, Gary; Zhang Ping.  Chromatic graph theory. — CRC Press, 2008. — ISBN 978-1-58488-800-0.
• Endo, Toshiki.  The pagenumber of toroidal graphs is at most seven // Discrete Mathematics. — 1997. — Vol. 175, no. 1–3. — P. 87—96. — DOI:10.1016/S0012-365X(96)00144-6.
• Gortler, Steven J.; Gotsman, Craig; Thurston, Dylan.  Discrete one-forms on meshes and applications to 3D mesh parameterization // Computer Aided Geometric Design. — 2006. — Vol. 23, no. 2. — P. 83—112. — DOI:10.1016/j.cagd.2005.05.002.
• Heawood P. J.  Map colouring theorems // Quarterly J. Math. Oxford Ser.. — 1890. — Vol. 24. — P. 322—339.
• Kocay W., Neilson D., Szypowski R.  Drawing graphs on the torus // Ars Combinatoria. — 2001. — Vol. 59. — P. 259—277.
• Kronk, Hudson V.; White, Arthur T.  A 4-color theorem for toroidal graphs // Proceedings of the American Mathematical Society. — 1972. — Vol. 34, no. 1. — P. 83—86. — DOI:10.2307/2037902.
• Marušič, Dragan; Pisanski, Tomaž.  The remarkable generalized Petersen graph G(8,3) // Math. Slovaca. — 2000. — Vol. 50. — P. 117—121. (недоступная ссылка)
• Neufeld, Eugene; Myrvold, Wendy.  Practical toroidality testing // Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. — 1997. — P. 574—580.
• Orbanić, Alen; Pisanski, Tomaž; Randić, Milan; Servatius, Brigitte.  Blanuša double // Math. Commun. — 2004. — Vol. 9, no. 1. — P. 91—103.