В теории графов верхушечный граф — это граф, который можно сделать планарным удалением одной вершины. Удалённая вершина называется верхушкой графа. Заметим, что верхушка может быть не одна. Например, в минимальном непланарном графе K ₅ или K _3,3 каждая вершина является верхушкой. Верхушечные графы включают изначально планарные графы, в которых каждая вершина является верхушкой. Нуль-граф считается также верхушечным, хотя в нём нет вершин для удаления .

Верхушечные графы замкнуты относительно операции образования миноров и играют большую роль в некоторых других аспектах теории миноров графов, включая незацепленное вложение , гипотезу Хадвигера , YΔY-сводимые графы и связь между древесной шириной и диаметром графа .

Описание и распознавание

Верхушечные графы замкнуты относительно операции образования миноров — стягивание любого ребра или удаление вершины или ребра приводит к другому верхушечному графу. Действительно, если граф G является верхушечным с верхушкой v , то стягивание или удаление, не затрагивающее вершину v , сохраняет планарность остального графа (без вершины v ). то же самое верно и при удалении любого ребра, инцидентного v . Если стягивается ребро, инцидентное v , эффект эквивалентен удалению противоположного конца ребра. Если же удаляется сама вершина v , любую другую вершину можно считать верхушкой .

Поскольку верхушечные графы замкнуты по операции образования миноров, по теореме Робертсона – Сеймура они имеют характеризацию запрещёнными графами . Существует лишь конечное число графов, которые не являются верхушечными графами и не содержат в качестве минора другой граф, не являющийся верхушечным. Эти графы являются запрещёнными минорами для свойства «верхушечный граф». Любой другой граф G является верхушечным тогда и только тогда, когда ни один из запрещённых миноров не является минором графа G . Запрещённые миноры включают семь графов из петерсенова семейства , три несвязных графа, образованных из непересекающихся объединений K ₅ и K _3,3 и много других графов. Полный список всех запрещённых миноров остаётся незавершённым .

Несмотря на то, что полный список запрещённых миноров не известен, есть возможность за линейное время проверить, является ли данный граф верхушечным, и если он таковой, найти верхушку графа . Более обще, для любой фиксированной константы k можно за линейное время распознать k -верхушечные графы (графы, в которых удаление аккуратно выбранного множества, содержащего не более k вершин, приводит к планарному графу ). Однако, если k не фиксировано, задача становится NP-полной .

Хроматическое число

Любой верхушечный граф имеет хроматическое число , не превосходящее пяти — планарный граф без верхушки требует не более четырёх цветов по теореме о четырёх красках , а для верхушки достаточно одного добавочного цвета. Робертсон, Сеймур и Томас использовали этот факт для доказательства случая k = 6 гипотезы Хадвигера , утверждения, что любой 6-хроматический граф имеет полный граф K ₆ в качестве минора — они показали, что любой минимальный контрпример гипотезе должен быть верхушечным графом, но верхушечных 6-хроматических графов нет, так что такого контрпримера не существует.

Йоргенсен высказал гипотезу, что любой вершинно 6-связный граф, не имеющий в качестве миноров K ₆ , должен быть верхушечным. Если бы это было доказано, результат Робертсона – Сеймура – Томаса для гипотезы Хадвигера стал бы прямым следствием . Гипотеза Йоргенсена пока не доказана . Однако если гипотеза не верна, она имеет лишь конечное число контрпримеров .

Локальная древесная ширина

Семейство графов F имеет ограниченную локальную древесную ширину , если графы из F подчиняются функциональной зависимостью между диаметром и древесной шириной — существует функция ƒ, такая, что древесная ширина графа из F с диаметром d не превосходит ƒ( d ). Верхушечные графы не имеют ограниченной локальной древесной ширины — граф, образованный соединением верхушки с каждой вершиной n × n решётки имеет древесную ширину n и диаметр 2, так что древесная ширина не ограничена некоторой функцией от диаметра этих графов. Однако верхушечные графы тесно связаны с графами с ограниченной локальной древесной шириной — замкнутые по минорам семейства графов F , имеющие ограниченную локальную древесную ширину, являются в точности семействами, одним из запрещённых миноров которых является какой-либо верхушечный граф . Замкнутые по минорам семейства графов, имеющие верхушечный граф в качестве минора, известны как свободные от верхушечного минора . Согласно этой терминологии связь между верхушечными графами и локальной древесной шириной можно переформулировать так: семейства графов, свободных от верхушечных миноров, совпадают с семействами замкнутых по минорам графов с ограниченной локальной древесной шириной.

Концепция ограниченной локальной древесной ширины образует базис теории ^* и позволяют решать многие алгоритмические задачи на свободных от верхушечных миноров графах в точности алгоритмом полиномиального времени, или алгоритмом, или задача может быть приближена с помощью приближенной схемы полиномиального времени . Для свободных от верхушечных миноров семейств графов выполняется усиленная версия структурной теоремы графов , что приводит к дополнительным аппроксимационным алгоритмам для раскраски графов и для задачи коммивояжёра . Однако некоторые из этих результатов могут быть распространены на произвольные замкнутые по минорам семейства графов с помощью использования структурных теорем на связанные с семействами свободные от верхушечных миноров графы .

Вложения

Если граф G является верхушечным графом с верхушкой v и ${\displaystyle \tau }$ равно минимальному числу граней, необходимых для покрытия всех соседей верхушки v при планарном вложении G \{ v }, то G может быть вложено в двумерную поверхность рода ${\displaystyle \tau -1}$ путём добавления такого числа мостов к планарному вложению, соединив тем самым все грани, с которыми верхушка v должна быть соединена. Например, добавление одной вершины к внешнепланарному графу (графу с a ${\displaystyle \tau =1}$ ) даёт планарный граф. Если граф G \{ v } 3-связен, его граница не отличается от оптимальной более чем на постоянный множитель — любое вложение G в поверхность требует род по меньшей мере ${\displaystyle \tau /160}$ . Однако задача определения оптимального рода для поверхности вложения для верхушечных графов является NP-трудной задачей .

При использовании SPQR-деревьев для кодировки возможных вложений планарной части верхушечного графа, можно вычислить за полиномиальное время укладку графа на плоскость, в которой пересечения вызваны только рёбрами, исходящими из верхушечной вершины, и общее число пересечений минимально . Если разрешены произвольные пересечения, задача минимизации числа пересечений становится NP-трудной задачей даже в специальном случае верхушечных графов, образованных добавлением одного ребра в планарный граф .

Верхушечные графы вложимы без зацепления в трёхмерное пространство — их можно вложить так, что любой цикл в графе является границей диска, который не пересекается любой другой частью графа . Рисунок такого типа можно получить, нарисовав планарную часть графа на плоскости, поместив верхушку графа над плоскостью, и соединив её с соседями отрезками. Вложимые без зацеплений графы образуют замкнутое по минорам семейство с семью графами из петерсенова семейства в качестве минимальных запрещённых миноров . Таким образом, эти графы являются запрещёнными минорами и для верхушечных графов. Существуют, однако, вложимые без зацепления графы, не являющиеся верхушечными.

YΔY-сводимость

Связный граф является YΔY-сводимым, если он может быть сведён к одиночной вершине последовательностью шагов, каждый из которых является Δ-Y или Y-Δ преобразованием , удалением петли или кратных рёбер, удалением вершины с одним соседом и заменой вершины степени два и двух её смежных рёбер одним ребром .

Подобно верхушечным графам и вложимым без зацепления графам YΔY-сводимые графы замкнуты относительно операции образования миноров. Подобно вложимым без зацепления графам YΔY-сводимые графы имеют семь графов из петерсенова семейства в качестве минимальных запрещённых миноров, откуда возникает вопрос, не являются ли только эти графы запрещёнными минорами и не совпадают ли семейства YΔY-сводимых графов и вложимых без зацепления графов. Нейл Робертсон, однако, привёл пример верхушечного графа, не являющегося YΔY-сводимым. Поскольку любой верхушечный граф вложим без зацепления, это показывает, что существуют вложимые без зацепления графы, не являющиеся YΔY-сводимыми, а потому существуют дополнительные запрещённые миноры для YΔY-сводимых графов .

Верхушечный граф Робертсона показан на рисунке. Его можно получить соединением верхушки со всеми вершинами степени три ромбододекаэдра или путём слияния двух противоположных вершин графа четырёхмерного гиперкуба . Поскольку граф ромбододекаэдра планарен, граф Робертсона является верхушечным. Граф не содержит треугольников и имеет минимальную степень четыре, так что к нему нельзя применить любую операцию YΔY-сведения .

Почти планарные графы

Если граф является верхушечным, не обязательно у него единственная верхушка. Например, в минорно минимальных непланарных графах K ₅ и K _3,3 любую вершину можно выбрать в качестве верхушки. Вагнер определил почти планарный граф как непланарный верхушечный граф, в котором любая вершина может служить верхушкой. Таким образом, K ₅ и K _3,3 являются почти планарными графами. Он дал классификацию таких графов, разделив их на четыре семейства. Одно семейство состоит из графов, которые (подобно лестницам Мёбиуса ) могут быть вложены в ленту Мёбиуса таким образом, что край ленты совпадает с гамильтоновым циклом графа. Ещё до доказательства теоремы четырёх красок он доказал, что любой почти планарный граф может быть раскрашен, не превышая четырёх цветов, за исключением графов, образованных из колеса с нечётным внешним циклом путём замены центральной вершины двумя смежными вершинами — для такого графа нужно пять красок. Кроме того, он доказал, что, за одним исключением (восьмивершинного дополнения куба ), любой почти планарный граф имеет вложение в проективную плоскость .

Однако фраза «почти планарный граф» в высокой степени неоднозначна — тот же термин использовался для верхушечных графов , графов, образованных добавлением одного ребра к планарному графу , графов, образованных из планарного вложения графа заменой ограниченного числа граней «вихрями» ограниченной путевой ширины , а также некоторых других менее строго определённых множеств графов.

Примечания

Литература