В теории графов , разделе математики, граф вершин — это граф , который можно сделать планарным путем удаления одной вершины . Удаленная вершина называется вершиной графа. Это вершина , а не вершина , потому что граф вершин может иметь более одной вершины; например, в минимальных непланарных графах K 5 или K 3,3 каждая вершина является вершиной. Графы вершин включают графы, которые сами являются планарными, и в этом случае снова каждая вершина является вершиной. Нулевой граф также считается графом вершин, даже если у него нет вершины для удаления.
Графы вершин замкнуты относительно операции взятия миноров и играют роль в нескольких других аспектах теории миноров графов: вложение без связей , [1] гипотеза Хадвигера , [2] YΔY-сводимые графы, [3] и соотношения между шириной дерева и диаметром графа . [4]
Графы вершин замкнуты относительно операции взятия миноров : стягивание любого ребра или удаление любого ребра или вершины приводит к другому графу вершин. Так как, если G является графом вершин с вершиной v , то любое стягивание или удаление, которое не затрагивает v, сохраняет планарность оставшегося графа, как и любое удаление ребра, инцидентного v . Если ребро, инцидентное v, стягивается, эффект на оставшийся граф эквивалентен удалению другой конечной точки ребра. И если сама v удалена, любая другая вершина может быть выбрана в качестве вершины. [5]
По теореме Робертсона–Сеймура , поскольку они образуют замкнутое по минорам семейство графов, верхушечные графы имеют характеристику запрещённого графа . Существует только конечное число графов, которые не являются ни верхушечными графами, ни имеют другой не верхушечный граф в качестве минора. Эти графы являются запрещёнными минорами по свойству быть верхушечным графом. Любой другой граф G является верхушечным графом тогда и только тогда, когда ни один из запрещённых миноров не является минором G. Эти запрещённые миноры включают семь графов семейства Петерсена , три несвязных графа, образованных из несвязных объединений двух из K 5 и K 3,3 , и многие другие графы. Однако полное описание их остаётся неизвестным. [5] [6]
Несмотря на то, что полный набор запрещенных миноров остается неизвестным, можно проверить, является ли заданный граф графом вершин, и если да, то найти вершину для графа за линейное время . В более общем случае, для любой фиксированной константы k можно распознать за линейное время k -графы вершин , графы, в которых удаление некоторого тщательно выбранного набора из не более чем k вершин приводит к планарному графу. [7] Однако, если k является переменным, задача является NP-полной . [8]
Каждый вершинный граф имеет хроматическое число не более пяти: базовый планарный граф требует не более четырех цветов по теореме о четырех цветах , а оставшаяся вершина требует не более одного дополнительного цвета. Робертсон, Сеймур и Томас (1993a) использовали этот факт в своем доказательстве случая k = 6 гипотезы Хадвигера , утверждения о том, что каждый 6-хроматический граф имеет полный граф K 6 в качестве минора: они показали, что любой минимальный контрпример к гипотезе должен был бы быть вершинным графом, но поскольку не существует 6-хроматических вершинных графов, такой контрпример не может существовать.
Йоргенсен (1994) предположил, что любой 6-вершинно-связный граф, не имеющий K 6 в качестве минора, должен быть графом вершины. Если бы это было доказано, результат Робертсона–Сеймура–Томаса о гипотезе Хадвигера был бы непосредственным следствием. [2] Гипотеза Йоргенсена остается недоказанной. [9] Однако, если она ложна, то имеет лишь конечное число контрпримеров. [10]
Семейство графов F имеет ограниченную локальную древесную ширину , если графы в F подчиняются функциональному соотношению между диаметром и древесной шириной : существует функция f такая, что древесная ширина графа диаметром d в F не превышает f ( d ) . Графы вершин не имеют ограниченной локальной древесной ширины: графы вершин, образованные путем соединения вершины с каждой вершиной графа сетки n × n , имеют древесную ширину n и диаметр 2, поэтому древесная ширина не ограничена функцией диаметра для этих графов. Однако графы вершин тесно связаны с ограниченной локальной древесной шириной: семейства графов F с замкнутыми минорами , имеющие ограниченную локальную древесную ширину, являются в точности теми семействами, которые имеют граф вершины в качестве одного из своих запрещенных миноров. [4] Семейство графов с замкнутыми минорами, которое имеет граф вершины в качестве одного из своих запрещенных миноров, известно как семейство графов без миноров . Используя эту терминологию, связь между графами вершин и локальной шириной дерева можно переформулировать как тот факт, что семейства графов без вершин и миноров совпадают с семействами графов с замкнутыми минорами и ограниченной локальной шириной дерева.
Концепция ограниченной локальной ширины дерева составляет основу теории двумерности и позволяет решать многие алгоритмические проблемы на графах без апекс-миноров точно с помощью алгоритма с полиномиальным временем или алгоритма с фиксированными параметрами , а также аппроксимировать их с помощью аппроксимационной схемы с полиномиальным временем . [11] Семейства графов без апекс-миноров подчиняются усиленной версии теоремы о структуре графа , что приводит к дополнительным алгоритмам аппроксимации для раскраски графа и задачи коммивояжера . [12] Однако некоторые из этих результатов можно распространить на произвольные семейства графов с замкнутыми минорами с помощью структурных теорем, связывающих их с графами без апекс-миноров. [13]
Если G — вершинный граф с вершиной v , а τ — минимальное число граней, необходимое для покрытия всех соседей v в плоском вложении G \ { v }, то G может быть вложен в двумерную поверхность рода τ – 1 : просто добавьте это число мостов к плоскому вложению, соединяя вместе все грани, в которые должен быть включён v . Например, добавление одной вершины к внешнепланарному графу (графу с τ = 1 ) даёт плоский граф. Когда G \ { v } является 3-связным, его граница находится в пределах постоянного множителя оптимальности: каждое поверхностное вложение G требует рода по крайней мере τ/160 . Однако, NP-трудно определить оптимальный род поверхностного вложения графа вершины. [14]
Используя деревья SPQR для кодирования возможных вложений плоской части графа вершин, можно вычислить рисунок графа на плоскости, в котором единственные пересечения включают вершину вершины, минимизируя общее количество пересечений за полиномиальное время. [15] Однако, если разрешены произвольные пересечения, становится NP-трудно минимизировать количество пересечений, даже в особом случае графов вершин, образованных путем добавления одного ребра к плоскому графу. [16]
Графы вершин также являются беззвеньевыми вложимыми в трехмерное пространство: они могут быть вложены таким образом, что каждый цикл в графе является границей диска, который не пересекается никакой другой особенностью графа. [17] Рисунок этого типа может быть получен путем рисования плоской части графа на плоскости, размещения вершины над плоскостью и соединения вершины прямолинейными ребрами с каждым из ее соседей. Беззвеньевые вложимые графы образуют замкнутое по минорам семейство с семью графами в семействе Петерсена в качестве их минимальных запрещенных миноров; [1] поэтому эти графы также запрещены как миноры для графов вершин. Однако существуют беззвеньевые вложимые графы, которые не являются графами вершин.
Связный граф является YΔY-приводимым, если его можно свести к одной вершине с помощью последовательности шагов, каждый из которых является преобразованием Δ-Y или Y-Δ , удалением петли или множественной смежности, удалением вершины с одним соседом и заменой вершины степени два и двух ее соседних ребер одним ребром. [3]
Подобно графам вершин и вкладываемым графам без зацеплений, YΔY-сводимые графы замкнуты относительно миноров графов. И, подобно вкладываемым графам без зацеплений, YΔY-сводимые графы имеют семь графов в семействе Петерсена в качестве запрещенных миноров, что вызывает вопрос о том, являются ли они единственными запрещенными минорами и являются ли YΔY-сводимые графы такими же, как вкладываемые графы без зацеплений. Однако Нил Робертсон привел пример графа вершин, который не является YΔY-сводимым. Поскольку каждый граф вершин является вкладываемым графом без зацеплений, это показывает, что существуют графы, которые являются вкладываемыми графами без зацеплений, но не YΔY-сводимыми, и, следовательно, существуют дополнительные запрещенные миноры для YΔY-сводимых графов. [3]
Граф вершин Робертсона показан на рисунке. Его можно получить, соединив вершину вершины с каждой из вершин степени три ромбического додекаэдра или объединив две диаметрально противоположные вершины четырехмерного графа гиперкуба . Поскольку граф ромбического додекаэдра является плоским, граф Робертсона является графом вершины. Это граф без треугольников с минимальной степенью четыре, поэтому его нельзя изменить никаким YΔY-сокращением. [3]
Если граф является графом вершин, то не обязательно, что он имеет единственную вершину. Например, в минорно-минимальных непланарных графах K 5 и K 3,3 любая из вершин может быть выбрана в качестве вершины. Вагнер (1967, 1970) определил почти планарный граф как непланарный граф вершин со свойством, что все вершины могут быть вершинами графа; таким образом, K 5 и K 3,3 являются почти планарными. Он предоставил классификацию этих графов на четыре подмножества, одно из которых состоит из графов, которые (подобно лестницам Мёбиуса ) могут быть вложены в ленту Мёбиуса таким образом, что единственное ребро ленты совпадает с гамильтоновым циклом графа. До доказательства теоремы о четырех красках он доказал, что любой почти планарный граф может быть раскрашен максимум четырьмя цветами, за исключением графов, образованных из графа-колеса с нечетным внешним циклом путем замены вершины концентратора двумя смежными вершинами, что требует пяти цветов. Кроме того, он доказал, что, за единственным исключением (восьмивершинный дополнительный граф куба ) , любой почти планарный граф имеет вложение в проективную плоскость .
Однако фраза «почти планарный граф» весьма неоднозначна: она также использовалась для обозначения вершинных графов [18] , графов, образованных путем добавления одного ребра к планарному графу [19], и графов, образованных из планарного вложенного графа путем замены ограниченного числа граней «вихрями» ограниченной ширины пути [20] , а также для других менее точно определенных наборов графов.
Абстрактный граф называется n- вершинным, если его можно сделать планарным, удалив n или меньше вершин. Граф с 1 вершиной также называется вершинным.
Согласно Lipton et al. (2018), граф является ребро-вершинным, если в графе есть некоторое ребро, которое можно удалить, чтобы сделать граф планарным. Граф является стягивающим-вершинным, если в графе есть некоторое ребро, которое можно стянуть, чтобы сделать граф планарным.
В общем случае, если X — класс графов, то граф «apex- X » — это граф, который можно перенести в класс X , удалив одну вершину. Например, apex- cograph — это граф G , имеющий вершину v, такую, что G―v — кограф.
