Jump to content

Субгамильтонов граф

В теории графов рисовании графов субгамильтонов граф это подграф планарного и гамильтонова графа . [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]

  1. ^ Хит, Ленвуд С. (1987), «Вложение внешнепланарных графов в небольшие книги», SIAM Journal on Algebraic and Discrete Methods , 8 (2): 198–218, doi : 10.1137/0608018 , MR   0881181 .
  2. ^ 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 .
  3. ^ Например, в техническом отчете 2003 года « Книжные вложения графов и теорема Уитни » Пол Кайнен определяет субгамильтоновы графы как подграфы плоских гамильтоновых графов без ограничений на множество вершин приращения, но пишет, что «в определении субгамильтонова графа можно потребовать, чтобы расширение включало только включение новых ребер».
  4. ^ Jump up to: а б Бекос, Майкл А.; Гронеманн, Мартин; Рафтопулу, Хрисанти Н. (2014), «Вложения 4-плоских графов в двухстраничную книгу», STACS , arXiv : 1401.0684 , Bibcode : 2014arXiv1401.0684B .
  5. ^ Бернхарт, Фрэнк Р.; Кайнен, Пол К. (1979), «Толщина графа в книге», Журнал комбинаторной теории , серия B, 27 (3): 320–331, doi : 10.1016/0095-8956(79)90021-2 .
  6. ^ Нисидзеки, Такао ; Чиба, Норишиге (2008), «Глава 10. Гамильтоновы циклы», Планарные графы: теория и алгоритмы , Dover Books on Mathematics, Courier Dover Publications, стр. 171–184, ISBN  9780486466712 .
  7. ^ Корнюжоль, Г. ; Наддеф, Д.; Пуллибланк, В.Р. (1983), «Графы Халина и проблема коммивояжера», Mathematical Programming , 26 (3): 287–294, doi : 10.1007/BF02591867 , S2CID   26278382 .
  8. ^ Кайнен, Пол С.; Овербей, Шеннон (2007), «Расширение теоремы Уитни», Applied Mathematics Letters , 20 (7): 835–837, arXiv : 2110.00820 , doi : 10.1016/j.aml.2006.08.019 , MR   2314718 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: d0643a4ca68aa02e4f238d346d1656d1__1704238500
URL1:https://arc.ask3.ru/arc/aa/d0/d1/d0643a4ca68aa02e4f238d346d1656d1.html
Заголовок, (Title) документа по адресу, URL1:
Subhamiltonian graph - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)