577
правок
Изменения
Нет описания правки
Гамма-алгоритм корректен, то есть если <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>2.</tex> Для любого сегмента <tex>S</tex> <tex>|\Gamma(S)| \geq 2</tex>.
}}
