Вершинный граф

Вершинный граф — это граф, который может быть получен из планарного графа путём добавления одной вершины, соединённой рёбрами с произвольным подмножеством исходных вершин. Иными словами, граф \( G \) является вершинным, если существует такая вершина \( v \) (называемая вершиной-апексом), что после её удаления из \( G \) оставшийся граф \( G \setminus \{v\} \) является планарным. Класс вершинных графов является одним из фундаментальных понятий теории графов и топологической теории графов, находящим применение в алгоритмической теории графов и теории миноров.

Определение и формализация

Пусть \( G = (V, E) \) — неориентированный граф. Граф \( G \) называется вершинным (или апексным), если существует вершина \( a \in V \) (апекс) такая, что граф \( G \setminus \{a\} \) является планарным. Вершина \( a \) может быть соединена рёбрами с любыми вершинами из \( V \setminus \{a\} \), в том числе со всеми, что не нарушает планарности после её удаления, так как планарность проверяется для подграфа без неё.

Важным уточнением является то, что определение не требует, чтобы граф \( G \) сам по себе был планарным. Напротив, вершинные графы часто являются непланарными. Например, полный граф \( K_5 \) (минимальный непланарный граф) является вершинным, так как удаление любой его вершины даёт \( K_4 \), который планарен. Аналогично, полный двудольный граф \( K_{3,3} \) также является вершинным: удаление одной вершины из любой доли даёт \( K_{3,2} \), который планарен.

История и контекст

Понятие вершинного графа возникло в рамках изучения планарности и непланарности графов. В 1930-х годах Казимеж Куратовский и Клаус Вагнер независимо сформулировали критерии планарности. Критерий Вагнера (1937) гласит, что граф планарен тогда и только тогда, когда он не содержит в качестве минора ни \( K_5 \), ни \( K_{3,3} \). Это открыло путь к изучению классов графов, определяемых запрещёнными минорами. Вершинные графы, как класс, естественным образом возникают при рассмотрении графов, которые становятся планарными после удаления небольшого числа вершин.

В 1970-х годах теория миноров графов, развитая Нейлом Робертсоном и Полом Сеймуром, привела к глубоким результатам о структуре графов. Одним из ключевых понятий этой теории является апекс-граф (вершинный граф) как часть более общего разложения графов на почти планарные компоненты. В 1980-х годах Робертсон и Сеймур доказали, что класс вершинных графов является минорно-замкнутым, то есть любой минор вершинного графа также является вершинным графом. Это свойство позволило включить апекс-графы в знаменитую теорему о структуре графов, которая утверждает, что любой граф, не содержащий некоторого фиксированного минора, может быть построен из вершинных графов и планарных графов с помощью склеиваний по кликам.

Свойства и характеристики

Минорная замкнутость

Класс вершинных графов замкнут относительно взятия миноров. Это означает, что если \( G \) — вершинный граф, то любой граф, полученный из \( G \) удалением вершин, удалением рёбер или стягиванием рёбер, также будет вершинным. Это свойство следует из того, что удаление или стягивание ребра не может создать новый непланарный подграф, который не был бы минором исходного графа, а планарность сохраняется при минорных операциях.

Запрещённые миноры

По теореме Робертсона — Сеймура, любой минорно-замкнутый класс графов может быть охарактеризован конечным набором запрещённых миноров. Для класса вершинных графов такой набор известен не полностью, но известно, что в него входят некоторые графы, не являющиеся вершинными. Например, граф Петерсена не является вершинным, так как удаление любой его вершины оставляет граф, содержащий минор \( K_{3,3} \). Однако полный список запрещённых миноров для вершинных графов неизвестен и, по-видимому, содержит более 20 графов.

Связь с планарностью

Вершинные графы являются обобщением планарных графов. Все планарные графы тривиально являются вершинными (можно взять любую вершину в качестве апекса, хотя это не требуется, так как планарный граф уже удовлетворяет условию). Обратное неверно: существуют непланарные вершинные графы, такие как \( K_5 \) и \( K_{3,3} \). Более того, любой граф, который становится планарным после удаления одной вершины, является вершинным.

Род графа

Вершинные графы имеют род (минимальное число ручек тора, необходимых для вложения графа без пересечений) не более 1. Это связано с тем, что удаление одной вершины позволяет вложить оставшуюся часть в плоскость, а сама вершина может быть размещена на дополнительной ручке. Однако это не точная характеристика: существуют графы рода 1, которые не являются вершинными (например, граф Петерсена).

Классификация и обобщения

Многоапексные графы

Обобщением вершинных графов являются k-апексные графы (или графы с k апексами), которые становятся планарными после удаления не более \( k \) вершин. Класс \( k \)-апексных графов также минорно-замкнут. Для \( k = 0 \) это планарные графы, для \( k = 1 \) — вершинные графы. Изучение \( k \)-апексных графов важно для теории параметризованной сложности, так как многие NP-трудные задачи становятся разрешимыми за полиномиальное время на графах с ограниченным числом апексов.

Апекс-миноры

В теории миноров графов понятие апекса используется для описания структурных разложений. Граф называется апекс-графом (в более узком смысле), если он может быть получен из планарного графа добавлением одной вершины, соединённой рёбрами с произвольным подмножеством вершин, но при этом сама добавленная вершина может быть соединена только с вершинами, образующими некоторое подмножество, не обязательно все. В современной литературе термины «вершинный граф» и «апекс-граф» часто используются как синонимы.

Применение

Алгоритмическая теория графов

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

Теория миноров

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

Топологическая теория графов

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

Примеры

Примеры вершинных графов

1. Полный граф \( K_5 \). Удаление любой вершины даёт \( K_4 \), который планарен.
2. Полный двудольный граф \( K_{3,3} \). Удаление одной вершины из любой доли даёт \( K_{3,2} \), который планарен.
3. Граф Вагнера (граф \( K_5 \) с одним ребром, разделённым вершиной). Удаление вершины, разделяющей ребро, даёт планарный граф.
4. Граф \( K_{3,4} \). Удаление вершины из доли с 4 вершинами даёт \( K_{3,3} \), который непланарен, но удаление вершины из доли с 3 вершинами даёт \( K_{2,4} \), который планарен. Таким образом, \( K_{3,4} \) является вершинным.

Примеры невершинных графов

1. Граф Петерсена. Удаление любой вершины оставляет граф, содержащий минор \( K_{3,3} \), что делает его непланарным.
2. Граф \( K_{4,4} \). Удаление одной вершины даёт \( K_{3,4} \) или \( K_{4,3} \), которые, как показано выше, вершинны, но сам \( K_{4,4} \) не является вершинным, так как после удаления любой вершины оставшийся граф содержит минор \( K_{3,3} \).
3. Граф Грёча (граф с 11 вершинами, являющийся контрпримером к гипотезе о раскраске). Он не является вершинным, так как удаление любой вершины не даёт планарного графа.

Интересные факты

• Вершинные графы являются одним из немногих классов графов, для которых известен точный алгоритм проверки принадлежности к классу за полиномиальное время. Алгоритм основан на проверке планарности после удаления каждой вершины, что даёт сложность \( O(n^2) \), где \( n \) — число вершин.
• Понятие вершинного графа тесно связано с понятием апекс-дерева в теории матроидов, где апекс-графы рассматриваются как частный случай более общих структур.
• В 2015 году была доказана гипотеза о том, что любой вершинный граф может быть вложен в тор, но это оказалось неверным: существуют вершинные графы, которые не вкладываются в тор, например, граф \( K_{3,4} \) вкладывается в тор, а граф \( K_{4,4} \) — нет, хотя он не является вершинным.

Источники

• Diestel, R. (2017). Graph Theory. Springer.
• Robertson, N., & Seymour, P. D. (1986). Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7(3), 309–322.
• Mohar, B., & Thomassen, C. (2001). Graphs on Surfaces. Johns Hopkins University Press.
• Bodlaender, H. L. (1998). A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209(1-2), 1–45.