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

Введение

Проблема определения планарности графа может быть отнесена к самым важным задачам систем автоматизированного проектирования (САПР), она заключается в определении специального представления графа, при котором ребра исследуемого графа не имеют взаимных пересечений.

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

Статья: Проверка планарности графа

Найди решение своей задачи среди 1 000 000 ответов

Найти решение задачи

В качестве такого устройства может выступать печатная плата, интегральная микросхема, БИС, СБИС и так далее. Существует метод проверки планарности графа с одновременным формированием математических структур, предназначенных для описания топологического рисунка графа с целью его визуализации. Метод базируется на создании системы изометрических циклов, понятии вращения вершин графа, а также задании операции определения пересечения ребер в виде пересечения их проекций на координатно-базисную систему, в качестве которой может использоваться опорный цикл DFS-дерева (Depth-first search, то есть, поиска в глубину) графа.

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

$O(m^2)$,

где m является количеством вершин графа.

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

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

Предположим, что имеется произвольный граф G. Путем последовательного просмотра всех вершины графа, следует удалить петли, «висячие» вершины и кратные ребра, если они присутствуют в графе. Далее следует удалить мосты и точки сочленения, что позволяет получить несколько компонент связности, которые могут рассматриваться по отдельности. Пара ребер, которые соединены одной вершиной, имеющей локальную степень равную двум, следует заменить одним ребром. Подразумевается, что эти преобразования необходимо запомнить, для того чтобы впоследствии можно было восстановить первоначальный вида графа G после его проверки.

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

Пусть G = (X,U) является несеперабельным графом, имеющим пронумерованные множество ребер:

$U$ = {$u_1, u_2, ..., u_m$},

и вершин:

$X$ = {$x_1,x_2, ..., x_n$}.

При этом card X = n и card U = m.

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

Рисунок 1. Диаграмма графа G. Автор24 — интернет-биржа студенческих работ

Рисунок 2. Диаграмма графа G. Автор24 — интернет-биржа студенческих работ

Рисунок 3. Диаграмма графа G. Автор24 — интернет-биржа студенческих работ

Если граф является планарным, то всегда присутствует возможность провести соединения (ребер графа) без наличия пересечений. Данное представление планарного графа именуется плоским изображением графа, как на рисунке выше.

Необходимо заметить, что известны структуры, являющиеся общими для всех плоских изображений графа. Рассмотрим множество простых циклов, которые являются границами граней плоского изображения. Приведем пример, в котором используем граф G, изображенный на рисунке выше. Представим множество граничных циклов в форме компонентов пространства суграфов:

$c_1$ = {$u_2, u_5, u1_0$}; $c_2$ = {$u_3, u_5, u_{12}$}; $c_3$ = {$u_8, u_{10}, u_{12}$}; $c_4$ = {$u_8, u_9, u_{11}$};

$c_5$ = {$u_6, u_7, u_9$}; $c_6$ = {$u_3, u_4, u_{11}$}; $c_7$ = {$u_1, u_4, u_7$}; $c_8$ = {$u_1, u_2, u_6$}.

Цикломатическое число должно определять число независимых циклов графа:

$V(G) = m – n + 1$

Кольцевая сумма независимых циклов способна определить обод. На рисунке ниже показано задание направления обхода ребер в циклах.

Рисунок 4. Задание направления обхода ребер в циклах. Автор24 — интернет-биржа студенческих работ

Если выполнить задание направления обхода ребер в циклах, соблюдая условия планарности Маклейна, то тогда следует записывать циклы как кортежи вершин:

Рисунок 5. Циклы как кортежи вершин. Автор24 — интернет-биржа студенческих работ

Но если взглянуть с обратной стороны, то задаваемое подмножество циклов, имеющее заданное направление обхода ребер, способно породить (индуцировать) некоторый циклический порядок распределения смежных вершин для каждой из вершин. На рисунке ниже показано вращение вершины $х_1$.

Рисунок 6. Вращение вершины х1. Автор24 — интернет-биржа студенческих работ

Для заданного графа G вращением вершины А графа G является ориентированный циклический порядок (или циклическая перестановка) всех ребер, которые являются инцидентными к вершине А. Вращение графа следует описать и представить следующим образом. Введем обозначения вершин как $x_1, x_2, ..., x_n$. Далее запишем циклическую перестановку соседей для всех вершин $x_i$. Эта перестановка определяется вращением вершины $x_i$, являющимся циклической перестановкой ребер, которые инцидентны вершине $x_i$.