Редактирование: Гамма-алгоритм

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 115: Строка 115:
 
|id=lemma1
 
|id=lemma1
 
|about=1
 
|about=1
|statement=Конфликтующие сегменты <tex>S_{1}</tex> и <tex>S_{2}</tex> обладают следующим свойством: если <tex>|\Gamma(S_{1})| \geqslant 2</tex> и <tex>|\Gamma(S_{2})| \geqslant 2</tex>, то <tex>\Gamma(S_{1}) = \Gamma(S_{2}) = 2</tex>.
+
|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(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>.
 
|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| \geqslant 3</tex>. Тогда снова существует три различные грани <tex>\Gamma_{1},  \Gamma_{2}</tex> и <tex>\Gamma_{3} \in Q</tex>. Аналогичными рассуждениями снова приходим к противоречию с тем, что <tex>S_{1}</tex> и <tex>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> {{---}} конфликтующие сегменты.  
 
}}
 
}}
  
Строка 142: Строка 142:
 
|id=lemma2
 
|id=lemma2
 
|about=2
 
|about=2
|statement=Если результатом некоторого шага работы гамма-алгоритма является частичная укладка <tex>G'</tex> планарного графа <tex>G</tex> такая, что <tex>|\Gamma(S)| \geqslant 2</tex> для любого сегмента <tex>S</tex> относительно <tex>G'</tex>, то <tex>A(G')</tex> {{---}} [[Двудольные графы и раскраска в 2 цвета|двудольный граф]].
+
|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> {{---}} не двудольный. Тогда по [[Двудольные графы и раскраска в 2 цвета#Теорема Кенига|теореме Кенинга]] в нем есть цикл нечетной длины. Этому циклу соответствует некоторая последовательность сегментов  <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> {{---}} двудольный.
 
|proof=Докажем от противного. Пусть <tex>A(G')</tex> {{---}} не двудольный. Тогда по [[Двудольные графы и раскраска в 2 цвета#Теорема Кенига|теореме Кенинга]] в нем есть цикл нечетной длины. Этому циклу соответствует некоторая последовательность сегментов  <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> {{---}} двудольный.
Строка 162: Строка 162:
 
1. Существует сегмент <tex>S</tex> для которого есть единственная вмещающая грань <tex>\Gamma</tex>, то есть <tex>|\Gamma(S)| = 1</tex>. Так как только грани <tex>\Gamma</tex> принадлежат все контактные вершины <tex>S</tex>, то укладка этого сегмента в эту грань неизбежна. Это значит, что помещая любую цепь <tex>L \subset S</tex>, снова получим частичную укладку графа.
 
1. Существует сегмент <tex>S</tex> для которого есть единственная вмещающая грань <tex>\Gamma</tex>, то есть <tex>|\Gamma(S)| = 1</tex>. Так как только грани <tex>\Gamma</tex> принадлежат все контактные вершины <tex>S</tex>, то укладка этого сегмента в эту грань неизбежна. Это значит, что помещая любую цепь <tex>L \subset S</tex>, снова получим частичную укладку графа.
  
2. Для любого сегмента <tex>S</tex> <tex>|\Gamma(S)| \geqslant 2</tex>. Построим граф <tex>A(G'_{k-1})</tex>, который по лемме 2 является двудольным. Рассмотрим его связную компоненту <tex>K</tex>, которая содержит не менее двух вершин. Граф <tex>K</tex> также является двудольным. По лемме 1 для любого сегмента <tex>S \in K</tex> справедливо <tex>\Gamma(S) = \{\Gamma_{1}, \Gamma_{2}\}</tex>. Так как граф <tex>K</tex> двудольный, то мы можем по очереди помещать сегменты <tex>K</tex> в разные грани, причем конфликтующих сегментов не возникнет в силу четности всех циклов в графе. Результатом будет частичная укладка графа.
+
2. Для любого сегмента <tex>S</tex> <tex>|\Gamma(S)| \geq 2</tex>. Построим граф <tex>A(G'_{k-1})</tex>, который по лемме 2 является двудольным. Рассмотрим его связную компоненту <tex>K</tex>, которая содержит не менее двух вершин. Граф <tex>K</tex> также является двудольным. По лемме 1 для любого сегмента <tex>S \in K</tex> справедливо <tex>\Gamma(S) = \{\Gamma_{1}, \Gamma_{2}\}</tex>. Так как граф <tex>K</tex> двудольный, то мы можем по очереди помещать сегменты <tex>K</tex> в разные грани, причем конфликтующих сегментов не возникнет в силу четности всех циклов в графе. Результатом будет частичная укладка графа.
  
 
Таким образом, на каждом шаге мы получаем частичную укладку графа, что доказывает корректность гамма-алгоритма.
 
Таким образом, на каждом шаге мы получаем частичную укладку графа, что доказывает корректность гамма-алгоритма.

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)