577
правок
Изменения
Нет описания правки
#* эта цепь укладывается в любую грань, вмещающую данный сегмент
# Либо получена плоская укладка графа, либо граф оказался не планарен.
= Доказательство корректности гамма-алгоритма =
Перед доказательством корректности приведем ряд важных вспомогательных лемм.
Пусть два сегмента <tex>S_{1}</tex> и <tex>S_{2}</tex> называются '''конфликтующими''' относительно уже уложенной части, если:
# грань вмещает каждый из сегментов <tex>S_{1}</tex> и <tex>S_{2}</tex>
# в этих сегментах есть две цепи между контактными вершинами <tex>L_{1}</tex> и <tex>L_{2}</tex> соответственно такие, что их невозможно уложить в одну грань без пересечения
Например, на рис. 1 конфликтующими являются сегменты <tex>S_{1}</tex> и <tex>S_{2}</tex>.
{| cellpadding="2"
| || [[Файл:Гамма-алгоритм8.jpg|thumb|left|520px|Рис. 1. Конфликтующие сегменты.]]
|}
{{Лемма
|id=lemma1
|about=1
|statement=Конфликтующие сегменты <tex>S_{1}</tex> и <tex>S_{2}</tex> обладают следующим свойством: если <tex>|\Gamma(S_{1})| \geq 2</tex> и <tex>|\Gamma(S_{2})| \geq 2</tex>, то <tex>\Gamma(S_{1}) = \Gamma(S_{2}) = 2</tex>.
|proof=Сначала докажем, что <tex>\Gamma(S_{1}) = \Gamma(S_{2})</tex>. Предположим противное. Тогда по условию леммы найдутся три различные грани <tex>\Gamma_{1}, \Gamma_{2}</tex> и <tex>\Gamma_{3}</tex> такие, что <tex>\Gamma_{1} \in \Gamma(S_{1}), \Gamma_{2} \in \Gamma(S_{2}), \Gamma_{3} \in Q = \Gamma(S_{1}) \cap \Gamma(S_{2}) \neq \emptyset</tex>. Тогда любые цепи <tex>L_{1} \subset S_{1}</tex> и <tex>L_{2} \subset S_{2}</tex> укладываются в <tex>\Gamma_{1}</tex> и <tex>\Gamma_{2}</tex> соответственно. Но это значит, что любая пара цепей <tex>L_{1}</tex> и <tex>L_{2}</tex> одновременно укладывается вне грани <tex>\Gamma_{3}</tex>. Следовательно, они одновременно укладываются и внутри грани <tex>\Gamma_{3}</tex>, причем без пересечений. Но это противоречит тому, что <tex>S_{1}</tex> и <tex>S_{2}</tex> {{---}} конфликтующие сегменты. Таким образом, <tex>\Gamma(S_{1}) = \Gamma(S_{2})</tex>.
Теперь покажем, что <tex>|Q| = 2</tex>. Доказательство снова поведем методом от противного. Пусть <tex>|Q| \geq 3</tex>. Тогда снова существует три различные грани <tex>\Gamma_{1}, \Gamma_{2}</tex> и <tex>\Gamma_{3} \in Q</tex>. Аналогичными рассуждениями снова приходим к противоречию с тем, что <tex>S_{1}</tex> и <tex>S_{2}</tex> {{---}} конфликтующие сегменты.
}}
'''Замечание.''' Пусть имеется множество сегментов таких, что они удовлетворяют следующей схеме: есть первый сегмент <tex>S_{1}</tex>, второй <tex>S_{2}</tex>, который конфликтует с <tex>S_{1}</tex>, третий <tex>S_{3}</tex>, который конфликтует с <tex>S_{2}</tex>, но не с <tex>S_{1}</tex>, и так далее, причем каждый из них укладывается в две грани. Тогда из леммы 1 следует, что эти грани являются общими для всех сегментов множества и можно укладывать их следующим образом: цепь <tex>L_{1} \subset S_{1}</tex> укладывается в первую грань <tex>\Gamma_{1}</tex>, цепь <tex>L_{2} \subset S_{2}</tex> {{---}} во вторую <tex>\Gamma_{2}</tex>, <tex>L_{3} \subset S_{3}</tex> {{---}} снова в <tex>\Gamma_{1}</tex> и так для всех элементов множества. Если цепочка сегментов замыкается в цикл четной длины, то проблем никаких нет. Если длина цикла нечетная, то два последних конфликтующих сегмента нужно будет уложить в одну грань без пересечений, что по определению невозможно. Следовательно, получить плоскую укладку нельзя.
{{Определение
|definition =
'''Частичной укладкой''' <tex>G'</tex> планарного графа <tex>G</tex> называется граф, который можно получить из какой-либо укладки графа <tex>G</tex> на плоскости путем удаления некоторых ребер и вершин.
}}
Таким образом во всякую частичную укладку планарного графа <tex>G</tex> можно уложить оставшуюся часть, а именно недостающие вершины и ребра графа <tex>G</tex>.
Построим некоторый '''служебный граф''' <tex>A(G')</tex> по следующей схеме: каждому сегменту в <tex>G'</tex> сопоставим некоторую вершину в <tex>A(G')</tex>, причем две вершины будут смежны тогда и только тогда, когда соответствующие им сегменты являются конфликтующими.
Например, для графа на рис. 1 служебный граф будет иметь вид (рис. 2):
{| cellpadding="2"
| || [[Файл:Гамма-алгоритм9.jpg|thumb|left|220px|Рис. 2. Служебный граф. Вершины обозначены как соответствующие сегменты.]]
|}
{{Лемма
|id=lemma2
|about=2
|statement=Если результатом некоторого шага работы гамма-алгоритма является частичная укладка <tex>G'</tex> планарного графа <tex>G</tex> такая, что <tex>|\Gamma(S)| \geq 2</tex> для любого сегмента <tex>S</tex> относительно <tex>G'</tex>, то <tex>A(G')</tex> {{---}} [[Двудольные графы и раскраска в 2 цвета|двудольный граф]].
|proof=Докажем от противного. Пусть <tex>A(G')</tex> {{---}} не двудольный. Тогда по [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B2%D1%83%D0%B4%D0%BE%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D0%B3%D1%80%D0%B0%D1%84%D1%8B_%D0%B8_%D1%80%D0%B0%D1%81%D0%BA%D1%80%D0%B0%D1%81%D0%BA%D0%B0_%D0%B2_2_%D1%86%D0%B2%D0%B5%D1%82%D0%B0#.D0.A2.D0.B5.D0.BE.D1.80.D0.B5.D0.BC.D0.B0_.D0.9A.D0.B5.D0.BD.D0.B8.D0.B3.D0.B0 теореме Кенинга] в нем есть цикл нечетной длины. Этому циклу соответствует некоторая последовательность сегментов <tex>S_{1}, S_{2}, \cdots S_{2m+1}, S_{1}</tex> относительно <tex>G'</tex>, в которой каждые соседние сегменты конфликтующие по определению. По лемме 1 <tex>\Gamma(S_{i}) = \{\Gamma_{1}, \Gamma_{2}\}, i \in \{1 \cdots 2m+1\}</tex>. Так как <tex>G'</tex> {{---}} частичная укладка графа, то все сегменты <tex>S_{1}, S_{2}, \cdots S_{2m+1}</tex> могут быть уложены. А так как соседние сегменты этой последовательности конфликтующие, то они должны быть уложены в разные грани, что невозможно, так как число сегментов в последовательности нечетное. Получили противоречие. Следовательно, <tex>A(G')</tex> {{---}} двудольный.
}}
{{Теорема
|about=
О корректности гамма-алгоритма
|statement=
Гамма-алгоритм корректен, то есть если <tex>G</tex> {{---}} планарный граф, то результатом каждого шага гамма-алгоритма является частичная укладка <tex>G'</tex>.
|proof=Докажем индукцией по числу шагов.
'''База индукции:''' полученный на этапе инициализации граф <tex>G'_{0}</tex> является простым циклом, он будет присутствовать в любой укладке графа <tex>G</tex>. Таким образом, <tex>G'_{0}</tex> является частичной укладкой.
'''Шаг индукции:''' пусть граф <tex>G'_{k-1}</tex>, полученный на <tex>k-1</tex>-м шаге работы алгоритма, является частичной укладкой. Докажем, что граф <tex>G'_{k} = G'_{k-1} \cup L_{k}</tex>, полученный на <tex>k</tex>-м шаге присоединением цепи <tex>L_{k}</tex>, также является частичной укладкой.
Заметим, что на текущем шаге нет такого сегмента <tex>S</tex> относительно <tex>G'_{k-1}</tex>, для которого бы выполнялось равенство <tex>\Gamma(S) = \emptyset</tex>, так как в противном случае существовала бы цепь этого сегмента, контактные вершины которой принадлежали бы разным граням и укладка которой была бы невозможна. Следовательно, нельзя было бы уложить <tex>S</tex>,что противоречит тому, что <tex>G</tex> {{---}} планарный граф. Значит, мы можем рассматривать только следующие два случая:
<tex>1.</tex> Существует сегмент <tex>S</tex> для которого есть единственная вмещающая грань <tex>\Gamma</tex>, то есть <tex>|\Gamma(S)| = 1</tex>. Так как только грани <tex>\Gamma</tex> принадлежат все контактные вершины <tex>S</tex>, то укладка этого сегмента в эту грань неизбежна. Это значит, что помещая любую цепь <tex>L \subset S</tex>, снова получим частичную укладку графа.
<tex>2.</tex> Для любого сегмента <tex>S</tex> <tex>|\Gamma(S)| \geq 2</tex>. Построим граф <tex>A(G'_{k-1})</tex>, который по лемме 2 является двудольным. Рассмотрим его связную компоненту <tex>K</tex>, которая содержит не менее двух вершин. Граф <tex>K</tex> также является двудольным. По лемме 1 для любого сегмента <tex>S \in K</tex> справедливо <tex>\Gamma(S) = \{\Gamma_{1}, \Gamma_{2}\}</tex>. Так как граф <tex>K</tex> двудольный, то мы можем по очереди помещать сегменты <tex>K</tex> в разные грани, причем конфликтующих сегментов не возникнет в силу четности всех циклов в графе. Результатом будет частичная укладка графа.
Таким образом, на каждом шаге мы получаем частичную укладку графа, что доказывает корректность гамма-алгоритма.
}}
'''Следствие:''' Если граф <tex>G</tex> планарный, то гамма-алгоритм строит его плоскую укладку.
'''Следствие:''' Если на каком-то шаге встретился сегмент <tex>S</tex>, для которого нет вмещающей грани, то граф непланарный.
