577
правок
Изменения
→Доказательство корректности гамма-алгоритма
|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> {{---}} снова в первую
