577
правок
Изменения
→Доказательство корректности гамма-алгоритма
|statement=Если результатом некоторого шага работы гамма-алгоритма является частичная укладка <tex>G'</tex> планарного графа <tex>G</tex> такая, что <tex>|\Gamma(S)| \geq 2</tex> для любого сегмента <tex>S</tex> относительно <tex>G'</tex>, то <tex>A(G')</tex> {{---}} [[Двудольные графы и раскраска в 2 цвета|двудольный граф]].
|proof=Докажем от противного. Пусть <tex>A(G')</tex> {{---}} не двудольный. Тогда по [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B2%D1%83%D0%B4%D0%BE%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D0%B3%D1%80%D0%B0%D1%84%D1%8B_%D0%B8_%D1%80%D0%B0%D1%81%D0%BA%D1%80%D0%B0%D1%81%D0%BA%D0%B0_%D0%B2_2_%D1%86%D0%B2%D0%B5%D1%82%D0%B0#.D0.A2.D0.B5.D0.BE.D1.80.D0.B5.D0.BC.D0.B0_.D0.9A.D0.B5.D0.BD.D0.B8.D0.B3.D0.B0 теореме Кенинга] в нем есть цикл нечетной длины. Этому циклу соответствует некоторая последовательность сегментов <tex>S_{1}, S_{2}, \cdots S_{2m+1}, S_{1}</tex> относительно <tex>G'</tex>, в которой каждые соседние сегменты конфликтующие по определению. По лемме 1 <tex>\Gamma(S_{i}) = \{\Gamma_{1}, \Gamma_{2}\}, i \in \{1 \cdots 2m+1\}</tex>. Так как <tex>G'</tex> {{---}} частичная укладка графа, то все сегменты <tex>S_{1}, S_{2}, \cdots S_{2m+1}</tex> могут быть уложены. А так как соседние сегменты этой последовательности конфликтующие, то они должны быть уложены в разные грани, что невозможно, так как число сегментов в последовательности нечетное. Получили противоречие. Следовательно, <tex>A(G')</tex> {{---}} двудольный.
}}
