Изменения

Перейти к: навигация, поиск

Обсуждение участницы:Анна

8 байт убрано, 11:34, 19 ноября 2015
Доказательство корректности гамма-алгоритма
}}
'''Замечание.''' Пусть имеется множество сегментов таких, что они удовлетворяют следующей схеме: есть первый сегмент <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> {{---}} снова в <tex>\Gamma_{1}</tex> и так для всех элементов множества. Если цепочка сегментов замыкается в цикл четной длины, то проблем никаких нет. Если длина цикла нечетная, то два последних конфликтующих сегмента нужно будет уложить в одну грань без пересечений, что по определению невозможно. Следовательно, получить плоскую укладку невозможнонельзя.
577
правок

Навигация