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

В математической области теории графов кубический граф — это граф которого , все вершины имеют степень три. Другими словами, кубический граф — это 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 ]} Наилучшая доказанная оценка числа различных гамильтоновых циклов: $O({1.276}^{n})$ . ^{[ 12 ]}

Другие объекты недвижимости

Нерешенная задача по математике :

Какова наибольшая возможная ширина пути

n

-вершинный кубический граф?

(еще нерешенные задачи по математике)

Ширина пути любого кубического графа с 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), «Теория регулярных графов» , 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 .

[Ref_Foster-1] Фостер, Р.М. (1932), «Геометрические схемы электрических сетей», Труды Американского института инженеров-электриков , 51 (2): 309–317, doi : 10.1109/T-AIEE.1932.5056068 , S2CID 51638449 .

[2] Тутте, В.Т. (1959), «О симметрии кубических графов» , кан. Дж. Математика. , 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 , МР 0032987 , S2CID 124723321 .

[5] Айзекс, Р. (1975), «Бесконечные семейства нетривиальных трехвалентных графов, которые не раскрашиваются по Тейту», American Mathematical Monthly , 82 (3): 221–239, doi : 10.2307/2319844 , JSTOR 2319844 .

[6] Боннингтон, К. Пол; Литтл, Чарльз Х.К. (1995), Основы топологической теории графов , Springer-Verlag .

[Ref_a-7] Бонди, Дж. А. и Мерти, Теория графов USR с приложениями. Нью-Йорк: Северная Голландия, с. 240, 1976.

[Ref_b-8] Эллингем, Миннесота «Негамильтоновы 3-связные кубические дробные графы». Отчет об исследовании № 28, факультет математики, Univ. Мельбурн, Мельбурн, 1981 год.

[Ref_c-9] Эллингем, Миннесота; Хортон, JD (1983), «Негамильтоновы 3-связные кубические двудольные графы», Journal of Combinatorial Theory , Series 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 .

[fh06-13] Перейти обратно: ^а ^б Фомин Федор Владимирович; Хойе, Кьяртан (2006), «Ширина кубических графов и точные алгоритмы», Information Processing Letters , 97 (5): 191–196, doi : 10.1016/j.ipl.2005.10.012 .

[Pet1891-14] Петерсен, Юлиус Питер Кристиан (1891), «Теория регулярных графов» , Acta Mathematica , 15 (15): 193–220, doi : 10.1007/BF02392606 , S2CID 123779343 .

[EKKKN11-15] Эспере, Луи; Кардош, Франтишек; Кинг, Эндрю Д.; Кинг, Дэниел ; Норин, Сергей (2011), «Экспоненциально много совершенных паросочетаний в кубических графах», Advances in Mathematics , 227 (4): 1646–1664, arXiv : 1012.2878 , doi : 10.1016/j.aim.2011.03.015 , S2CID 4401537 .

[XiaoNag13-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 .

[Hlinny2006-19] Хлиненый, Петр (2006), «Число пересечения сложно для кубических графов», Журнал комбинаторной теории , серия B, 96 (4): 455–471, doi : 10.1016/j.jctb.2005.09.009 .

[20] Карпински, Марек; Шмид, Ричард (2013), Твердость аппроксимации графического TSP на кубических графах , arXiv : 1304.6800 , Bibcode : 2013arXiv1304.6800K .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]