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

Подгамильтонов граф — это подграф планарного гамильтонова графа[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. Di Giacomo, Liotta, 2010, с. 35–46.
  3. Например, в техническом отчёте 2003 года "Book embeddings of graphs and a theorem of Whitney", Пол Кайнен определяет подгамильтоновы графы как подграфы планарных гамильтоновых графов без ограничения множества вершин в расширенном графе, но пишет, что «в определении подгамильтонова графа можно потребовать, что расширение осуществляется только добавлением рёбер»
  4. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.