577
правок
Изменения
→Доказательство корректности гамма-алгоритма
<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>, для которого нет вмещающей грани, то граф непланарный.
