Алгоритм укладки графа на плоскости

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

Одним из таких алгоритмов является следующий [3].

Рассмотрим граф G=(X,U). Алгоритм укладки графа представляет собой процесс последовательного присоединения к некоторому уложенному подграфу G' (G'=(X',U')) графа G новой цепи, оба конца которой принадлежат G'. Тем самым эта цепь разбивает одну из граней G' на две. При этом в качестве начального плоского графа G' выбирается любой простой цикл графа G. Процесс продолжается до тех пор, пока не будет построен плоский граф, изоморфный графу G, или присоединение некоторой цепи окажется невозможным. В этом случае граф не является планарным.

Введем ряд определений.

Плоский граф – это граф, уложенный на плоскости.

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

Рис. 10

Пусть построена некоторая укладка подграфа G' графа G. Сегментом S относительно G' (или просто сегментом) будем называть подграф графа G одного из следующих двух видов:

1) ребро e=(u,v) G, такое, что еÏG', u, v ÎX';

2) связанную компоненту графа G-G', дополненную всеми ребрами графа G, инцидентными вершинам взятой компоненты, и концам этих ребер.

Очевидно, что в случае, когда граф G планарный, всякий сегмент, как подграф графа G, планарен, а в случае, когда G не является планарным, сегмент может быть как планарным, так и не планарным.

Вершину v сегмента S относительно G' будем называть контактной, если v ÎX'.

Поскольку граф G' плоский, то он разбивает плоскость на грани. Допустимой гранью для сегмента S относительно G' называется грань Г графа G', содержащая все контактные вершины сегмента S. Через Г(S) будем обозначать множество допустимых граней для S. Может оказаться, что Г(S)=Æ.

Простую цепь L сегмента S, соединяющую две различные контактные вершины и не содержащую других контактных вершин, назовем a–цепью. Очевидно, что всякая a–цепь, принадлежащая сегменту, может быть уложена в любую грань, допустимую для этого сегмента.

Два сегмента S₁ и S₂ относительно G' назовем конфликтующими, если

1) q=Г(S)ÇГ(S)¹Æ,

2) существуют две a-цепи L₁ÎS_1, L₂ÎS₂, которые без пересечений нельзя уложить одновременно ни в какую грань ГÎq. В противном случае будем говорить, что сегменты не конфликтуют.

Вернемся к алгоритму. На первом шаге этого алгоритма уложим произвольный простой цикл графа G.

Пусть G' - построенная на предыдущем шаге укладка некоторого подграфа графа G. Для каждого сегмента относительно G' находим множество допустимых граней. Теперь могут представиться только следующие три случая.

1. Существует сегмент, для которого нет допустимой грани. В этом случае граф не планарен.

2. Для некоторого сегмента S существует единственная допустимая грань Г. Тогда очередной шаг состоит в расположении любой a–цепи сегмента S в грани Г. При этом a–цепь разбивает грань Г на две грани.

3. Г(S)³2 для всякого сегмента S. Тогда появляется несколько вариантов продолжения построения укладки графа, поскольку любой сегмент можно размещать в любую допустимую для этого сегмента грань. Поэтому возникают опасения, что неудачный выбор сегмента и грани может помешать процессу построения укладки на следующих шагах и плоская укладка планарного графа не будет построена. Это могло бы привести к неверному заключению о том, что планарный граф непланарен. В [3] показано, что в этом случае для продолжения алгоритма можно выбирать a–цепь в любом сегменте и помещать его в любую допустимую грань.

Поиск по сайту: