В математической области теории графов тороидальный граф — это граф , который может быть вложен в тор . Другими словами, вершины и ребра графа могут быть размещены на торе таким образом, что никакие ребра не пересекаются, за исключением вершины, которая принадлежит обоим.
Любой граф, который может быть вложен в плоскость, может быть вложен и в тор, поэтому каждый планарный граф также является тороидальным графом. Говорят, что тороидальный граф, который не может быть вложен в плоскость, имеет род 1.
Граф Хивуда , полный граф K 7 (и, следовательно, K 5 и K 6 ), граф Петерсена (и, следовательно, полный двудольный граф K 3,3 , поскольку граф Петерсена содержит его подразделение), один из снарков Блануши [1] и все лестницы Мёбиуса являются тороидальными. В более общем смысле, любой граф с числом пересечений 1 является тороидальным. Некоторые графы с большим числом пересечений также являются тороидальными: например, граф Мёбиуса–Кантора имеет число пересечений 4 и является тороидальным. [2]
Любой тороидальный граф имеет хроматическое число не более 7. [3] Полный граф K 7 представляет собой пример тороидального графа с хроматическим числом 7. [4]
Любой тороидальный граф без треугольников имеет хроматическое число не более 4. [5]
По результату, аналогичному теореме Фари , любой тороидальный граф может быть нарисован с прямыми ребрами в прямоугольнике с периодическими граничными условиями . [6] Кроме того, в этом случае применим аналог теоремы Тутте о пружине . [7] Тороидальные графы также имеют книжные вложения с максимум 7 страницами. [8]
По теореме Робертсона–Сеймура существует конечное множество H минимальных нетороидальных графов, такое, что граф является тороидальным тогда и только тогда, когда он не имеет минора графа в H. То есть, H образует множество запрещенных миноров для тороидальных графов. Полное множество H неизвестно, но оно содержит не менее 17 523 графов. В качестве альтернативы, существует не менее 250 815 нетороидальных графов, которые минимальны в топологическом минорном порядке. Граф является тороидальным тогда и только тогда, когда он не содержит ни одного из этих графов в качестве топологического минора. [9]
