Подгамильтонов граф — это подграф планарного гамильтонова графа.
Определение Граф G является подгамильтоновым, если G является подграфом некоторого другого графа aug(G) с тем же множеством вершин, при этом граф aug(G) планарен и содержит гамильтонов цикл. Чтобы эти условия выполнялись, сам граф G должен быть планарным и, кроме того, должна существовать возможность добавить рёбра с сохранением планарности, чтобы создать цикл в расширенном графе, проходящий все вершины ровно один раз. Граф aug(G) называется гамильтоновым расширением графа G.
Можно было бы дать определение подгамильтонова графа как подграфа гамильтонова графа без требования, что этот больший граф имеет то же самое множество вершин. То есть в этом альтернативном определении можно было бы добавлять вершины и рёбра. Однако, если граф может быть сделан гамильтоновым с помощью добавления вершин и рёбер, его можно сделать таковым и без добавления вершин, так что эта дополнительная свобода не меняет определениеНапример, в техническом отчёте 2003 года "Book embeddings of graphs and a theorem of Whitney ", Пол Кайнен определяет подгамильтоновы графы как подграфы планарных гамильтоновых графов без ограничения множества вершин в расширенном графе, но пишет, что «в определении подгамильтонова графа можно потребовать, что расширение осуществляется только добавлением рёбер»
В подгамильтоновом графе подгамильтонов цикл — это циклическая последовательность вершин, такая, что добавление ребра в любую пару вершин в последовательности не нарушает планарности графа. Граф является подгамильтоновым тогда и только тогда, когда он имеет подгамильтонов цикл.
История и приложения Класс подгамильтоновых графов (но не имя класса) предложили Бернхарт и Кайнен. Они доказали, что это в точности те графы, которые имеют две страницы в книжных вложениях. Подгамильтоновы графы и гамильтоновы расширения использовались также в области визуализации графов для задач вложения графов в универсальное множество точек, одновременного вложения нескольких графов и послойного рисования графа.
Связанные семейства графов Некоторые классы планарных графов в обязательном порядке гамильтоновы, а потому и подгамильтоновы. Сюда входят вершинно 4-связные графы и графы Халина .
Любой планарный граф с максимальной степенью, не превосходящей четырёх, является подгамильтоновым, как и любой планарный граф без разделяющих треугольниковРазделяющий треугольник — это подграф, содержащий три вершины и три ребра, удаление которого (вместе со смежными рёбрами) приводит к разбиению графа на несвязные части .. Если рёбра произвольного планарного графа разбиты на пути длины дваТо есть каждое ребро преобразовано в два ребра путём помещения на ребро вершины., получившийся граф всегда подгамильтонов.
Примечания
Литература
Категория:Семейства графов Категория:Планарные графы Категория:Гамильтоновы пути и циклы