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

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

Алгоритм γ укладки графа G представляет собой процесс последовательного присоединения к некоторому уложенному подграфу С₀ графа G новой цепи, оба конца ко­торой принадлежат G₀. Тем самым эта цепь разбивает одну из граней графа G₀ на две. При этом в качестве на­чального плоского графа G₀ выбирается любой простой цикл графа G. Процесс продолжается до тех пор, пока не будет построен плоский граф, изоморфный графу G, или присоединение некоторой цепи окажется невозможным. В последнем случае граф G не является планарным.

Поскольку связный граф планарен тогда и только тогда, когда планарны все. его блоки (теорема 37.8), а граф К₂ планарен, то будем предполагать не теряя общности, что укладываемый граф 2-связен.

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

1. ребро e = uvEG такое, что eи  EG₀, u,vVG₀;

1. связную компоненту графа G — G₀, дополненную всеми ребрами графа G, инцидентными вершинам взя­той компоненты, и концами этих ребер.

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

Вершину v сегмента S относительно G₀ будем называть контактной, если v  VG₀. Так как в графе G нет то­чек сочленения, то легко доказать, что в случае, когда граф G является 2-связным, каждый сегмент содержит не менее двух контактных вершин.

На рис. 41.1 изображены граф G, его уложенный под­граф G₀ и все сегменты относительно G₀. Контактные вер­шины сегментов обведены кружками.

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

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

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

1) 0 = Г (S₁)  Г (S₂)  ø, 2) существуют две α -цепи L₁ S₁, L₂ S₂, которые без пересечений нельзя уложить одновременно ни в какую грань Г  0. В противном случае будем говорить, что сегменты не конфликтуют.

Для графа, изображенного на рис. 41.1, конфликтую­щими являются, например, сегменты S₁ и S₂, S₃ и S₄,S₂ и S₆

Вернемся к обсуждению алгоритма у.

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

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

1. Существует сегмент, для которого нет допустимой грани. Как мы покажем в дальнейшем, граф G в этом случае не планарен.

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

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

Теперь формально опишем алгоритм γ, а затем зай­мемся его обоснованием.

Алгоритм γ

0. Выберем некоторый простой цикл С графа G и уложим его на плоскости; положим G₀ = =C.

1. Найдем грани графа G₀ и сегменты относительно G₀. Если множество сегментов пусто, то перейдем к п. 7.

2. Для каждого сегмента S определим множество Г(S).

3. Если существует сегмент S, для которого Г (S) = ø, то граф G непланарен. Конец. Иначе перейдем к п. 4.

4. Если существует сегмент S, для которого имеется единственная допустимая грань Г, то перейдем к п. 6. Иначе — к п. 5.

5. Для некоторого сегмента S (Г(S)> 1) выбираем произвольную допустимую грань Г.

6. Поместим произвольную а-цепь L  S в грань Гзаменим G₀ наG U L и перейдем к п 1. 7.Построена укладка G₀ графа G на плоскости. Конец. Шагом алгоритма γ будем считать присоединение к G α -цепи L.

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

Лемма 41.1. Если конфликтующие сегменты S₁ иS₂ относительно G₀ таковы, что |Г(S₁)|2, Г|(S2)|2, то Г(S₁) = Г(S₂), |Г(S₁) |=2.

Сначала докажем, что Г(S₁) = Г(S₂). Допустим противное. Тогда по условию леммы существуют три различных грани: Г₁Г(S₁), Г₂ Г(S₂),Г₃0=Г(S₁)Г(S₂)ø. Поэтому всякая а-цепь L₁лежитS₁ укладывается в Г₁, а всякая а-цепь L₂S₂ укладывается в Г₂. Но это значит, что всякая пара α-цепей L₁лежитS₁, L₂ лежит S₂ од- новременно укладывается вне Гз. Тогда они укладываются и внутри грани Гз. Но это противоречит тому, что S₁и S₂ — конфликтующие сегменты.

Итак, F(S₁) = Г(S₂) = 0.

От противного легко показать, что|0|= 2. Пусть |0|  3. Тогда существует по крайней мере три различных грани Г₁, Г₂, Гз  0. Поэтому, повторяя предыдущие рас­суждения, получаем противоречие.

Построим вспомогательный граф S (G₀) по следующему правилу: каждому сегменту относительно G₀ поставим в соответствие вершину графа S(G₀), причем будем считать, что две вершины смежны тогда и только тогда, когда соответствующие им сегменты конфликтующие.

На рис. 41.2 изображен вспомо­гательный граф S(G₀), соответствую­щий сегментам ранее рассмотренного графа S (рис. 41.1) относительно G₀. При этом вершины графа S(G₀) обозначены так же, как и соответствующие им сегменты.

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

Лемма 41.2. Если результатом некоторого шага ал­горитма γ является частичная укладка G₀ планарного гра­фа G такая, что \ Г (S) \  2 для всякого сегмента S отно­сительно G₀, то S(G₀)— двудольный граф.

Доказательство проведем от противного. Пусть граф S(G₀) не двудольный. Тогда на основании теоремы Кёнига в S(G₀) есть r-цикл нечетной длины. Этому циклу соответствует последовательность Р сегментов S₁, S₂, ... ..., S_r, S₁ относительно G₀1, в которой каждые соседние сегменты конфликтующие. Поэтому на основании леммы 41.1 Г(S_i)={Г₁, Г₂} (i = i, r). Поскольку G₀ — частичная укладка графа G, то все сегменты S₁, S₂, ..., S_r могут быть уложены, а так как соседние сегменты последова­тельности Р конфликтуют, то они должны быть уложены в различные грани (Г₁ и Г₂). Но это невозможно в силу нечетности числа сегментов r.

Теорема 41.3. Если G — планарный граф, то резулътатом каждого шага алгоритма γ является частичная укладка G₀ графа G.

Доказательство проведем индукцией по числу шагов.

Полученный на начальном этапе работы алгоритма γ граф G является простым циклом, который присутствует в любой укладке графа G. Следовательно, G₀ — частичная укладка.

Пусть граф G₀, построенный на предыдущем шаге работы алгоритма γ, является частичной укладкой. Покажем, что граф G₀ U L, полученный на очередном шаге при- соединением к G₀ α -цепи L, также является частичной укладкой.

Прежде всего заметим, что не существует сегмента S относительно G₀, для которого Г(S)= ø. Действительно, если бы такой сегмент S существовал, то существовала бы и а-цепь этого сегмента, обе контактные вершины которой не принадлежат одной грани. Поэтому укладка такой цепи (и тем более сегмента S) невозможна.

Итак, могут представиться лишь следующие два случая.

Случай 1. Для некоторого сегмента S относительно G₀ существует единственная допустимая грань Г. Пусть G' — укладка графа G, из которой путем удаления вершин и ребер можно получить граф G. В этой укладке сегмент S находится в грани Г, так как только этой грани принадлежат все его контактные вершины. Это значит, что, помещая любуюа-цепь L .S в грань Г, снова получим частичную укладку графа G.

Случай 2. |Г(S)|2 для всякого сегмента S относительно G₀. Рассмотрим связную компоненту Н двудольного (по лемме 41.2) графа S(G₀), содержащую не менее двух вершин. Эта компонента также является двудольным графом, и в силу леммы 41.1 Г(S)={Г₁,Г₂ }для всякого S  H.

Пусть G' — укладка графа G, из которой путем удаления вершин и ребер можно получить граф G₀. Так как все контактные вершины каждого сегмента принадлежали только граням Г₁ и Г₂, то каждый из сегментов относительно G₀ находится в одной из этих граней. При этом сегменты, соответствующие вершинам каждой доли графа S(G₀), не конфликтуют. Поэтому в графе G' сегменты, соответствующие одной доле, находятся в грани Г₁ а сегменты, соответствующие вершинам другой доли, в грани Г₂. Если теперь сегменты, находящиеся в Г₁, поменять местами с сегментами, находящимися в Г2, то получим граф G", который также является укладкой графа G. Это значит, что всякая а-цепь любого сегмент» S  Н в любой плоской укладке графа G может быть расположена и в Г₁, и в Г₂. Иными словами, помещая α-цепь LS в любую грань, допустимую для сегмента S, полу­чаем частичную укладку графа G.

Если для некоторого сегмента S нет конфликтующих сегментов, т. е. вершина SS(G₀) является изолирован­ной, то наше утверждение очевидно.

Замечание. Если граф G не является циклом, то в процессе работы алгоритма γ встретится случай, когда |Г (S)|  2, и поэтому существуют различные укладки графа G. На рис. 41.3 показаны две возможные укладки графа G, изображенного на рис. 41.1.

Следствие 41.4. Если граф G планарный, то алго­ритм γ строит его плоскую укладку.

Следствие 41.5. Если в процессе работы алгоритма γ встретится сегмент S, для которого нет допустимой гра­ни, то граф G непланарный.

Проиллюстрируем работу алгоритма γ на примерах.

Пример 1. Пусть граф G изображен на рис. 41.4. Уложим сначала цикл С = (1, 2, 3, 4, 1), который разби­вает плоскость на две грани Г₁ и Г₂. На рис. 41.5 изобра­жены граф G₀ = C и сегменты S₁, S₂, S3 относительно G₀ с контактным вершинами, обведенными кружками. Так как Г(S_i) = {Г₁,Г₂} (i=1, 2, 3), то любую α-цепь про­извольного сегмента можно укладывать в любую допусти­мую для него грань. Поместим, например, α -цепь L =

= (2, 5, 4) в Г₁ Возникает новый граф G₀ и его сегмен­ты (рис. 41.6). При этом Г(S₁)={Г₃}, Г(S₂)={Г₁ Г₂}, Г(Sз) = {Г₁, Г₂, Гз). Укладываем цепь L = (l, 5) в Гз (рис. 41.7). Тогда Г(S₁)=(Г₁, Г₂}, Г(S₂)={Г₁, Г₂}. Да­лее, уложим α-цепь L=(2, 6, 4) сегмента S₁ в Г₁ (рис. 41.8). В результате имеем Г(S₁) = {Г₅}, Г(S₂) = (Г₁, Г₂, Гз). Наконец, уложив ребро (6, 3) в г₅, а ребро

(2, 4) —например, в Г₁, получаем укладку графа G на плоскости (рис. 41.9).

Пример 2. Пусть G = K_3,3 (рис. 41.10).

Цикл и сегменты относительно этого цикла изобра­жены на рис. 41.11. При этом Г(S_i)=

={Г₁ Г₂} (i= 1, 2, 3),

Помещаем S₁ в грань Г₂ Тогда S₂ необходимо поместить в грань Г₁ (рис. 41.12). Поскольку Г(S₁)= ø, то Kз,з — непланарный граф.