Субгамильтонов граф
В теории графов рисовании графов — субгамильтонов граф это подграф планарного и гамильтонова графа . [1] [2]
Определение
[ редактировать ]Граф G является субгамильтоновым, если G является подграфом другого графа aug( G ) на том же множестве вершин, такого, что aug( G ) является плоским и содержит гамильтонов цикл . Чтобы это было правдой, G должна быть возможность добавлять ребра сам по себе должен быть плоским, и, кроме того, к G , сохраняя планарность, чтобы создать в расширенном графе цикл, проходящий через каждую вершину ровно один раз. Граф aug( G называется гамильтоновым дополнением G ) . [2]
Было бы эквивалентно определить G как субгамильтонов, если G является подграфом гамильтонова плоского графа, не требуя, чтобы этот больший граф имел тот же набор вершин. То есть для этого альтернативного определения должна быть возможность добавлять к G как вершины, так и ребра , чтобы создать гамильтонов цикл. Однако если граф можно сделать гамильтоновым путем добавления вершин и ребер, его также можно сделать гамильтоновым путем добавления только ребер, поэтому эта дополнительная свобода не меняет определения. [3]
В субгамильтоновом графе субгамильтонов цикл — это циклическая последовательность вершин, такая, что добавление ребра между каждой последовательной парой вершин в последовательности сохраняет планарность графа. Граф является субгамильтоновым тогда и только тогда, когда он имеет субгамильтонов цикл. [4]
История и приложения
[ редактировать ]Класс субгамильтоновых графов (но не это название для них) был введен Бернхартом и Кайненом (1979) , которые доказали, что это именно графы с двухстраничными книжными вложениями . [5] Субгамильтоновы графы и гамильтоновы дополнения также применялись при рисовании графов для решения задач, связанных с встраиванием графов в универсальные множества точек , одновременным внедрением нескольких графов и рисованием многослойных графов . [2]
Связанные классы графов
[ редактировать ]Некоторые классы плоских графов обязательно гамильтоновы и, следовательно, субгамильтоновы; к ним относятся 4-связные плоские графы [6] и графики Халина . [7]
Каждый планарный граф с максимальной степенью не выше четырех является субгамильтоновым, [4] как и любой плоский граф без разделяющих треугольников. [8] Если ребра произвольного планарного графа подразделить на пути длины два, полученный подразделенный граф всегда будет субгамильтоновым. [2]
Ссылки
[ редактировать ]- ^ Хит, Ленвуд С. (1987), «Вложение внешнепланарных графов в небольшие книги», SIAM Journal on Algebraic and Discrete Methods , 8 (2): 198–218, doi : 10.1137/0608018 , MR 0881181 .
- ^ Jump up to: а б с д Ди Джакомо, Эмилио; Лиотта, Джузеппе (2010), «Проблема гамильтониана и ее приложения к построению графиков», WALCOM: Алгоритмы и вычисления, 4-й международный семинар, WALCOM 2010, Дакка, Бангладеш, 10–12 февраля 2010 г., Труды , Конспекты лекций по компьютеру Наука, том. 5942, Берлин: Springer, стр. 35–46, номер документа : 10.1007/978-3-642-11440-3_4 , MR 2749626 .
- ^ Например, в техническом отчете 2003 года « Книжные вложения графов и теорема Уитни » Пол Кайнен определяет субгамильтоновы графы как подграфы плоских гамильтоновых графов без ограничений на множество вершин приращения, но пишет, что «в определении субгамильтонова графа можно потребовать, чтобы расширение включало только включение новых ребер».
- ^ Jump up to: а б Бекос, Майкл А.; Гронеманн, Мартин; Рафтопулу, Хрисанти Н. (2014), «Вложения 4-плоских графов в двухстраничную книгу», STACS , arXiv : 1401.0684 , Bibcode : 2014arXiv1401.0684B .
- ^ Бернхарт, Фрэнк Р.; Кайнен, Пол К. (1979), «Толщина графа в книге», Журнал комбинаторной теории , серия B, 27 (3): 320–331, doi : 10.1016/0095-8956(79)90021-2 .
- ^ Нисидзеки, Такао ; Чиба, Норишиге (2008), «Глава 10. Гамильтоновы циклы», Планарные графы: теория и алгоритмы , Dover Books on Mathematics, Courier Dover Publications, стр. 171–184, ISBN 9780486466712 .
- ^ Корнюжоль, Г. ; Наддеф, Д.; Пуллибланк, В.Р. (1983), «Графы Халина и проблема коммивояжера», Mathematical Programming , 26 (3): 287–294, doi : 10.1007/BF02591867 , S2CID 26278382 .
- ^ Кайнен, Пол С.; Овербей, Шеннон (2007), «Расширение теоремы Уитни», Applied Mathematics Letters , 20 (7): 835–837, arXiv : 2110.00820 , doi : 10.1016/j.aml.2006.08.019 , MR 2314718 .