Кубический граф
В математической области теории графов кубический граф — это граф которого , все вершины имеют степень три. Другими словами, кубический граф — это 3- регулярный граф . Кубические графы также называются трехвалентными графами .
Бикубический граф — это кубический двудольный граф .
Симметрия [ править ]
В 1932 году Рональд М. Фостер начал собирать примеры кубических симметричных графов , положив начало переписи населения Фостера . [1] Многие известные отдельные графы являются кубическими и симметричными, в том числе граф полезности , граф Петерсена , граф Хивуда , граф Мёбиуса-Кантора , граф Паппуса , граф Дезарга , граф Науру , граф Коксетера , граф Тутте-Коксетера. граф , граф Дика , граф Фостера и граф Биггса-Смита . У. Татт классифицировал симметричные кубические графы по наименьшему целому числу s, так что каждые два ориентированных пути длины s могут быть сопоставлены друг с другом ровно одной симметрией графа. Он показал, что s не превосходит 5, и привел примеры графиков с каждым возможным значением s от 1 до 5. [2]
Полусимметричные кубические графы включают граф Грея (самый маленький полусимметричный кубический граф), граф Любляны и 12-клетку Тутте .
Граф Фрухта — один из пяти наименьших кубических графов без каких-либо симметрий: [3] он обладает только одним автоморфизмом графа — тождественным автоморфизмом. [4]
Раскраски и независимые множества [ править ]
Согласно теореме Брукса каждый связный кубический граф, кроме полного графа K4 , имеет раскраску вершин не более чем в три цвета. Следовательно, каждый связный кубический граф, отличный от K 4, имеет независимый набор , по крайней мере, из n /3 вершин, где n — количество вершин в графе: например, самый большой цветовой класс в 3-раскраске имеет по крайней мере такое количество вершины.
Согласно теореме Визинга каждого кубического графа требуется либо три, либо четыре цвета для раскраски ребер . Раскраска 3-х ребер известна как раскраска Тейта и образует разбиение ребер графа на три совершенных паросочетания . По теореме Кенига о раскраске линий каждый бикубический граф имеет раскраску Тейта.
Кубические графы без мостов, не имеющие раскраски Тейта, известны как снарки . К ним относятся граф Петерсена , граф Титце , снарк Блануши , снарк-цветок , снарк двойной звезды , снарк Секереса и снарк Уоткинса . Существует бесконечное количество различных приколов. [5]
Топология и геометрия [ править ]
Кубические графы естественным образом возникают в топологии несколькими способами. Например, кубические графы с 2g-2 вершинами описывают различные способы разрезания поверхности рода g ≥ 2 на пары штанов . Если рассматривать граф как одномерный комплекс CW , кубические графы являются общими в том смысле, что большинство карт прикрепления 1-клетки не пересекаются с 0-скелетом графа. Кубические графы также формируются как графы простых трехмерных многогранников , многогранников, таких как правильный додекаэдр , обладающий свойством, что в каждой вершине встречаются три грани.
Произвольный граф, вложенный в двумерную поверхность, может быть представлен как структура кубического графа, известная как карта, закодированная графом . В этой структуре каждая вершина кубического графа представляет собой флаг вложения, взаимно инцидентную тройку вершины, ребра и грани поверхности. Три соседа каждого флага — это три флага, которые можно получить из него, заменив один из членов этой взаимно инцидентной тройки и оставив два других члена неизменными. [6]
Гамильтоновость [ править ]
Было проведено много исследований гамильтоновости кубических графов. В 1880 году П.Г. Тейт предположил, что каждый граф кубических многогранников имеет гамильтонову схему . Уильям Томас Татт в 1946 году предоставил контрпример к гипотезе Тейта с 46 вершинами - граф Тутте . В 1971 году Татт предположил, что все бикубические графы являются гамильтоновыми. Однако Джозеф Хортон предоставил контрпример на 96 вершинах — граф Хортона . [7] Позже Марк Эллингем построил еще два контрпримера: графы Эллингема–Хортона . [8] [9] Гипотеза Барнетта , все еще открытая комбинация гипотез Тейта и Тутта, утверждает, что каждый бикубический многогранный граф является гамильтоновым. Когда кубический граф является гамильтоновым, обозначение LCF позволяет его представить кратко.
Если кубический граф выбирается равномерно случайным образом среди всех кубических графов с n - вершинами, то он, скорее всего, будет гамильтоновым: доля гамильтоновых кубических графов с n - вершинами стремится к единице в пределе, когда n стремится к бесконечности. [10]
Дэвид Эппштейн предположил, что каждый кубический граф с n вершинами имеет не более 2 н /3 (около 1,260 н ) различных гамильтоновых циклов и предоставил примеры кубических графов с таким количеством циклов. [11] Наилучшая доказанная оценка числа различных гамильтоновых циклов: . [12]
Другая недвижимость [ править ]
Какова наибольшая возможная ширина пути -вершинный кубический граф?
Ширина пути любого кубического графа с n -вершинами не превышает n /6. Самая известная нижняя граница ширины пути кубических графов равна 0,082 n . Неизвестно, как уменьшить этот разрыв между этой нижней границей и верхней границей n /6. [13]
следует Из леммы о рукопожатии , доказанной Леонардом Эйлером в 1736 году в рамках первой статьи по теории графов, , что каждый кубический граф имеет четное число вершин.
Теорема Петерсена утверждает, что каждый кубический без мостов граф имеет идеальное паросочетание . [14] Ловас и Пламмер предположили, что каждый кубический граф без мостов имеет экспоненциальное число совершенных паросочетаний. Гипотеза была недавно доказана, показав, что каждый кубический граф без мостов с n вершинами имеет по крайней мере 2 н/3656 идеальные совпадения. [15]
Алгоритмы и сложность [ править ]
Несколько исследователей изучали сложность алгоритмов экспоненциального времени, ограниченных кубическими графами. Например, применив динамическое программирование к по путям разложению графа , Фомин и Хойе показали, как найти их максимальные независимые множества за время 2. п /6 + о( п ) . [13] в Задача коммивояжера кубических графах может быть решена за время O(1,2312 н ) и полиномиальное пространство. [16] [17]
Некоторые важные задачи оптимизации графов являются сложными по APX , что означает, что, хотя у них есть алгоритмы аппроксимации которых , коэффициент аппроксимации ограничен константой, у них нет схем аппроксимации с полиномиальным временем , коэффициент аппроксимации которых стремится к 1, если только P = NP . К ним относятся проблемы нахождения минимального вершинного покрытия , максимального независимого множества , минимального доминирующего множества и максимального разреза . [18] Число пересечений (минимальное количество ребер, которые пересекаются на любом рисунке графа ) кубического графа также является NP-трудным для кубических графов, но может быть аппроксимировано. [19] NP - Доказано, что задачу коммивояжера на кубических графах трудно аппроксимировать с точностью до любого коэффициента меньше 1153/1152. [20]
См. также [ править ]
Ссылки [ править ]
- ^ Фостер, Р.М. (1932), «Геометрические схемы электрических сетей», Труды Американского института инженеров-электриков , 51 (2): 309–317, doi : 10.1109/T-AIEE.1932.5056068 , S2CID 51638449 .
- ^ Тутте, В.Т. (1959), «О симметрии кубических графов» , кан. Дж. Математика. , 11 : 621–624, doi : 10.4153/CJM-1959-057-2 , S2CID 124273238 , заархивировано из оригинала 16 июля 2011 г. , получено 21 июля 2010 г.
- ^ Буссемейкер, ФК; Кобельич, С.; Цветкович, Д.М.; Зайдель, Дж. Дж. (1976), Компьютерное исследование кубических графов , отчет EUT, том. 76-WSK-01, кафедра математики и информатики, Технологический университет Эйндховена
- ^ Фрухт, Р. (1949), «Графы третьей степени с заданной абстрактной группой», Canadian Journal of Mathematics , 1 (4): 365–378, doi : 10.4153/CJM-1949-033-6 , ISSN 0008-414X , МР 0032987 , S2CID 124723321 .
- ^ Айзекс, Р. (1975), «Бесконечные семейства нетривиальных трехвалентных графов, которые не раскрашиваются по Тейту», American Mathematical Monthly , 82 (3): 221–239, doi : 10.2307/2319844 , JSTOR 2319844 .
- ^ Боннингтон, К. Пол; Литтл, Чарльз Х.К. (1995), Основы топологической теории графов , Springer-Verlag .
- ^ Бонди, Дж. А. и Мерти, Теория графов USR с приложениями. Нью-Йорк: Северная Голландия, с. 240, 1976.
- ^ Эллингем, Миннесота «Негамильтоновы 3-связные кубические дробные графы». Отчет об исследовании № 28, факультет математики, Univ. Мельбурн, Мельбурн, 1981 год.
- ^ Эллингем, Миннесота; Хортон, JD (1983), «Негамильтоновы 3-связные кубические двудольные графы», Journal of Combinatorial Theory , Series B, 34 (3): 350–353, doi : 10.1016/0095-8956(83)90046-1 .
- ^ Робинсон, RW; Вормальд, Северная Каролина (1994), «Почти все регулярные графы являются гамильтоновыми», Случайные структуры и алгоритмы , 5 (2): 363–374, doi : 10.1002/rsa.3240050209 .
- ^ Эппштейн, Дэвид (2007), «Проблема коммивояжера для кубических графов» (PDF) , Журнал графовых алгоритмов и приложений , 11 (1): 61–81, arXiv : cs.DS/0302030 , doi : 10.7155/jgaa. 00137 .
- ^ Гебауэр, Х. (2008), «О количестве циклов Гамильтона в графах ограниченной степени», Proc. 4-й семинар по аналитической алгоритмике и комбинаторике (ANALCO '08) , стр. 241–248, doi : 10.1137/1.9781611972986.8 , ISBN 9781611972986 .
- ^ Перейти обратно: а б Фомин Федор Владимирович; Хойе, Кьяртан (2006), «Ширина кубических графов и точные алгоритмы», Information Processing Letters , 97 (5): 191–196, doi : 10.1016/j.ipl.2005.10.012 .
- ^ Петерсен, Юлиус Питер Кристиан (1891), «Die Theorie der regularen Graphs (Теория регулярных графов)» , Acta Mathematica , 15 (15): 193–220, doi : 10.1007/BF02392606 , S2CID 123779343 .
- ^ Эспере, Луи; Кардош, Франтишек; Кинг, Эндрю Д.; Краль, Даниэль ; Норин, Сергей (2011), «Экспоненциально много совершенных паросочетаний в кубических графах», Advances in Mathematics , 227 (4): 1646–1664, arXiv : 1012.2878 , doi : 10.1016/j.aim.2011.03.015 , S2CID 4401537 .
- ^ Сяо, Мингю; Нагамоти, Хироши (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 .
- ^ Сяо, Мингю; Нагамоти, Хироши (2012), «Точный алгоритм для TSP в графах степени 3 с помощью схемной процедуры и амортизации структуры связности», Algorithmica , 74 (2): 713–741, arXiv : 1212.6831 , Bibcode : 2012arXiv1212.6831X , doi : 10.1007/s00453-015-9970-4 , S2CID 7654681 .
- ^ Алимонти, Паола; Канн, Вигго (2000), «Некоторые результаты APX-полноты для кубических графов», Theoretical Computer Science , 237 (1–2): 123–134, doi : 10.1016/S0304-3975(98)00158-3 .
- ^ Хлиненый, Петр (2006), «Число пересечений сложно для кубических графов», Журнал комбинаторной теории , серия B, 96 (4): 455–471, doi : 10.1016/j.jctb.2005.09.009 .
- ^ Карпински, Марек; Шмид, Ричард (2013), Твердость аппроксимации графического TSP на кубических графах , arXiv : 1304.6800 , Bibcode : 2013arXiv1304.6800K .
Внешние ссылки [ править ]
- Ройл, Гордон. «Кубические симметричные графы (Перепись Фостера)» . Архивировано из оригинала 23 октября 2011 г.
- Вайсштейн, Эрик В. «Бикубический граф» . Математический мир .
- Вайсштейн, Эрик В. «Кубический граф» . Математический мир .
- Бринкманн, Гуннар; Гегебер, Ян; Ван Климпут, Нико (2013). «История создания кубических графов» (PDF) . Межд. Дж. Хим. Моделирование . 5 (2–3). Нова Сайенс: 67–89. ISSN 1941-3955 .