stringtranslate.com

Кубический граф

Граф Петерсена является кубическим графом.
Полный двудольный граф является примером бикубического графа.

В математической области теории графов кубический граф — это граф , в котором все вершины имеют степень три. Другими словами, кубический граф — это 3- регулярный граф . Кубические графы также называются трехвалентными графами .

Бикубический граф — это кубический двудольный граф .

Симметрия

В 1932 году Рональд М. Фостер начал собирать примеры кубических симметричных графов , что положило начало переписи Фостера . [1] Многие известные отдельные графы являются кубическими и симметричными, включая граф полезности , граф Петерсена , граф Хивуда , граф Мёбиуса–Кантора , граф Паппуса , граф Дезарга , граф Науру , граф Коксетера , граф Тутта–Коксетера , граф Дика , граф Фостера и граф Биггса–Смита . У. Т. Тутт классифицировал симметричные кубические графы по наименьшему целому числу s, такому, что каждые два ориентированных пути длины s могут быть отображены друг на друга ровно одной симметрией графа. Он показал, что s не превышает 5, и привел примеры графов с каждым возможным значением s от 1 до 5. [2]

К полусимметричным кубическим графам относятся граф Грея (наименьший полусимметричный кубический граф), граф Любляны и 12-клетка Тутте .

Граф Фрухта является одним из пяти наименьших кубических графов без каких-либо симметрий: [3] он обладает только одним графовым автоморфизмом — тождественным автоморфизмом. [4]

Раскраски и самостоятельные наборы

Согласно теореме Брукса, любой связный кубический граф, отличный от полного графа K 4 , имеет вершинную раскраску не более чем тремя цветами. Следовательно, любой связный кубический граф, отличный от K 4 , имеет независимое множество из не менее n /3 вершин, где n — число вершин в графе: например, наибольший цветовой класс в 3-раскраске имеет не менее этого числа вершин.

Согласно теореме Визинга, для раскраски ребер кубического графа требуется либо три, либо четыре цвета . Раскраска ребер в 3 цвета известна как раскраска Тейта и образует разбиение ребер графа на три совершенных паросочетания . По теореме Кёнига о раскраске линий каждый бикубический граф имеет раскраску Тейта.

Кубические графы без мостов, не имеющие раскраски Тейта, называются снарками . Они включают в себя граф Петерсена , граф Титце , снарки Блануши , снарки цветка , снарки двойной звезды , снарки Секереша и снарки Уоткинса . Существует бесконечное количество различных снарков. [5]

Топология и геометрия

Кубические графы естественным образом возникают в топологии несколькими способами. Например, кубические графы с 2g-2 вершинами описывают различные способы разрезания поверхности рода g ≥ 2 на пары брюк . Если рассматривать граф как 1-мерный комплекс CW , кубические графы являются общими в том смысле, что большинство 1-клеточных карт присоединения не пересекаются с 0-скелетом графа. Кубические графы также образуются как графы простых многогранников в трех измерениях, многогранников, таких как правильный додекаэдр со свойством, что три грани встречаются в каждой вершине.

Представление планарного вложения в виде граф-кодированной карты

Произвольное вложение графа на двумерной поверхности может быть представлено как кубическая графовая структура, известная как граф-кодированная карта . В этой структуре каждая вершина кубического графа представляет флаг вложения, взаимно инцидентную тройку вершины, ребра и грани поверхности. Три соседа каждого флага — это три флага, которые могут быть получены из него путем изменения одного из членов этой взаимно инцидентной тройки и оставления двух других членов неизменными. [6]

Гамильтоновость

Было проведено много исследований гамильтоновости кубических графов. В 1880 году П. Г. Тейт предположил, что каждый кубический полиэдральный граф имеет гамильтонов контур . Уильям Томас Тейт представил контрпример к гипотезе Тейта , 46-вершинный граф Тейта , в 1946 году. В 1971 году Тейт предположил, что все бикубические графы являются гамильтоновыми. Однако Джозеф Хортон предоставил контрпример для 96 вершин, граф Хортона . [7] Позже Марк Эллингем построил еще два контрпримера: графы Эллингема–Хортона . [8] [9] Гипотеза Барнетта , все еще открытая комбинация гипотез Тейта и Тейта, утверждает, что каждый бикубический полиэдральный граф является гамильтоновым. Когда кубический граф является гамильтоновым, нотация LCF позволяет представить его кратко.

Если кубический граф выбирается равномерно и случайным образом среди всех n -вершинных кубических графов, то весьма вероятно, что он будет гамильтоновым: доля n -вершинных кубических графов, которые являются гамильтоновыми, стремится к единице в пределе, когда n стремится к бесконечности. [10]

Дэвид Эппштейн предположил, что каждый кубический граф с n вершинами имеет не более 2 n /3 (приблизительно 1,260 n ) различных гамильтоновых циклов, и привел примеры кубических графов с таким количеством циклов. [11] Лучшая доказанная оценка количества различных гамильтоновых циклов равна . [12]

Другие свойства

Нерешенная задача по математике :
Какова наибольшая возможная ширина пути -вершинного кубического графа?
(еще нерешенные проблемы по математике)

Ширина пути любого n -вершинного кубического графа не превышает n / 6. Лучшая известная нижняя граница ширины пути кубических графов составляет 0,082 n . Неизвестно, как сократить этот разрыв между этой нижней границей и верхней границей n / 6. [13]

Из леммы о рукопожатии , доказанной Леонардом Эйлером в 1736 году в рамках первой статьи по теории графов, следует , что каждый кубический граф имеет четное число вершин.

Теорема Петерсена утверждает, что любой кубический граф без мостов имеет идеальное паросочетание . [14] Ловас и Пламмер предположили, что любой кубический граф без мостов имеет экспоненциальное число идеальных паросочетаний. Гипотеза была недавно доказана, показав, что любой кубический граф без мостов с n вершинами имеет по крайней мере 2 n/3656 идеальных паросочетаний. [15]

Алгоритмы и сложность

Несколько исследователей изучали сложность алгоритмов экспоненциального времени , ограниченных кубическими графами. Например, применяя динамическое программирование к путевой декомпозиции графа, Фомин и Хойе показали, как найти их максимальные независимые множества за время 2 n /6 + o( n ) . [13] Задача коммивояжера в кубических графах может быть решена за время O(1.2312 n ) и полиномиальное пространство. [16] [17]

Несколько важных задач оптимизации графов являются APX-трудными , что означает, что, хотя у них есть алгоритмы аппроксимации , коэффициент аппроксимации которых ограничен константой, у них нет схем аппроксимации за полиномиальное время , коэффициент аппроксимации которых стремится к 1, если только P=NP . К ним относятся задачи поиска минимального покрытия вершин , максимального независимого множества , минимального доминирующего множества и максимального разреза . [18] Число пересечений (минимальное число ребер, которые пересекаются в любом рисунке графа ) кубического графа также является NP-трудным для кубических графов, но может быть аппроксимировано. [19] Было доказано, что задача коммивояжера на кубических графах является NP - трудной для аппроксимации с точностью до любого множителя, меньшего 1153/1152. [20]

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

На Викискладе есть медиафайлы по теме 3-регулярные графы .

Ссылки

  1. ^ Фостер, Р. М. (1932), «Геометрические схемы электрических сетей», Труды Американского института инженеров-электриков , 51 (2): 309–317, doi : 10.1109/T-AIEE.1932.5056068, S2CID  51638449.
  2. ^ Tutte, WT (1959), «О симметрии кубических графов», Can. J. Math. , 11 : 621–624, doi : 10.4153/CJM-1959-057-2 , S2CID  124273238, заархивировано из оригинала 2011-07-16 , извлечено 2010-07-21.
  3. ^ Буссемейкер, ФК; Кобелжич, С.; Цветкович, ДМ; Зайдель, Дж. Дж. (1976), Компьютерное исследование кубических графов, отчет EUT, т. 76-WSK-01, Кафедра математики и вычислительной техники, Технологический университет Эйндховена
  4. ^ Фрухт, Р. (1949), «Графы степени три с заданной абстрактной группой», Канадский журнал математики , 1 (4): 365–378, doi : 10.4153/CJM-1949-033-6 , ISSN  0008-414X, MR  0032987, S2CID  124723321.
  5. ^ Айзекс, Р. (1975), «Бесконечные семейства нетривиальных трехвалентных графов, которые не раскрашиваются по Тейту», American Mathematical Monthly , 82 (3): 221–239, doi :10.2307/2319844, JSTOR  2319844.
  6. ^ Боннингтон, К. Пол; Литтл, Чарльз ХК (1995), Основы топологической теории графов , Springer-Verlag.
  7. ^ Бонди, JA и Мурти, Теория графов USR с приложениями. Нью-Йорк: Северная Голландия, стр. 240, 1976.
  8. ^ Эллингем, МН «Негамильтоновы 3-связные кубические дольные графы». Исследовательский отчет № 28, Кафедра математики, Мельбурнский университет, Мельбурн, 1981.
  9. ^ Эллингем, МН; Хортон, ДжД (1983), «Негамильтоновы 3-связные кубические двудольные графы», Журнал комбинаторной теории , Серия B, 34 (3): 350–353, doi : 10.1016/0095-8956(83)90046-1.
  10. ^ Робинсон, РВ; Вормальд, Н.К. (1994), «Почти все регулярные графы являются гамильтоновыми», Случайные структуры и алгоритмы , 5 (2): 363–374, doi :10.1002/rsa.3240050209.
  11. ^ Эппштейн, Дэвид (2007), «Задача коммивояжера для кубических графов» (PDF) , Журнал графовых алгоритмов и приложений , 11 (1): 61–81, arXiv : cs.DS/0302030 , doi : 10.7155/jgaa.00137.
  12. ^ Гебауэр, Х. (2008), «О числе гамильтоновых циклов в графах ограниченной степени», Труды 4-го семинара по аналитической алгоритмике и комбинаторике (ANALCO '08), стр. 241–248, doi :10.1137/1.9781611972986.8, ISBN 9781611972986.
  13. ^ ab Фомин, Федор В.; Хойе, Кьяртан (2006), «Путьевая ширина кубических графов и точные алгоритмы», Information Processing Letters , 97 (5): 191–196, doi :10.1016/j.ipl.2005.10.012.
  14. ^ Петерсен, Юлиус Питер Кристиан (1891), «Die Theorie der regularen Graphs (Теория регулярных графов)», Acta Mathematica , 15 (15): 193–220, doi : 10.1007/BF02392606 , S2CID  123779343.
  15. ^ Эспере, Луи; Кардош, Франтишек; Кинг, Эндрю Д.; Краль, Даниэль ; Норин, Сергей (2011), «Экспоненциально много совершенных паросочетаний в кубических графах», Advances in Mathematics , 227 (4): 1646–1664, arXiv : 1012.2878 , doi : 10.1016/j.aim.2011.03.015, S2CID  4401537.
  16. ^ Сяо, Минюй; Нагамочи, Хироши (2013), «Точный алгоритм для TSP в графах степени 3 с помощью процедуры схемы и амортизации на структуре связности», Теория и применение моделей вычислений , Lecture Notes in Computer Science, т. 7876, Springer-Verlag, стр. 96–107, arXiv : 1212.6831 , doi : 10.1007/978-3-642-38236-9_10, ISBN 978-3-642-38236-9.
  17. ^ Сяо, Минюй; Нагамочи, Хироши (2012), «Точный алгоритм для TSP в графах степени 3 с помощью процедуры схемы и амортизации на структуре связности», Algorithmica , 74 (2): 713–741, arXiv : 1212.6831 , Bibcode : 2012arXiv1212.6831X, doi : 10.1007/s00453-015-9970-4, S2CID  7654681.
  18. ^ Алимонти, Паола; Канн, Вигго (2000), «Некоторые результаты APX-полноты для кубических графов», Теоретическая информатика , 237 (1–2): 123–134, doi : 10.1016/S0304-3975(98)00158-3.
  19. ^ Глиненый, Петр (2006), «Число пересечений сложно для кубических графов», Журнал комбинаторной теории , Серия B, 96 (4): 455–471, doi : 10.1016/j.jctb.2005.09.009.
  20. ^ Карпински, Марек; Шмид, Ричард (2013), Аппроксимационная сложность графической задачи коммивояжера на кубических графах , arXiv : 1304.6800 , Bibcode : 2013arXiv1304.6800K.

Внешние ссылки