1632
правки
Изменения
м
rollbackEdits.php mass rollback
# Граф не имеет [[Мост, эквивалентные определения|мостов]].
Если нарушено свойство 1, то граф нужно укладывать отдельно по компонентам связности. Если нарушено свойство 2, то граф {{---}} дерево и [[Укладка дерева|нарисовать его плоскую укладку ]] тривиально.
Более подробно рассмотрим случай, когда в графе <tex>G</tex> нарушено свойство 3. Сначала все мосты нужно убрать, далее произвести отдельную укладку всех компонент следующим образом: уложим одну компоненту связности, а следующую компоненту, связанную с первой в графе <tex>G</tex> мостом, будем рисовать в той грани, в которой лежит вершина, принадлежащая мосту. Иначе может сложиться ситуация, когда концевая вершина моста будет находиться внутри плоского графа, а следующая компонента {{---}} снаружи. Таким образом мы сможем соединить мостом нужные вершины. Далее будем так поступать с каждой новой компонентой.
=== Инициализация ===
Первый этап {{- --}} '''инициализация''' алгоритма.
В графе <tex>G</tex> выбирается [[Использование обхода в глубину для поиска цикла|любой простой цикл]] и производится его укладка на плоскость. Пусть в примере это будет цикл <tex>\{1, 2, 3, 4, 5, 6\}</tex>. После его укладки получаем две грани: <tex>\Gamma_{1}</tex> и <tex>\Gamma_{2}</tex> (рис. 2).
=== Общий шаг ===
Второй этап {{- --}} общий шаг.
Построим множество '''сегментов'''. Каждый сегмент <tex>S</tex> относительно уже построенного <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>S_{i}</tex> и для каждого определим число <tex>|\Gamma(S_{i})|</tex>. Если найдется такой номер <tex>i</tex>, что <tex>|\Gamma(S_{i})| = 0</tex>, то граф не планарен, алгоритм завершает работу. Иначе выбираем такой сегмент <tex>S_{i}</tex>, для которого число <tex>|\Gamma(S_{i})|</tex> минимально. Если таких сегментов несколько, можно выбрать любой из них. Найдем в этом сегменте цепь между двумя контактными вершинами и уложим ее в любую грань из множества <tex>|\Gamma(S_{i})|</tex>, совместив контактные вершины сегмента с соответствующими вершинами грани. Выбранная грань разобьется на две. Выбранный сегмент после того, как из него взяли цепь, либо исчезнет, либо распадется на меньшие части, в которых будут новые контактные вершины, ведущие к вершинам обновленного <tex>G_{plane}</tex>.
В примере для любого <tex>i</tex>: <tex>S_{i} \subset \{\Gamma_{1}, \Gamma_{2}\}</tex>, то есть <tex>|\Gamma(S_{i})| = 2</tex>. Следовательно, можем выбрать любой <tex>S_{i}</tex>. Пусть это будет сегмент <tex>S_{1}</tex>. В нем есть цепь <tex>\{1, 4\}</tex>. Вставим эту цепь в грань <tex>\Gamma_{1}</tex>, например, и этот сегмент исчезнет. После укладки цепи граф <tex>G</tex> и сегменты будут выглядеть так (рис. 4):
|id=lemma1
|about=1
|statement=Конфликтующие сегменты <tex>S_{1}</tex> и <tex>S_{2}</tex> обладают следующим свойством: если <tex>|\Gamma(S_{1})| \geq geqslant 2</tex> и <tex>|\Gamma(S_{2})| \geq geqslant 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>.
Теперь покажем, что <tex>|Q| = 2</tex>. Доказательство снова поведем методом от противного. Пусть <tex>|Q| \geq geqslant 3</tex>. Тогда снова существует три различные грани <tex>\Gamma_{1}, \Gamma_{2}</tex> и <tex>\Gamma_{3} \in Q</tex>. Аналогичными рассуждениями снова приходим к противоречию с тем, что <tex>S_{1}</tex> и <tex>S_{2}</tex> {{---}} конфликтующие сегменты.
}}
|id=lemma2
|about=2
|statement=Если результатом некоторого шага работы гамма-алгоритма является частичная укладка <tex>G'</tex> планарного графа <tex>G</tex> такая, что <tex>|\Gamma(S)| \geq geqslant 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[Двудольные графы и раскраска в 2 цвета#.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> {{---}} двудольный.
}}
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)| \geq 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> в разные грани, причем конфликтующих сегментов не возникнет в силу четности всех циклов в графе. Результатом будет частичная укладка графа.
Таким образом, на каждом шаге мы получаем частичную укладку графа, что доказывает корректность гамма-алгоритма.
==См. также==
* [[Теорема Понтрягина-Куратовского|Теорема Понтрягина-Куратовского]]
* [[Теорема Фари|Теорема Фари]]
== Источники информации ==
