stringtranslate.com

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

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

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

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

Симметрия

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

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

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

Раскраски и независимые множества

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

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

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

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

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

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

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

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

Было проведено много исследований гамильтоновости кубических графов. В 1880 году П.Г. Тейт предположил, что каждый граф кубических многогранников имеет гамильтонову схему . Уильям Томас Татт в 1946 году предоставил контрпример к гипотезе Тейта - граф Тутте с 46 вершинами . В 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. ^ Тутте, WT (1959), «О симметрии кубических графов», Can. Дж. Математика. , 11 : 621–624, doi : 10.4153/CJM-1959-057-2 , S2CID  124273238, заархивировано из оригинала 16 июля 2011 г. , получено 21 июля 2010 г..
  3. ^ Буссемакер, ФК; Кобельич, С.; Цветкович, Д.М.; Зайдель, Дж. Дж. (1976), Компьютерное исследование кубических графов, отчет EUT, том. 76-WSK-01, кафедра математики и информатики, Технологический университет Эйндховена
  4. ^ Фрухт, Р. (1949), «Графы третьей степени с заданной абстрактной группой», Canadian Journal of Mathematics , 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. ^ Бонди, Дж. А. и Мурти, Теория графов USR с приложениями. Нью-Йорк: Северная Голландия, с. 240, 1976.
  8. ^ Эллингем, Миннесота «Негамильтоновы 3-связные кубические дробные графы». Отчет об исследовании № 28, факультет математики, Univ. Мельбурн, Мельбурн, 1981 год.
  9. ^ Эллингем, Миннесота; Хортон, JD (1983), «Негамильтоновы 3-связные кубические двудольные графы», Журнал комбинаторной теории , серия B, 34 (3): 350–353, doi : 10.1016/0095-8956(83)90046-1.
  10. ^ Робинсон, RW; Вормальд, Северная Каролина (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), «О количестве циклов Гамильтона в графах ограниченной степени», Proc. 4-й семинар по аналитической алгоритмике и комбинаторике (ANALCO '08), стр. 241–248, doi : 10.1137/1.9781611972986.8, ISBN 9781611972986.
  13. ^ аб Фомин, Федор В.; Хойе, Кьяртан (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), «Экспоненциально много совершенных паросочетаний в кубических графах», Успехи в математике , 227 (4): 1646–1664, arXiv : 1012.2878 , doi : 10.1016/j.aim.2011.03.015, S2CID  4401537.
  16. ^ Сяо, Мингю; Нагамоти, Хироши (2013), «Точный алгоритм для TSP в графах степени 3 с помощью схемной процедуры и амортизации структуры связности», Теория и применение моделей вычислений , Конспекты лекций по информатике, том. 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 для кубических графов», Theoretical Computer Science , 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), Твердость аппроксимации графического TSP на кубических графах , arXiv : 1304.6800 , Bibcode : 2013arXiv1304.6800K.

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