Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Кубический граф с 14 вершинами внедренных на торе
Граф хивуд и ассоциированное отображение встроенного в торе.

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

Примеры [ править ]

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

Свойства [ править ]

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

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

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

Препятствия [ править ]

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

Галерея [ править ]

  • Два изоморфных графа Кэли группы кватернионов .

  • Граф Кэли группы кватернионов, вложенной в тор.

  • Воспроизвести медиа

    Видео графа Кэли группы кватернионов, вложенной в тор.

  • Граф хивуд и ассоциированное отображение встроенного в торе.

  • Граф Паппа и связанное с ним отображение, вложенное в тор.

См. Также [ править ]

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

Заметки [ править ]

  1. ^ Орбанич и др. (2004) .
  2. ^ Marusic & Pisanski (2000) .
  3. ^ В работе Хивуда (1890) .
  4. ^ Chartrand & Zhang (2008) .
  5. ^ Кронк & White (1972) .
  6. ^ Kocay, Нелсон и Szypowski (2001) .
  7. ^ Gortler, Гоцман & Thurston (2006) .
  8. Перейти ↑ Endo (1997) .
  9. ^ Myrvold & Вудкок (2018) .

Ссылки [ править ]

  • Чартран, Гэри ; Чжан, Пинг (2008), теория хроматических графов , CRC Press, ISBN 978-1-58488-800-0.
  • Эндо, Тошики (1997), «Число страниц тороидальных графов не превышает семи», Дискретная математика , 175 (1–3): 87–96, DOI : 10.1016 / S0012-365X (96) 00144-6 , MR  1475841.
  • Гортлер, Стивен Дж .; Гоцман, Крейг; Терстон, Дилан (2006), «Дискретные одноформы на сетках и приложения для параметризации трехмерных сеток» (PDF) , Компьютерное геометрическое проектирование , 23 (2): 83–112, doi : 10.1016 / j.cagd.2005.05.002 , Руководство по ремонту  2189438.
  • Heawood, PJ (1890), "Теоремы раскраски карт", Quarterly J. Math. Oxford Ser. , 24 : 322–339.
  • Kocay, W .; Neilson, D .; Шиповски, Р. (2001), «Рисование графиков на торе» (PDF) , Ars Combinatoria , 59 : 259–277, MR  1832459 , архивировано из оригинала (PDF) 24 декабря 2004 г. , получено 2018-09– 06.
  • Kronk, Hudson V .; Белый, Артур Т. (1972), "Теорема 4 цвета для тороидальных графов", Труды Американского математического общества , Американского математического общества, 34 (1): 83-86, DOI : 10,2307 / 2037902 , JSTOR  2037902 , MR  0291019.
  • Марушич, Драган ; Писанский, Томаж (2000), "Замечательный обобщенный граф Петерсена G (8,3)" , Math. Словака , 50 : 117–121[ постоянная мертвая ссылка ] .
  • Мирволд, Венди ; Вудкок, Дженнифер (2018), «Большой набор препятствий в виде тора и как они были обнаружены», Электронный журнал комбинаторики , 25 (1): P1.16
  • Нойфельд, Юджин; Мирволд, Венди (1997), «Практическое тестирование тороидальности», Труды восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 574–580.
  • Орбанич, Ален; Писанский, Томаж ; Рандич, Милан ; Серватиус, Бриджит (2004), «Blanuša double», Математика. Commun. , 9 (1): 91–103.