В теории графов , разделе математики, вершинный граф — это граф , который можно сделать плоским , удалив одну вершину . Удаленная вершина называется вершиной графа. Это вершина , а не вершина , поскольку вершинный граф может иметь более одной вершины; например, в минимальных непланарных графах 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-хроматических вершинных графов, такой контрпример не может существовать.
Каждый ли 6-связный K 6 -минорный граф является вершинным графом?
Йоргенсен (1994) предположил, что каждый 6-связный граф, не имеющий K 6 в качестве минора, должен быть вершинным графом. Если бы это было доказано, непосредственным следствием стал бы результат Робертсона-Сеймура-Томаса по гипотезе Хадвигера. [2] Гипотеза Йоргенсена остается недоказанной. [9] Однако, если оно неверно, оно имеет лишь конечное число контрпримеров. [10]
Семейство графов F имеет ограниченную локальную ширину дерева, если графы в F подчиняются функциональному соотношению между диаметром и шириной дерева : существует функция f такая, что ширина дерева графа диаметра d в F не превышает f ( d ) . Вершинные графы не имеют ограниченной локальной ширины дерева: вершинные графы, образованные путем соединения вершинной вершины с каждой вершиной сеточного графа размера n × n , имеют ширину дерева n и диаметр 2, поэтому ширина дерева не ограничена функцией диаметра для этих графов. . Однако вершинные графы тесно связаны с ограниченной локальной шириной дерева: семейства F замкнутых минорных графов , которые имеют ограниченную локальную ширину дерева, являются именно теми семьями, у которых вершинный граф является одним из запрещенных миноров. [4] Семейство минорно-замкнутых графов, в котором вершинный граф является одним из запрещенных миноров, называется Apex-minor-free . Используя эту терминологию, связь между вершинными графами и шириной локального дерева можно переформулировать как тот факт, что семейства графов без вершинных миноров — это то же самое, что семейства графов с ограниченной локальной шириной дерева.
Концепция ограниченной локальной ширины дерева формирует основу теории двумерности и позволяет решать многие алгоритмические проблемы на графах без вершинных миноров точно с помощью алгоритма с полиномиальным временем или управляемого алгоритма с фиксированным параметром или аппроксимировать с помощью схема полиномиальной аппроксимации . [11] Семейства графов без вершинных миноров подчиняются усиленной версии теоремы о структуре графа , что приводит к дополнительным алгоритмам аппроксимации для раскраски графов и задачи коммивояжера . [12] Однако некоторые из этих результатов также могут быть распространены на произвольные минорно-замкнутые семейства графов с помощью структурных теорем, связывающих их с графами без вершин-миноров. [13]
Если G — вершинный граф с вершиной v , а τ — минимальное количество граней, необходимое для покрытия всех соседей v в плоском вложении G \ { v }, то G можно вложить в двумерную поверхность рода τ – 1 : просто добавьте это количество мостов к плоскому вложению, соединяя вместе все грани, с которыми должно быть связано v . Например, добавление одной вершины во внешнепланарный граф (граф с τ = 1 ) создает планарный граф. Когда G \ { v } 3-связен, его оценка находится в пределах постоянного фактора оптимальности: каждое поверхностное вложение G требует рода не менееτ/160. Однако NP-трудно определить оптимальный род поверхностного вложения вершинного графа. [14]
Используя деревья SPQR для кодирования возможных вложений планарной части вершинного графа, можно вычислить рисунок графа на плоскости, в котором единственные пересечения включают вершину вершины, минимизируя общее количество пересечений в полиномиальном виде. время. [15] Однако, если разрешены произвольные пересечения, становится NP-трудно минимизировать количество пересечений, даже в частном случае вершинных графов, образованных добавлением одного ребра к планарному графу. [16]
Графы Apex также встраиваются без связей в трехмерное пространство: их можно встроить таким образом, что каждый цикл в графе является границей диска, который не пересекает какой-либо другой элемент графа. [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 вершиной также называется вершинным.
По данным Липтона и др. (2018), граф является вершинно-реберным, если в графе есть какое-то ребро, которое можно удалить, чтобы сделать граф плоским. Граф называется сжимающейся вершиной, если в графе есть какое-то ребро, которое можно сжать, чтобы сделать граф плоским.
В общем, если X — класс графов, граф «вершина- X » — это граф, который можно перевести в класс X , удалив какую-то одну вершину. Например, апексограф — это граф G , имеющий вершину v такую, что G—v — кограф.
