Проверка планарного графа

О Проверка планарного графа

Инструмент Проверка Планарного Графа определяет, является ли простой неориентированный граф планарным (то есть изобразимым на плоскости без пересечений ребер), и, если граф не проходит проверку, находит и визуализирует свидетельство Куратовского: подразделение либо K₅ (полного графа на 5 вершинах), либо K₃,₃ (полного двудольного графа на 3 + 3 вершинах). Инструмент создан для обучения, подготовки к соревнованиям по программированию и быстрой проверки небольших конструкций графов.

Что означает «Планарный»?

Граф G = (V, E) называется планарным, если его можно вложить в плоскость так, чтобы ребра пересекались только в своих общих конечных точках. Эквивалентно, G можно нарисовать на поверхности сферы без пересечений. Планарность — это чисто топологическое свойство: оно не зависит от того, как вы рисуете граф, а только от того, существует ли хотя бы одна укладка без пересечений.

Планарные графы встречаются повсеместно: дорожные и инженерные сети, разводка печатных плат, реберные графы Платоновых тел и структура граней многогранников. Тем не менее, многие «естественные» графы упрямо непланарны: каждый раз, когда вы пытаетесь соединить 3 дома с 3 источниками ресурсов без пересечений, вы сталкиваетесь с барьером K₃,₃.

Теорема Куратовского — ядро проверки

Казимир Куратовский в 1930 году доказал, что планарность имеет чисто комбинаторную характеристику:

Подразделение графа H получается путем замены некоторых ребер H более длинными путями, внутренние вершины которых являются новыми вершинами степени 2. Теорема Куратовского, таким образом, говорит о том, что K₅ и K₃,₃ являются единственными препятствиями для планарности — любой непланарный граф содержит один из них в «растянутом» виде.

Запрещенные графы

Формула Эйлера и быстрые необходимые условия

Перед запуском (относительно дорогого) поиска подразделения, инструмент применяет два быстрых необходимых условия, выведенных из формулы Эйлера: для любого связного планарного графа, нарисованного на плоскости с V вершинами, E ребрами и F гранями (с учетом неограниченной внешней грани), выполняется:

В сочетании с наблюдением, что каждая грань простого планарного графа имеет как минимум 3 ребра на своей границе, мы получаем верхнюю границу количества ребер:

Любой граф, нарушающий эти неравенства, немедленно признается непланарным без поиска подразделений. У K₅ m = 10, n = 5 ⇒ 3n − 6 = 9, так как 10 > 9 — условие нарушено. У K₃,₃ m = 9, n = 6 ⇒ 2n − 4 = 8, так как 9 > 8 — нарушено условие двудольности.

Как работает поиск подразделения

После быстрых проверок Эйлера инструмент ищет подразделение напрямую:

1. Быстрый поиск — обнаружение K₅ или K₃,₃ как буквального подграфа. Если 5 вершин попарно смежны, это в чистом виде K₅. Если 6 вершин делятся на 3 + 3 со всеми 9 перекрестными ребрами, это K₃,₃.
2. Поиск подразделения K₅. Для каждого набора-кандидата из 5 «базовых» вершин (каждая со степенью ≥ 4 в G) делается попытка найти 10 путей — по одному на пару — которые не имеют общих внутренних вершин и не используют другие базовые вершины в качестве промежуточных. Успех доказывает непланарность.
3. Поиск подразделения K₃,₃. Выбираются 6 базовых вершин (со степенью ≥ 3) и разбиение 3 + 3. Ищутся 9 межгрупповых путей с тем же требованием отсутствия общих внутренних вершин.
4. Нет свидетельства ⇒ планарный. Если ни одно подразделение не найдено в пределах ограничений по размеру, теорема Куратовского гарантирует, что граф планарный.

Поиск путей без общих вершин в общем случае является NP-трудной задачей, поэтому инструмент использует ограниченный рандомизированный жадный поиск: в каждой итерации требуемые пары упорядочиваются по сложности, путь для самой сложной пары ищется первым с помощью рандомизированного BFS, внутренние вершины удаляются, и процесс продолжается. Если порядок не сработал, делается попытка с перемешанным порядком — до 40 попыток на каждую конфигурацию вершин. Для всех протестированных малых графов (до 16 вершин) этого достаточно для обнаружения свидетельства, если оно существует.

Как пользоваться этим калькулятором

1. Выберите формат ввода с помощью вкладок вверху: список ребер или список смежности. Оба описывают один и тот же граф.
2. Введите ваш граф. Граф считается неориентированным, поэтому A-B и B-A — это одно и то же ребро.
3. Нажмите «Проверить планарность». Инструмент выдаст вердикт, покажет пошаговые рассуждения (Эйлер, двудольность, Куратовский) и отрисует граф.
4. Для непланарного графа визуализация окрасит подразделение K₅ или K₃,₃ и перечислит пути без общих вершин. Кликните на строку пути, чтобы выделить его.
5. Для планарного графа количество граней F = m − n + 1 + c будет указано вместе со структурой графа.

Пример 1 — K₄ планарный

У K₄ n = 4, m = 6. Любой граф с ≤ 4 вершинами планарный, и действительно, K₄ можно представить как треугольник с одной вершиной внутри, соединенной со всеми тремя углами. Эйлер говорит, что F = 6 − 4 + 2 = 4 грани: три треугольные внутренние грани плюс внешняя область.

Пример 2 — K₃,₃ непланарный

У K₃,₃ n = 6, m = 9. Он двудольный, поэтому применяется граница двудольности: m = 9 > 2n − 4 = 8. Одно это доказывает непланарность. Свидетельство тривиально — K₃,₃ сам по себе является запрещенным подграфом. Инструмент выделит разбиение 3 + 3 и 9 прямых ребер.

Пример 3 — Граф Петерсена

Граф Петерсена имеет n = 10, m = 15, поэтому m ≤ 3n − 6 = 24, и быстрые проверки Эйлера проходят. Тем не менее, он знаменит своей непланарностью. Инструмент находит подразделение K₃,₃: выбираются шесть вершин из внешнего пятиугольника и внутренней пентаграммы так, чтобы каждая перекрестная пара могла быть соединена через оставшиеся четыре вершины путями без общих внутренних вершин. Инструмент отрисовывает это свидетельство, делая геометрию 1930-х годов осязаемой.

Применение планарности

• Проектирование СБИС и печатных плат. Однослойная схема возможна только если граф соединений планарный; непланарные сети требуют переходных отверстий или дополнительных слоев.
• Отрисовка и визуализация графов. Планарные графы позволяют создавать четкие схемы без пересечений — полезно для карт метро, графов вызовов и принципиальных схем.
• Дизайн алгоритмов. Многие NP-трудные задачи (максимальный разрез, вершинное покрытие, изоморфизм графов) решаются за полиномиальное время, если ограничиться планарными графами.
• Раскраска графов. Теорема о четырех красках гарантирует, что любой планарный граф можно раскрасить 4 цветами — классический результат, основанный на планарности.
• Комбинаторная оптимизация. Поиск кратчайшего пути, максимального потока и минимального разреза в планарных графах имеет специализированные быстрые алгоритмы.
• Молекулярная химия. Графы ароматических углеводородов с бензольным кольцом планарны; некоторые каркасные молекулы — нет.

Часто задаваемые вопросы

Что означает «планарный» для графа?

Граф называется планарным, если его можно изобразить на плоскости так, чтобы никакие два ребра не пересекались нигде, кроме общих вершин. Эквивалентно, граф является планарным тогда и только тогда, когда его можно изобразить на поверхности сферы без пересечений. Деревья, циклы, граф куба и Платоновы тела являются планарными, в то время как K₅ и K₃,₃ — каноническими примерами непланарных графов.

Что такое теорема Куратовского?

Теорема Куратовского утверждает, что конечный граф является планарным тогда и только тогда, когда он не содержит подграфа, являющегося подразделением K₅ или K₃,₃. Подразделение получается путем замены некоторых ребер более длинными путями через новые вершины степени 2. Это дает конкретное комбинаторное доказательство непланарности.

В чем разница между K₅ и K₃,₃?

K₅ имеет 5 вершин, каждая пара которых соединена ребром (всего 10 ребер). K₃,₃ имеет 6 вершин, разделенных на две группы по 3, где каждая вершина одной группы соединена с каждой вершиной другой группы (всего 9 ребер). Оба являются наименьшими непланарными графами в своем роде и образуют запрещенные миноры.

Как помогает неравенство Эйлера?

Формула Эйлера V − E + F = 2 для планарных связных графов в сочетании с тем фактом, что каждая грань простого планарного графа имеет не менее 3 ребер, дает m ≤ 3n − 6. Любой простой граф, нарушающий этот предел, сразу считается непланарным. Для двудольных планарных графов каждая грань имеет не менее 4 ребер, что дает границу m ≤ 2n − 4. Инструмент применяет оба правила для быстрого отсева.

Каков предел размера?

Инструмент обрабатывает до 16 вершин и 60 ребер. Этого достаточно для большинства учебных и соревновательных графов, таких как граф Петерсена, граф Мёбиуса — Кантора, малые гиперкубы и полный граф K₇. Для более крупных графов требуются специализированные тесты за линейное время.

Как рисуется подразделение-свидетельство?

Когда граф непланарный, 5 базовых вершин найденного K₅ — или 6 базовых вершин K₃,₃, разделенных на две тройки A и B — подсвечиваются на внутреннем кольце. 10 (или 9) необходимых путей без общих внутренних вершин рисуются разными цветами для визуального прослеживания топологии. Вершины и ребра, не входящие в подразделение, затеняются.

Дополнительная литература

• Планарный граф — Википедия
• Теорема Куратовского — Википедия
• Эйлерова характеристика — Википедия
• Граф Петерсена — Википедия
• Теорема Вагнера — Википедия