Подгамильтонов граф — это подграф планарного гамильтонова графа[1][2].
Определение
Граф G является подгамильтоновым, если G является подграфом некоторого другого графа aug(G) с тем же множеством вершин, при этом граф aug(G) планарен и содержит гамильтонов цикл. Чтобы эти условия выполнялись, сам граф G должен быть планарным и, кроме того, должна существовать возможность добавить рёбра с сохранением планарности, чтобы создать цикл в расширенном графе, проходящий все вершины ровно один раз. Граф aug(G) называется гамильтоновым расширением графа G[2].
Можно было бы дать определение подгамильтонова графа как подграфа гамильтонова графа без требования, что этот больший граф имеет то же самое множество вершин. То есть в этом альтернативном определении можно было бы добавлять вершины и рёбра. Однако, если граф может быть сделан гамильтоновым с помощью добавления вершин и рёбер, его можно сделать таковым и без добавления вершин, так что эта дополнительная свобода не меняет определение[3]
В подгамильтоновом графе подгамильтонов цикл — это циклическая последовательность вершин, такая, что добавление ребра в любую пару вершин в последовательности не нарушает планарности графа. Граф является подгамильтоновым тогда и только тогда, когда он имеет подгамильтонов цикл[4].
История и приложения
Класс подгамильтоновых графов (но не имя класса) предложили Бернхарт и Кайнен[5]. Они доказали, что это в точности те графы, которые имеют две страницы в книжных вложениях[6]. Подгамильтоновы графы и гамильтоновы расширения использовались также в области визуализации графов для задач вложения графов в универсальное множество точек, одновременного вложения[en] нескольких графов и многоуровневого представления графа[en][2].
Связанные семейства графов
Некоторые классы планарных графов в обязательном порядке гамильтоновы, а потому и подгамильтоновы. Сюда входят вершинно 4-связные графы[7] и графы Халина[8] .
Любой планарный граф с максимальной степенью, не превосходящей четырёх, является подгамильтоновым[4], как и любой планарный граф без разделяющих треугольников[9][10]. Если рёбра произвольного планарного графа разбиты на пути длины два[11], получившийся граф всегда подгамильтонов[2].
Примечания
- ↑ Heath, 1987, с. 198–218.
- 1 2 3 4 Di Giacomo, Liotta, 2010, с. 35–46.
- ↑ Например, в техническом отчёте 2003 года "Book embeddings of graphs and a theorem of Whitney", Пол Кайнен определяет подгамильтоновы графы как подграфы планарных гамильтоновых графов без ограничения множества вершин в расширенном графе, но пишет, что «в определении подгамильтонова графа можно потребовать, что расширение осуществляется только добавлением рёбер»
- 1 2 Bekos, Gronemann, Raftopoulou, 2014.
- ↑ Bernhart, Kainen, 1979.
- ↑ Bernhart, Kainen, 1979, с. 320–331.
- ↑ Nishizeki, Chiba, 2008, с. 171–184.
- ↑ Cornuéjols, Naddef, Pulleyblank, 1983, с. 287–294.
- ↑ Kainen, Overbay, 2007, с. 835–837.
- ↑ Разделяющий треугольник — это подграф, содержащий три вершины и три ребра, удаление которого (вместе со смежными рёбрами) приводит к разбиению графа на несвязные части (Duncan, Goodrich, Kobourov 2003).
- ↑ То есть каждое ребро преобразовано в два ребра путём помещения на ребро вершины.
Литература
- 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.
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .