577
правок
Изменения
→Доказательство корректности гамма-алгоритма
Заметим, что на текущем шаге нет такого сегмента <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>.
}}
