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

В теории графов , разделе математики, вершинный граф - это граф, который можно сделать плоским , удалив одну вершину. Удаленная вершина называется вершиной графа. Это вершина, а не вершина , потому что вершина граф может иметь более одной вершины; например, в минимальных неплоских графах 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-вершинно-связный -без минорным графом вершинным?

(больше нерешенных задач по математике)

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

Ширина местного дерева [ править ]

Семейство графов F имеет ограниченную локальную ширину дерева, если графы в F подчиняются функциональному соотношению между диаметром и шириной дерева : существует функция ƒ такая, что ширина дерева графа диаметра d в F не превосходит ( d ). Графики апекса не имеют ограниченные локальную древесную ширину: апекс графы , образованную путем соединения при вершине вершины каждой вершины из п  ×  п сетка график Наличия древесной шириной ни диаметр 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-приводимого вершинного графа.

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

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

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

Почти плоские графики [ править ]

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

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

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

Связанные классы графов [ править ]

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

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

См. Также [ править ]

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

Заметки [ править ]

  1. ^ a b Робертсон, Сеймур и Томас (1993b) .
  2. ^ a b Робертсон, Сеймур и Томас (1993a) .
  3. ^ а б в г Truemper (1992) .
  4. ^ а б Эппштейн (2000) ; Demaine и Hajiaghayi (2004) .
  5. ^ а б Гупта и Импальяццо (1991) .
  6. ^ Пирс (2014) .
  7. ^ Kawarabayashi (2009) .
  8. ^ Lewis & Yannakakis (1980) .
  9. ^ «Гипотеза Йоргенсен» , Открытый Проблема Сад , извлекаться 2016-11-13.
  10. ^ Каварабаяши и др. (2012) .
  11. ^ Эпштайна (2000) ; Фрик и Гроэ (2001) ; Demaine и Hajiaghayi (2005) .
  12. ^ Demaine, Hajiaghayi & Kawarabayashi (2009) .
  13. ^ Grohe (2003) .
  14. ^ Mohar (2001) .
  15. ^ Чимани и др. (2009) .
  16. ^ Кабельо & Mohar (2010) .
  17. ^ Робертсон, Seymour & Thomas (1993c) .
  18. ^ Робертсон, Seymour & Thomas (1993c) ; Эппштейн (2000) .
  19. ↑ Архидьякон и Боннингтон (2004) .
  20. ^ Abraham & Gavoille (2006 год) .

Ссылки [ править ]

  • Авраам, Иттай; Gavoille, Cyril (2006), "Местоположение объекта с использованием разделителей пути", Proc. Двадцать пятый ACM симпозиум по принципам распределенных вычислений (PODC '06) . С. 188-197, DOI : 10,1145 / 1146381,1146411.
  • Архидиакон, Дан ; Боннингтон, CPC Paul (2004), "Препятствия для вложения кубических графов на поверхность шпинделя", Журнал комбинаторной теории, серия B , 91 (2): 229–252, doi : 10.1016 / j.jctb.2004.02.001.
  • Кабельо, Серджио; Мохар, Боян (2010), "Добавление одного ребра к планарным графам затрудняет число пересечений", Proc. 26-й симпозиум ACM по вычислительной геометрии (SoCG '10) (PDF) , стр. 68–76, DOI : 10.1145 / 1810959.1810972 , заархивировано из оригинала (PDF) 14 марта 2012 г. , извлечено 02 августа 2010 г..
  • Чимани, Маркус; Гутвенгер, Карстен; Муцель, Петра ; Вольф, Кристиан (2009), "Вставка вершины в плоский граф", Proc. 20-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA '09) , стр. 375–383.
  • Демейн, Эрик Д .; Hajiaghayi Мохаммад Taghi (2004), "Диаметр и древесная ширина в минорных замкнутый граф семей, Revisited", Algorithmica , 40 (3): 211-215, DOI : 10.1007 / s00453-004-1106-1.
  • Демейн, Эрик Д .; Хаджиагайи, Мохаммад Таги (2005), «Двумерность: новые связи между алгоритмами FPT и PTAS», Proc. Шестнадцатый ACM-SIAM симпозиум по дискретным алгоритмам (SODA '05) , стр. 590-601, архивируется с оригинала на 2018-12-11 , извлекаться 2010-08-02.
  • Демейн, Эрик Д .; Хаджиагайи, Мохаммад Таги; Каварабаяси, Кен-ичи (2009), "Алгоритмы приближения через структурные результаты для графов без апекс-минор" (PDF) , Proc. 36-й Международный коллоквиум «Автоматы, языки и программирование» (ICALP '09) , Lecture Notes in Computer Science, 5555 , Springer-Verlag, pp. 316–327, doi : 10.1007 / 978-3-642-02927-1_27.
  • Эппштейн, Дэвид (2000), «Диаметр и ширина дерева в семействах малых замкнутых графов», Algorithmica , 27 (3): 275–291, arXiv : math.CO/9907126 , doi : 10.1007 / s004530010020.
  • Фрик, Маркус; Grohe, Martin (2001), "Определение свойств первого порядка локально древовидно разложимых структур", Журнал ACM , 48 (6): 1184–1206, arXiv : cs / 0004007 , doi : 10.1145 / 504794.504798.
  • Grohe, Martin (2003), «Локальная ширина дерева, исключенные миноры и алгоритмы аппроксимации», Combinatorica , 23 (4): 613–632, arXiv : math.CO/0001128 , doi : 10.1007 / s00493-003-0037- 9.
  • Gupta, A .; Impagliazzo, R. (1991), "Вычисление плоских переплетений" , Proc. 32-й симпозиум IEEE по основам компьютерных наук (FOCS '91) , IEEE Computer Society, стр. 802–811, DOI : 10.1109 / SFCS.1991.185452.
  • Йоргенсен, Лейф К. (1994), «Сокращение до K 8 », Журнал теории графов , 18 (5): 431–448, DOI : 10.1002 / jgt.3190180502. Цитируется Робертсоном, Сеймуром и Томасом ( 1993a , 1993c ).
  • Каварабаяси, Кен-ичи (2009), «Планарность, допускающая несколько вершин ошибок за линейное время» (PDF) , Proc. Пятидесятые IEEE симпозиум по Основы информатики (FOCS '09) ., IEEE Computer Society, стр 639-648, DOI : 10,1109 / FOCS.2009.45.
  • Каварабаяси, Кен-ичи ; Норин, Сергей; Томас, Робин ; Воллан, Пол (2012), миноры в больших 6-связных графах , arXiv : 1203.2192 , Bibcode : 2012arXiv1203.2192K.
  • Льюис, Джон М .; Yannakakis, Михалис (1980), "Проблема узла удаления наследственных свойств является NP-полной", журнал компьютерных и системных наук , 20 (2): 219-230, DOI : 10,1016 / 0022-0000 (80) 90060- 4.
  • Липтон, Макс; Макколл, Эоин; Mattman, Thomas W .; Пирс, Майк; Робинсон, Саманта; Томас, Джереми; Вайншельбаум, Илан (2018), «Шесть вариаций на тему: почти плоские графы», Involve, A Journal of Mathematics , 11 (3): 413–448, arXiv : 1608.01973 , doi : 10.2140 / include.2018.11.413.
  • Mohar, Боян (2001), "накрывает лицо и проблема рода для апекса графов" (PDF) , Журнал комбинаторной теории, серии B , 82 (1): 102-117, DOI : 10,1006 / jctb.2000.2026 , архивируется с оригинал (PDF) на 2017-09-22 , извлекаться 2010-08-02.
  • Пирс, Майк (2014), Поиск и классификация конечного множества минорно-минимальных не вершинных графов (PDF) , диплом с отличием, Калифорнийский государственный университет, Чико.
  • Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1993a), "гипотеза Хадвигера для K 6 -свободных графов" (PDF) , Combinatorica , 13 (3): 279-361, DOI : 10.1007 / BF01202354.
  • Робертсон, Нил ; Сеймур, PD ; Томас, Робин (1993b), «Бесконечные вложения графов в 3-пространство», Бюллетень Американского математического общества , 28 (1): 84–89, arXiv : math / 9301216 , doi : 10.1090 / S0273-0979-1993- 00335-5 , Руководство по ремонту  1164063.
  • Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1993c), «Обзор беззвучных вложений», Робертсон, Нил ; Сеймур, Пол (ред.), Теория структуры графов: Proc. Совместная летняя исследовательская конференция AMS – IMS – SIAM по второстепенным графам (PDF) , Современная математика, 147 , Американское математическое общество, стр. 125–136.
  • Truemper, Klaus (1992), Matroid Decomposition (PDF) , Academic Press, стр. 100–101..
  • Вагнер, Клаус (1967), "Fastplättbare графена", Журнал комбинаторной теории (на немецком языке ), 3 (4): 326-365, DOI : 10.1016 / S0021-9800 (67) 80103-0.
  • Вагнер, Клаус (1970), «Zum baseproblem der nicht in die projektive ebene einbettbaren graphen, I», Журнал комбинаторной теории (на немецком языке), 9 (1): 27–43, DOI : 10.1016 / S0021-9800 (70) 80052-7.