577
правок
Изменения
→Доказательство корректности гамма-алгоритма
|statement=Конфликтующие сегменты <tex>S_{1}</tex> и <tex>S_{2}</tex> обладают следующим свойством: если <tex>|\Gamma(S_{1})| \geq 2</tex> и <tex>|\Gamma(S_{2})| \geq 2</tex>, то <tex>\Gamma(S_{1}) = \Gamma(S_{2}) = 2</tex>.
|proof=Докажем от противного. По определению они имеют одну общую вмещающую грань Сначала докажем, что <tex>\Gamma_Gamma(S_{1}) = \Gamma(S_{32})</tex>. Пусть они имеют еще Предположим противное. Тогда по собственной вмещающей условию леммы найдутся три различные грани <tex>\Gamma_{1}, \Gamma_{2}</tex> и <tex>\Gamma_{23}</tex> соответственно. Но тогда любые цепи из такие, что <tex>S_\Gamma_{1}</tex> и <tex>\in \Gamma(S_{21}</tex> могут разместиться в <tex>), \Gamma_{12}</tex> и <tex>\Gamma_in \Gamma(S_{2}</tex> соответственно), а значит, и в <tex>\Gamma_{3}\in Q = \Gamma(S_{1}) \cap \Gamma(S_{2}) \neq \emptyset</tex>, причем без пересечений, что противоречит тому, что они конфликтующие.
}}
