График вершины

Вершинный график. Подграф , образованный удалением красной вершины, является плоским .

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

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

Характеристика и признание

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

По теореме Робертсона-Сеймура , поскольку они образуют минорно-замкнутое семейство графов, вершинные графы имеют запрещенную характеристику графа .Существует лишь конечное число графов, которые не являются ни вершинными графами, ни имеют другой невершинный граф в качестве минорного.Эти графы являются запрещенными минорами из-за свойства быть вершинным графом.Любой другой граф G является вершинным графом тогда и только тогда, когда ни один из запрещенных миноров не является минором графа G .К этим запрещенным минорам относятся семь графов семейства Петерсена , три несвязных графа, образованных из непересекающихся объединений двух K ₅ и K _3,3 , и многие другие графы. Однако полное их описание остается неизвестным.

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

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

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

Нерешенная задача по математике :

Каждый ли 6-связный K ₆ -минорный граф является вершинным графом?

(еще нерешенные задачи по математике)

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

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

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

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

Вложения

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

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

Графы Apex также встраиваются без связей в трехмерное пространство: их можно встроить таким образом, что каждый цикл в графе является границей диска, который не пересекает какой-либо другой элемент графа. Рисунок такого типа можно получить, нарисовав плоскую часть графа на плоскости, поместив вершину над плоскостью и соединив вершину прямыми ребрами с каждым из своих соседей. Бессвязно встраиваемые графы образуют минорно-замкнутое семейство, в котором семь графов семейства Петерсена являются минимальными запрещенными минорами; следовательно, эти графы также запрещены как миноры для вершинных графов. Однако существуют бессвязно встраиваемые графы, которые не являются вершинными графами.

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

Пример Робертсона не-YΔY-приводимого вершинного графа.

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

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

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

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

с 16 вершинами Лестница Мёбиуса — пример почти плоского графа.

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

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

Связанные классы графов

Абстрактный граф называется n -вершинным, если его можно сделать плоским, удалив n или меньше вершин. Граф с 1 вершиной также называется вершинным.

По данным Липтона и др. (2018) , граф является вершинно-реберным, если в графе есть какое-то ребро, которое можно удалить, чтобы сделать граф плоским. Граф называется сжимающейся вершиной, если в графе есть какое-то ребро, которое можно сжать, чтобы сделать граф плоским.

В общем, если X — класс графов, граф «вершина- X » — это граф, который можно перевести в класс X , удалив какую-то одну вершину. Например, апексограф — это граф G , имеющий вершину v такую, что G—v — кограф.

См. также

• Многогранная пирамида , 4-мерный многогранник, вершины и ребра которого образуют вершинный граф, вершина которого примыкает к каждой вершине многогранного графа.

Ссылки

• Авраам, Иттай; Гавуа, Сирил (2006), «Расположение объекта с использованием разделителей путей», Proc. 25-й симпозиум ACM по принципам распределенных вычислений (PODC '06) , стр. 188–197, doi : 10.1145/1146381.1146411 , S2CID   8844836 .
• Архидиакон Дэн ; Боннингтон, КПК Пол (2004), «Препятствия для встраивания кубических графов на поверхность шпинделя», Журнал комбинаторной теории, серия B , 91 (2): 229–252, doi : 10.1016/j.jctb.2004.02.001 , hdl : 2292/5158 .
• Кабельо, Серджио; Мохар, Боян (2010), «Добавление одного ребра к планарным графам усложняет число пересечений», Proc. 26-й симпозиум ACM по вычислительной геометрии (SoCG '10) (PDF) , стр. 68–76, doi : 10.1145/1810959.1810972 , S2CID   17271180 , заархивировано из оригинала (PDF) 14 марта 2012 г. , получено 2 августа 2010 г. .
• Чимани, Маркус; Гутвенгер, Карстен; Мюцель, Петра ; Вольф, Кристиан (2009), «Вставка вершины в плоский граф», Proc. 20-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA '09) , стр. 375–383 .
• Демейн, Эрик Д .; Хаджиагайи, Мохаммад Таги (2004), «Диаметр и ширина дерева в семействах второстепенных замкнутых графов, пересмотренный», Algorithmica , 40 (3): 211–215, doi : 10.1007/s00453-004-1106-1 , S2CID   390856 .
• Демейн, Эрик Д .; Хаджиагайи, Мохаммад Таги (2005), «Двумерность: новые связи между алгоритмами FPT и PTAS», Proc. 16-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA '05) , стр. 590–601, заархивировано из оригинала 11 декабря 2018 г. , получено 2 августа 2010 г.
• Демейн, Эрик Д .; Хаджиагайи, Мохаммад Таги; Каварабаяши, Кен-ичи (2009), «Алгоритмы аппроксимации с помощью структурных результатов для графов без вершинных миноров» (PDF) , Proc. 36-й международный коллоквиум «Автоматы, языки и программирование» (ICALP '09) , Конспекты лекций по информатике, том. 5555, Springer-Verlag, стр. 316–327, номер документа : 10.1007/978-3-642-02927-1_27 .
• Эппштейн, Дэвид (2000), «Диаметр и ширина дерева в семействах младших замкнутых графов», Algorithmica , 27 (3): 275–291, arXiv : math.CO/9907126 , doi : 10.1007/s004530010020 , S2CID   3172160 .
• Фрик, Маркус; Гроэ, Мартин (2001), «Определение свойств первого порядка локально разложимых по дереву структур», Journal of the ACM , 48 (6): 1184–1206, arXiv : cs/0004007 , doi : 10.1145/504794.504798 , S2CID   999472 .
• Гроэ, Мартин (2003), «Локальная ширина дерева, исключенные миноры и алгоритмы аппроксимации», Combinatorica , 23 (4): 613–632, arXiv : math.CO/0001128 , doi : 10.1007/s00493-003-0037- 9 , S2CID   11751235 .
• Гупта, А.; Импальяццо, Р. (1991), "Вычисление плоских переплетений" , Proc. 32-й симпозиум IEEE по основам компьютерных наук (FOCS '91) , IEEE Computer Society, стр. 802–811, doi : 10.1109/SFCS.1991.185452 , S2CID   209133 .
• Йоргенсен, Лейф К. (1994), «Сокращение до K ₈ », Журнал теории графов , 18 (5): 431–448, doi : 10.1002/jgt.3190180502 . Цитируется Робертсоном, Сеймуром и Томасом ( 1993a , 1993c ).
• Каварабаяши, Кен-ичи (2009), «Планарность, допускающая небольшое количество ошибочных вершин за линейное время» (PDF) , Proc. 50-й симпозиум IEEE по основам информатики (FOCS '09) , IEEE Computer Society, стр. 639–648, doi : 10.1109/FOCS.2009.45 , S2CID   11647021 .
• Каварабаяси, Кеничи ; Норина, Сергей; Томас, Робин ; Воллан, Пол (2012), $K_{6}$ миноры в больших 6-связных графах , arXiv : 1203.2192 , Bibcode : 2012arXiv1203.2192K .
• Льюис, Джон М.; Яннакакис, Михалис (1980), «Проблема удаления узла для наследственных свойств является NP-полной», Journal of Computer and System Sciences , 20 (2): 219–230, doi : 10.1016/0022-0000(80)90060- 4 .
• Липтон, Макс; Макколл, Эоин; Мэттман, Томас В.; Пирс, Майк; Робинсон, Саманта; Томас, Джереми; Вайншельбаум, Илан (2018), «Шесть вариаций на тему: почти плоские графы», Involve: A Journal of Mathematics , 11 (3): 413–448, arXiv : 1608.01973 , doi : 10.2140/involve.2018.11.413 , S2CID   119740613 .
• Мохар, Боян (2001), «Лицевые покровы и проблема рода для вершинных графов» (PDF) , Journal of Combinatorial Theory, Series B , 82 (1): 102–117, doi : 10.1006/jctb.2000.2026 , заархивировано из оригинал (PDF) от 22 сентября 2017 г. , получено 2 августа 2010 г.
• Пирс, Майк (2014), Поиск и классификация конечного множества минорно-минимальных невершинных графов (PDF) , дипломная работа с отличием, Калифорнийский государственный университет, Чико .
• Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1993a), «Гипотеза Хадвигера для PDF ₍ графов, свободных от K6» ) , Combinatorica , 13 (3): 279–361, doi : 10.1007/BF01202354 , S2CID   9608738 .
• Робертсон, Нил ; Сеймур, Полиция ; Томас, Робин (1993b), «Бесзвенные вложения графов в трехмерное пространство», Бюллетень Американского математического общества , 28 (1): 84–89, arXiv : math/9301216 , doi : 10.1090/S0273-0979-1993- 00335-5 , МР   1164063 , S2CID   1110662 .
• Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1993c), «Обзор бессвязных вложений», Робертсон, Нил ; Сеймур, Пол (ред.), Теория структуры графов: Proc. Совместная летняя исследовательская конференция AMS – IMS – SIAM по минорным графам (PDF) , Contemporary Mathematics, vol. 147, Американское математическое общество, стр. 125–136 .
• Трумпер, Клаус (1992), Разложение матроида (PDF) , Academic Press, стр. 100–101, заархивировано из оригинала (PDF) 29 августа 2017 г. , получено 2 августа 2010 г.
• Вагнер, Клаус (1967), «Почти плоские графы», Журнал комбинаторной теории (на немецком языке), 3 (4): 326–365, doi : 10.1016/S0021-9800(67)80103-0 .
• Вагнер, Клаус (1970), «Об основной проблеме графов, которые не могут быть вложены в проективную плоскость I», Журнал комбинаторной теории (на немецком языке), 9 (1): 27–43, doi : 10.1016/S0021- 9800(70) 80052-7 .