Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Не следует путать с графиками из кубических функций , гиперкуб графа , куба графа , кубического графа .
Граф Петерсена - это кубический граф.
Полный двудольный граф представляет собой пример графика бикубического

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

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

Симметрия [ править ]

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

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

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

Раскраски и независимые наборы [ править ]

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

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

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

Топология и геометрия [ править ]

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

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

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

Гамильтоничность [ править ]

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

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

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

Другие свойства [ править ]

Вопрос, Web Fundamentals.svgНерешенная задача по математике :
Какова наибольшая возможная ширина пути кубического графа с вершинами?
(больше нерешенных задач по математике)

Pathwidth из любого N -vertex кубического графа не превосходит п / 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]

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

  • Таблица простых кубических графов

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

  1. ^ Фостер, Р. (1932), "Геометрические схемы электрических сетей", Труды Американского института инженеров - электриков , 51 (2): 309-317, DOI : 10,1109 / T-AIEE.1932.5056068.
  2. ^ Тутте, WT (1959), "О симметрии кубических графов" , Can. J. Math. , 11 : 621-624, DOI : 10,4153 / CJM-1959-057-2.
  3. ^ Буссемейкер, ФК; Cobeljic, S .; Цветкович, DM; Зайдель, Дж. Дж. (1976), Компьютерное исследование кубических графов , отчет EUT, 76-WSK-01, кафедра математики и вычислительной техники, Технологический университет Эйндховена
  4. ^ Frucht, R. (1949), "Графы третьей степени с данной абстрактной группы", Canadian Journal математики , 1 : 365-378, DOI : 10,4153 / CJM-1949-033-6 , ISSN 0008-414X , MR 0032987  .
  5. ^ Айзекс, R. (1975), "бесконечные семейства нетривиальных трехвалентных графов, не являющихся Тейт раскраску", American Mathematical Monthly , 82 (3): 221-239, DOI : 10,2307 / 2319844 , JSTOR 2319844 .
  6. ^ Боннингтон, К. Пол; Литтл, Чарльз ХК (1995), Основы топологической теории графов , Springer-Verlag.
  7. ^ Бонди, Дж. А. и Мерти, Теория графов USR с приложениями. Нью-Йорк: Северная Голландия, стр. 240, 1976.
  8. ^ Ellingham, MN "Негамильтоновы 3-связные кубические долевые графы". Отчет об исследовании № 28, Отдел математики, Univ. Мельбурн, Мельбурн, 1981.
  9. ^ Эллингем, Миннесота; Хортон, Дж. Д. (1983), " Негамильтоновы трехсвязные кубические двудольные графы", Журнал комбинаторной теории , серия B, 34 (3): 350–353, DOI : 10.1016 / 0095-8956 (83) 90046-1.
  10. ^ Робинсон, RW; Wormald, NC (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 0,00137 .
  12. ^ Гебауэр, Х. (2008), "О числе циклов Гамильтона в графах с ограниченной степенью", Proc. 4-й семинар по аналитической алгоритмике и комбинаторике (ANALCO '08).
  13. ^ а б Фомин, Федор В .; Хойе, Кьяртан (2006), "Пропускная способность кубических графов и точные алгоритмы", Письма об обработке информации , 97 (5): 191–196, DOI : 10.1016 / j.ipl.2005.10.012.
  14. ^ Петерсен, Julius Питер Кристиан (1891), "Die Theorie дер regulären Графики (Теория регулярных графов)" (PDF) , Acta Mathematica , 15 (15): 193-220, DOI : 10.1007 / BF02392606 .
  15. ^ Эспере, Луи; Кардош, Франтишек; Кинг, Эндрю Д .; Krá, Daniel ; Норин, Сергей (2011), «Экспоненциально много точных сопоставлений в кубических графах», Успехи в математике , 227 (4): 1646–1664, arXiv : 1012.2878 , doi : 10.1016 / j.aim.2011.03.015.
  16. ^ Сяо, Минюй; Нагамочи, Хироши (2013), «Точный алгоритм для TSP в графах степени 3 с помощью схемной процедуры и амортизации на структуре связности», Теория и приложения моделей вычислений , Lecture Notes in Computer Science, 7876 , Springer-Verlag, pp. 96–107, arXiv : 1212.6831 , doi : 10.1007 / 978-3-642-38236-9_10 , ISBN 978-3-642-38236-9.
  17. ^ Сяо, Минюй; Нагамочи, Хироши (2012), Точный алгоритм для TSP в графах степени 3 с помощью процедуры схемы и амортизации структуры подключения , arXiv : 1212.6831 , Bibcode : 2012arXiv1212.6831X.
  18. ^ Алимонти, Паола; Kann, Вигго (2000), "Некоторые APX-полноты результатов для кубических графов", Теоретическая информатика , 237 (1-2): 123-134, DOI : 10.1016 / S0304-3975 (98) 00158-3.
  19. ^ Hliněný, Петр (2006), «Число пересечений трудно для кубических графов», Журнал комбинаторной теории , серия B, 96 (4): 455–471, doi : 10.1016 / j.jctb.2005.09.009.
  20. ^ Карпинский, Марек; Шмид, Ричард (2013), Аппроксимационная твердость графического TSP на кубических графах , arXiv : 1304.6800 , Bibcode : 2013arXiv1304.6800K.

Внешние ссылки [ править ]

  • Ройл, Гордон. «Кубические симметричные графы (перепись Фостера)» . Архивировано из оригинала на 2011-10-23.
  • Вайсштейн, Эрик В. «Бикубический граф» . MathWorld .
  • Вайсштейн, Эрик В. «Кубический граф» . MathWorld .