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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 13: Строка 13:
 
# Граф не имеет [[Мост, эквивалентные определения|мостов]].
 
# Граф не имеет [[Мост, эквивалентные определения|мостов]].
  
Если нарушено свойство 1, то граф нужно укладывать отдельно по компонентам связности. Если нарушено свойство 2, то граф {{---}} дерево и [[Укладка дерева|нарисовать его плоскую укладку]] тривиально.  
+
Если нарушено свойство 1, то граф нужно укладывать отдельно по компонентам связности. Если нарушено свойство 2, то граф {{---}} дерево и нарисовать его плоскую укладку тривиально.  
  
 
Более подробно рассмотрим случай, когда в графе <tex>G</tex> нарушено свойство 3. Сначала все мосты нужно убрать, далее произвести отдельную укладку всех компонент следующим образом: уложим одну компоненту связности, а следующую компоненту, связанную с первой в графе <tex>G</tex> мостом, будем рисовать в той грани, в которой лежит вершина, принадлежащая мосту. Иначе может сложиться ситуация, когда концевая вершина моста будет находиться внутри плоского графа, а следующая компонента {{---}} снаружи. Таким образом мы сможем соединить мостом нужные вершины. Далее будем так поступать с каждой новой компонентой.
 
Более подробно рассмотрим случай, когда в графе <tex>G</tex> нарушено свойство 3. Сначала все мосты нужно убрать, далее произвести отдельную укладку всех компонент следующим образом: уложим одну компоненту связности, а следующую компоненту, связанную с первой в графе <tex>G</tex> мостом, будем рисовать в той грани, в которой лежит вершина, принадлежащая мосту. Иначе может сложиться ситуация, когда концевая вершина моста будет находиться внутри плоского графа, а следующая компонента {{---}} снаружи. Таким образом мы сможем соединить мостом нужные вершины. Далее будем так поступать с каждой новой компонентой.
Строка 28: Строка 28:
 
=== Инициализация ===
 
=== Инициализация ===
  
Первый этап {{---}} '''инициализация''' алгоритма.  
+
Первый этап - '''инициализация''' алгоритма.  
  
 
В графе <tex>G</tex> выбирается [[Использование обхода в глубину для поиска цикла|любой простой цикл]] и производится его укладка на плоскость. Пусть в примере это будет цикл <tex>\{1, 2, 3, 4, 5, 6\}</tex>. После его укладки получаем две грани: <tex>\Gamma_{1}</tex> и <tex>\Gamma_{2}</tex> (рис. 2).
 
В графе <tex>G</tex> выбирается [[Использование обхода в глубину для поиска цикла|любой простой цикл]] и производится его укладка на плоскость. Пусть в примере это будет цикл <tex>\{1, 2, 3, 4, 5, 6\}</tex>. После его укладки получаем две грани: <tex>\Gamma_{1}</tex> и <tex>\Gamma_{2}</tex> (рис. 2).
Строка 40: Строка 40:
 
=== Общий шаг ===
 
=== Общий шаг ===
  
Второй этап {{---}} общий шаг.
+
Второй этап - общий шаг.
  
 
Построим множество '''сегментов'''. Каждый сегмент <tex>S</tex> относительно уже построенного <tex>G_{plane}</tex> представляет собой одно из двух:
 
Построим множество '''сегментов'''. Каждый сегмент <tex>S</tex> относительно уже построенного <tex>G_{plane}</tex> представляет собой одно из двух:
Строка 52: Строка 52:
 
|}
 
|}
  
Пусть в каком-то сегменте нет ни одной контактной вершины. В таком случае граф до выделения <tex>G_{plane}</tex> был несвязным, что противоречит условию. Пусть контактная вершина в сегменте только одна. Это значит, что в графе был мост или точка сочленения, чего быть не может так же по условию. Таким образом, в каждом сегменте имеется не менее двух контактных вершин. Соответственно, в каждом сегменте есть цепь между любой парой контактных вершин.
+
Пусть в каком-то сегменте нет ни одной контактной вершины. В таком случае граф до выделения <tex>G_{plane}</tex> был несвязным, что противоречит условию. Пусть контактная вершина в сегменте только одна. Это значит, что в графе был мост, чего быть не может так же по условию. Таким образом, в каждом сегменте имеется не менее двух контактных вершин. Соответственно, в каждом сегменте есть цепь между любой парой контактных вершин.
  
 
Пусть грань <tex>\Gamma</tex> '''вмещает''' сегмент <tex>S</tex>, если номера всех контактных вершин <tex>S</tex> принадлежат этой грани, <tex>S \subset \Gamma</tex>. Очевидно, таких граней может быть несколько. Множество таких граней обозначим <tex>\Gamma(S)</tex>, а их число {{---}} <tex>|\Gamma(S)|</tex>.
 
Пусть грань <tex>\Gamma</tex> '''вмещает''' сегмент <tex>S</tex>, если номера всех контактных вершин <tex>S</tex> принадлежат этой грани, <tex>S \subset \Gamma</tex>. Очевидно, таких граней может быть несколько. Множество таких граней обозначим <tex>\Gamma(S)</tex>, а их число {{---}} <tex>|\Gamma(S)|</tex>.
Строка 114: Строка 114:
 
|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> {{---}} конфликтующие сегменты.  
 
}}
 
}}
  
Строка 141: Строка 141:
 
|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> {{---}} не двудольный. Тогда по [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> {{---}} двудольный.
 
}}
 
}}
  
Строка 161: Строка 161:
 
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> в разные грани, причем конфликтующих сегментов не возникнет в силу четности всех циклов в графе. Результатом будет частичная укладка графа.
  
 
Таким образом, на каждом шаге мы получаем частичную укладку графа, что доказывает корректность гамма-алгоритма.
 
Таким образом, на каждом шаге мы получаем частичную укладку графа, что доказывает корректность гамма-алгоритма.
Строка 172: Строка 172:
 
==См. также==
 
==См. также==
 
* [[Теорема Понтрягина-Куратовского|Теорема Понтрягина-Куратовского]]
 
* [[Теорема Понтрягина-Куратовского|Теорема Понтрягина-Куратовского]]
* [[Теорема Фари|Теорема Фари]]
 
  
 
== Источники информации ==
 
== Источники информации ==

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

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

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