577
правок
Изменения
→Доказательство корректности гамма-алгоритма
'''Замечание.''' Пусть имеется множество сегментов таких, что они удовлетворяют следующей схеме: есть первый сегмент <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. Служебный граф. Вершины обозначены как соответствующие сегменты.]]
|}
