Подгамильтонов граф

Перейти к навигацииПерейти к поиску

Подгамильтонов граф — это подграф планарного гамильтонова графа[1][2].

Определение

Граф G является подгамильтоновым, если G является подграфом некоторого другого графа aug(G) с тем же множеством вершин, при этом граф aug(G) планарен и содержит гамильтонов цикл. Чтобы эти условия выполнялись, сам граф G должен быть планарным и, кроме того, должна существовать возможность добавить рёбра с сохранением планарности, чтобы создать цикл в расширенном графе, проходящий все вершины ровно один раз. Граф aug(G) называется гамильтоновым расширением графа G[2].

Можно было бы дать определение подгамильтонова графа как подграфа гамильтонова графа без требования, что этот больший граф имеет то же самое множество вершин. То есть в этом альтернативном определении можно было бы добавлять вершины и рёбра. Однако, если граф может быть сделан гамильтоновым с помощью добавления вершин и рёбер, его можно сделать таковым и без добавления вершин, так что эта дополнительная свобода не меняет определение[3]

В подгамильтоновом графе подгамильтонов цикл — это циклическая последовательность вершин, такая, что добавление ребра в любую пару вершин в последовательности не нарушает планарности графа. Граф является подгамильтоновым тогда и только тогда, когда он имеет подгамильтонов цикл[4].

История и приложения

Класс подгамильтоновых графов (но не имя класса) предложили Бернхарт и Кайнен[5]. Они доказали, что это в точности те графы, которые имеют две страницы в книжных вложениях[6]. Подгамильтоновы графы и гамильтоновы расширения использовались также в области визуализации графов для задач вложения графов в универсальное множество точек, одновременного вложения нескольких графов и послойного рисования графа[2].

Связанные семейства графов

Некоторые классы планарных графов в обязательном порядке гамильтоновы, а потому и подгамильтоновы. Сюда входят вершинно 4-связные графы[7] и графы Халина[8] .

Любой планарный граф с максимальной степенью, не превосходящей четырёх, является подгамильтоновым[4], как и любой планарный граф без разделяющих треугольников[9][10]. Если рёбра произвольного планарного графа разбиты на пути длины два[11], получившийся граф всегда подгамильтонов[2].

Примечания

  1. ↑ Heath, 1987, с. 198–218.
  2. ↑ 1 2 3 4 Di Giacomo, Liotta, 2010, с. 35–46.
  3. ↑ Например, в техническом отчёте 2003 года "Book embeddings of graphs and a theorem of Whitney Архивная копия от 29 августа 2017 на Wayback Machine", Пол Кайнен определяет подгамильтоновы графы как подграфы планарных гамильтоновых графов без ограничения множества вершин в расширенном графе, но пишет, что «в определении подгамильтонова графа можно потребовать, что расширение осуществляется только добавлением рёбер»
  4. ↑ 1 2 Bekos, Gronemann, Raftopoulou, 2014.
  5. ↑ Bernhart, Kainen, 1979.
  6. ↑ Bernhart, Kainen, 1979, с. 320–331.
  7. ↑ Nishizeki, Chiba, 2008, с. 171–184.
  8. ↑ Cornuéjols, Naddef, Pulleyblank, 1983, с. 287–294.
  9. ↑ Kainen, Overbay, 2007, с. 835–837.
  10. ↑ Разделяющий треугольник — это подграф, содержащий три вершины и три ребра, удаление которого (вместе со смежными рёбрами) приводит к разбиению графа на несвязные части (Duncan, Goodrich, Kobourov 2003).
  11. ↑ То есть каждое ребро преобразовано в два ребра путём помещения на ребро вершины.

Литература

  • Lenwood S. Heath. Embedding outerplanar graphs in small books // SIAM Journal on Algebraic and Discrete Methods. — 1987. — Т. 8, вып. 2. — С. 198–218. — doi:10.1137/0608018.
  • Emilio Di Giacomo, Giuseppe Liotta. WALCOM: Algorithms and Computation, 4th International Workshop, WALCOM 2010, Dhaka, Bangladesh, February 10-12, 2010, Proceedings. — Berlin: Springer, 2010. — Т. 5942. — С. 35–46. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-11440-3_4.
  • Frank R. Bernhart, Paul C. Kainen. The book thickness of a graph // Journal of Combinatorial Theory. — 1979. — Т. 27, вып. 3. — С. 320–331. — doi:10.1016/0095-8956(79)90021-2.
  • Takao Nishizeki, Norishige Chiba,. Planar Graphs: Theory and Algorithms. — Courier Dover Publications, 2008. — С. 171–184. — (Dover Books on Mathematics). — ISBN 9780486466712.
  • G. Cornuéjols, D. Naddef, W. R. Pulleyblank. Halin graphs and the travelling salesman problem // Mathematical Programming. — 1983. — Т. 26, вып. 3. — С. 287–294. — doi:10.1007/BF02591867.
  • Michael A. Bekos, Martin Gronemann, Chrysanthi N. Raftopoulou. STACS. — 2014.
  • Paul C. Kainen, Shannon Overbay. Extension of a theorem of Whitney // Applied Mathematics Letters. — 2007. — Т. 20, вып. 7. — С. 835–837. — doi:10.1016/j.aml.2006.08.019.
  • Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov. Planarity-Preserving Clustering and Embedding for Large Planar Graphs // Computational Geomenty. — Elsevier, 2003. — Вып. 24.