Тороидальный граф - Toroidal graph

А кубический граф с 14 вершинами, вложенными в тор
В График Хивуда и соответствующее отображение, вложенное в тор.

В математика, а тороидальный граф это график это может быть встроенный на тор. Другими словами, граф вершины можно разместить на торе, чтобы никакие ребра не пересекались.

Примеры

Любой граф, который можно вложить в плоскость, также можно вложить в тор. Тороидальный граф род 1 можно вложить в тор, но не в плоскость. В График Хивуда, то полный график K7 (а значит, K5 и K6), Граф Петерсена (и, следовательно, полный двудольный граф K3,3, поскольку граф Петерсена содержит его подразделение), одна из Blanuša Snarks,[1] и все Лестницы Мебиуса тороидальные. В общем, любой график с номер перехода 1 - тороидальный. Некоторые графы с большим числом пересечений также являются тороидальными: График Мёбиуса – Кантора, например, имеет перекресток номер 4 и является тороидальным.[2]

Характеристики

Любой тороидальный граф имеет хроматическое число максимум 7.[3] В полный график K7 приведен пример тороидального графа с хроматическим числом 7.[4]

Любой без треугольников тороидальный граф имеет хроматическое число не более 4.[5]

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

Препятствия

Посредством Теорема Робертсона – Сеймура, существует конечное множество ЧАС минимальных нетороидальных графов, таких что граф является тороидальным тогда и только тогда, когда он не имеет граф минор в ЧАС.То есть, ЧАС образует набор запрещенные несовершеннолетние для тороидальных графов. ЧАС неизвестно, но содержит не менее 17 523 графов. В качестве альтернативы существует не менее 250 815 нетороидальных графов, которые минимальны в топологический минор Упорядочение. Граф является тороидальным тогда и только тогда, когда он не имеет ни одного из этих графов в качестве топологического минора.[9]

Галерея

Смотрите также

Примечания

  1. ^ Орбанич и др. (2004).
  2. ^ Марушич и Писанский (2000).
  3. ^ Хивуд (1890).
  4. ^ Чартран и Чжан (2008).
  5. ^ Кронк и Уайт (1972).
  6. ^ Коджай, Нейлсон и Шиповски (2001).
  7. ^ Гортлер, Гоцман и Терстон (2006).
  8. ^ Эндо (1997).
  9. ^ Мирвольд и Вальдшнеп (2018).

Рекомендации