Interested Article - Подгамильтонов граф
- 2020-09-29
- 1
Подгамильтонов граф — это подграф планарного гамильтонова графа .
Определение
Граф G является подгамильтоновым, если G является подграфом некоторого другого графа aug( G ) с тем же множеством вершин, при этом граф aug( G ) планарен и содержит гамильтонов цикл . Чтобы эти условия выполнялись, сам граф G должен быть планарным и, кроме того, должна существовать возможность добавить рёбра с сохранением планарности, чтобы создать цикл в расширенном графе, проходящий все вершины ровно один раз. Граф aug( G ) называется гамильтоновым расширением графа G .
Можно было бы дать определение подгамильтонова графа как подграфа гамильтонова графа без требования, что этот больший граф имеет то же самое множество вершин. То есть в этом альтернативном определении можно было бы добавлять вершины и рёбра. Однако, если граф может быть сделан гамильтоновым с помощью добавления вершин и рёбер, его можно сделать таковым и без добавления вершин, так что эта дополнительная свобода не меняет определение
В подгамильтоновом графе подгамильтонов цикл — это циклическая последовательность вершин, такая, что добавление ребра в любую пару вершин в последовательности не нарушает планарности графа. Граф является подгамильтоновым тогда и только тогда, когда он имеет подгамильтонов цикл .
История и приложения
Класс подгамильтоновых графов (но не имя класса) предложили Бернхарт и Кайнен . Они доказали, что это в точности те графы, которые имеют две страницы в книжных вложениях . Подгамильтоновы графы и гамильтоновы расширения использовались также в области визуализации графов для задач вложения графов в универсальное множество точек , одновременного вложения нескольких графов и послойного рисования графа .
Связанные семейства графов
Некоторые классы планарных графов в обязательном порядке гамильтоновы, а потому и подгамильтоновы. Сюда входят вершинно 4-связные графы и графы Халина .
Любой планарный граф с максимальной степенью , не превосходящей четырёх, является подгамильтоновым , как и любой планарный граф без разделяющих треугольников . Если рёбра произвольного планарного графа разбиты на пути длины два , получившийся граф всегда подгамильтонов .
Примечания
- , с. 198–218.
- ↑ , с. 35–46.
- Например, в техническом отчёте 2003 года " от 29 августа 2017 на Wayback Machine ", Пол Кайнен определяет подгамильтоновы графы как подграфы планарных гамильтоновых графов без ограничения множества вершин в расширенном графе, но пишет, что «в определении подгамильтонова графа можно потребовать, что расширение осуществляется только добавлением рёбер»
- ↑ .
- .
- , с. 320–331.
- , с. 171–184.
- , с. 287–294.
- , с. 835–837.
- Разделяющий треугольник — это подграф, содержащий три вершины и три ребра, удаление которого (вместе со смежными рёбрами) приводит к разбиению графа на несвязные части ( ).
- То есть каждое ребро преобразовано в два ребра путём помещения на ребро вершины.
Литература
- Lenwood S. Heath. Embedding outerplanar graphs in small books // SIAM Journal on Algebraic and Discrete Methods. — 1987. — Т. 8 , вып. 2 . — С. 198–218 . — doi : .
- 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 : .
- Frank R. Bernhart, Paul C. Kainen. The book thickness of a graph // Journal of Combinatorial Theory . — 1979. — Т. 27 , вып. 3 . — С. 320–331 . — doi : .
- 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 : .
- 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 : .
- Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov. Planarity-Preserving Clustering and Embedding for Large Planar Graphs // Computational Geomenty. — Elsevier, 2003. — Вып. 24 .
- 2020-09-29
- 1