Теория графов

c. Выбираем одну  из подходящих граней для выбранного  сегмента.

d. В данном  сегменте выбираем цепь между  двумя контактными вершинами  и укладываем ее в выбранной  грани. Учтем изменения в структуре сегментов, и если множество образовавшихся сегментов не пусто, перейдем к п. a). В противном случае перейдем к п.3.

3. Завершение. Построена  плоская укладка G. исходного графа  G, конец. 

Корректность  гамма-алгоритма

 

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

Назовем сегменты S1 и S2 конфликтующими относительно уже  уложенной части, если:

- существует  грань, которая вмещает каждый  из сегментов; 

- в сегментах  S1 и S2 есть две цепи (между контактными вершинами) L1 и L2 соответственно, такие, что их невозможно уложить в одну грань без пересечения.

Лемма 1

Конфликтующие сегменты S1 и S2 обладают следующим свойством: если |Г(S1)| . 2 и |Г(S2)| . 2, то Г(S1) = Г(S2) = 2.

Доказательство. Действительно, в противном случае, имея по определению одну общую вмещающую грань Г3, они бы имели еще по собственной вмещающей грани Г1 и Г2 соответственно. Тогда любые цепи из S1 и S2 могли бы разместиться в Г1 и Г2 соответственно, а значит и в Г3, причем без пересечения; следовательно, S1 и S2 не были бы конфликтующими.

Противоречие. Что и требовалось доказать.

Замечание. Из доказанной леммы следует, что, если имеется сегмент S1, и еще сегмент S2, конфликтующий с S1, затем сегмент S3, конфликтующий с S2 (но не с S1) и т. д., причем каждый вмещается в две грани, то эти грани являются общими для всех сегментов последовательности, и можно укладывать цепь L1 из S1 в первую грань Г1, L2 из S2 в Г2, L3 из S3 снова в Г1 и т. д. до конца последовательности. Если цепочка сегментов замыкается в цикл четной длины, то проблем не будет; если в нечетный цикл, то в конце окажется, что два конфликтующих сегмента нужно разместить без пересечений в общую грань, что невозможно.

Сейчас нам  понадобится в качестве вспомогательного утверждения теорема Д. Кёнига (D. Konig), которая полезна при решении и многих других задач.

Теорема (Кёнига, 1936)

В графе все  циклы четные тогда и только тогда, когда граф является двудольным.

Доказательство.

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

Необходимость. Если граф несвязный, то проведем доказательство отдельно для каждой компоненты. Пусть граф связный и все циклы в нем четные. Выделим произвольную вершину v0 и найдем произвольные цепи между v0 и всеми остальными вершинами (например, самые короткие, с помощью алгоритма Дейкстры). Если одна цепь (v0, vi) нечетной длины, то и любая цепь (v0, vi) нечетная, иначе бы эти цепи образовали нечетный цикл. Аналогично, если (v0, vi) — четная, то и любая (v0, vi) — четная. Разобьем вершины на две доли: в одну войдет вершина v0 и все, находящиеся от v0 на четном расстоянии; в другую долю поместим все вершины, находящиеся от

v0 на нечетном  расстоянии. Если вершины u1 и u2 принадлежат одной доле, то между  ними не может быть ребра,  иначе это ребро вместе с  цепями (v0, u1) и (v0, u2) образовали бы  нечетный цикл. Ч. т. д.

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

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

В частичной  укладке G. сопоставим каждому сегменту вершину в некотором постороннем  служебном графе A(G.), где вершины  соединяются ребрами, если соответствующие  сегменты являются конфликтующими.

 

 

 

 

 

 

Лемма 2

Если результатом  некоторого шага работы гамма-алгоритма  является частичная укладка G. планарного графа G такая, что |Г(S)| . 2 для любого сегмента S относительно G., то A(G.) —  двудольный граф.

Доказательство. Докажем от противного. Пусть A(G.) — не двудольный, тогда по теореме Кенига в нем есть r - цикл нечетной длины. Этому циклу соответствует последовательность P сегментов S1, S2,…, Sr, S1 относительно G., в которой каждые соседние сегменты конфликтующие. Поэтому на основании Леммы 1 Г(Si) = {Г1, Г2} (i = 1..r). Так как G. - частичная укладка графа, то все сегменты S1, S2,…, Sr могут быть уложены, а так как соседние сегменты последовательности P конфликтующие, то они должны быть уложены в различные грани (Г1, Г2). Но это невозможно в силу нечетности числа сегментов r. Противоречие. Что и требовалось доказать. 

Теорема (о корректности гамма-алгоритма)

Гамма-алгоритм корректен, то есть, если G — планарный  граф, то результатом каждого шага гамма-алгоритма является частичная  укладка G.

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

Пусть граф G.k.1, полученный на (k.1)-м шаге, является частичной  укладкой. На текущем шаге к нему присоединится цепь L: G.k = G.k.1 U L. Докажем, что граф G.k — тоже частичная укладка. Среди сегментов на текущем шаге нет такого S, что |Г(S)| = 0, иначе G.k.1 не был бы частичной

укладкой. Значит, либо существует S такой, что |Г(S)| = 1, либо все S таковы, что |Г(S)| . 2.

Первый случай означает, что укладка S в Г неизбежна, так что граф G.k после добавления цепи из S останется частичной укладкой. Во втором случае построим граф A(G.k.1), по Лемме 2 он двудольный. Возьмем его  связную компоненту A., этот граф тоже двудольный. Для сегментов из A. имеются ровно две грани Г1 и Г2, вмещающие их. Раскидаем сегменты A. по граням Г1 и Г2 попеременно. В итоге будет получена частичная укладка.

Фактически, основой  последней части доказательства было, что если граф A(G.k.1) двудольный, то после удаления части ребер и вершин граф A(G.k) тоже двудольный. Таким образом, в результате каждой итерации для планарного графа частичная укладка увеличивается, в конце мы получим

плоскую укладку. Что и требовалось доказать.

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

Замечание. В источнике [1] перед доказательством теоремы о корректности приведена лемма, утверждающая, что для любого сегмента S верно |Г(S)| . 2. Это утверждение ошибочно, так как нетрудно найти пример показывающий ситуацию, где |Г(S)| > 2. Рассмотрим следующий пример (см. рис. 10).

 

 

 

 

 

Рис. 10

На шаге инициализации  выберем простой цикл {1, 2, 3, 4, 5, 6, 7} , это будет уже уложенная  часть графа, G’. Затем, к получившемуся графу G’ добавим сегмент 2 – 6. На следующем шаге мы уложим цепь 2 – 5 в одну из граней (2-3-4-5-6): мы видим, что теперь оставшуюся цепь 2 - 8 - 5 мы можем уложить в грани Г2 ,Г3 и Г4 (см. рис. 11).

 

 

 

Литература

 

1. Новиков Ф.А.  Дискретная математика для программистов. СПб.: Питер, 2004.

2. Зыков А.А.  Основы теории графов.  М.: Наука, 1987.

3. Кристофидес  М. Теория графов. Алгоритмический  подход. М.: Мир, 1978.

4. Ловас Л., Пламер Л. Прикладные задачи теории графов. М.: Мир, 1998.
5. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981.
6. Бондарев В.М., Рублинецкий В.И., Качко Е.Г. Основы программирования. — Харьков: Фолио; Ростов н/Д: Феникс, 1997.
7. Емеличев Р.И., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. — М.: Наука, 1990.
8. Харари Ф. Теория графов. – М.: Мир, 1973.