577
правок
Изменения
Нет описания правки
Более подробно рассмотрим случай, когда в графе <tex>G</tex> нарушено свойство <tex>3</tex>. Сначала все мосты нужно убрать, далее произвести отдельную укладку всех компонент следующим образом: уложим одну компоненту связности, а следующую компоненту, связанную с первой в графе <tex>G</tex> мостом, будем рисовать в той грани, в которой лежит вершина, принадлежащая мосту. Иначе может сложиться ситуация, когда концевая вершина моста будет находиться внутри плоского графа, а следующая компонента - снаружи. Таким образом мы сможем соединить мостом нужные вершины. Далее будем так поступать с каждой новой компонентой.
= Описание алгоритма =
Рассмотрим работу алгоритма, параллельно разбирая на примере каждый шаг.
Пусть дан граф <tex>G</tex> (рис. 1).
{| cellpadding="2"
| || [[Файл:Гамма-алгоритм1.jpg|thumb|left|370px|Рис. 1. Исходный граф.]]
|}
<tex>1.</tex> Первый этап - '''инициализация''' алгоритма.
В графе <tex>G</tex> выбирается любой простой цикл и производится его укладка на плоскость. Пусть в примере это будет цикл <tex>\{1, 2, 3, 4, 5, 6\}</tex>. После его укладки получаем две грани: <tex>\Gamma_{1}</tex> и <tex>\Gamma_{2}</tex> (рис. 2).
{| cellpadding="2"
| || [[Файл:Гамма-алгоритм2.jpg|thumb|left|370px|Рис. 2. Укладка цикла на плоскость.]]
|}
Уже уложенную во время работы алгоритма часть будем обозначать <tex>G_{plane}</tex>. В примере сейчас <tex>G_{plane}</tex> {{---}} выбранный цикл <tex>\{1, 2, 3, 4, 5, 6\}</tex>.
<tex>2.</tex> Второй этап - общий шаг.
Построим множество '''сегментов'''. Каждый сегмент <tex>S</tex> относительно уже построенного <tex>G_{plane}</tex> представляет собой одно из двух:
# ребро, оба конца которого принадлежат <tex>G_{plane}</tex>, но само оно не принадлежит <tex>G_{plane}</tex>,
# связную компоненту графа <tex>G \backslash G_{plane}</tex>, дополненную всеми ребрами графа <tex>G</tex> такими, у которых один из концов принадлежит связной компоненте, а второй принадлежит графу <tex>G_{plane}</tex>.
Вершины, одновременно принадлежащие <tex>G_{plane}</tex> и какому-либо сегменту, назовем '''контактными'''. На рис. 3 изображены сегменты для нашего примера. Контактные вершины обведены в квадрат.
{| cellpadding="2"
| || [[Файл:Гамма-алгоритм3.jpg|thumb|left|370px|Рис. 3. Выделение сегментов.]]
|}
Пусть в каком-то сегменте нет ни одной контактной вершины. В таком случае граф до выделения <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):
{| cellpadding="2"
| || [[Файл:Гамма-алгоритм4.jpg|thumb|left|500px|Рис. 4. Граф и сегменты после второго этапа.]]
|}
<tex>3.</tex> Третий и последующие этапы аналогичны второму. Повторять вышеуказанные действия нужно либо до тех пор, пока не будет получена плоская укладка, то есть множество сегментов не останется пустым, либо пока не будет получено, что граф не планарен.
Разберем пример до конца. Повторим снова общий шаг. Теперь <tex>|\Gamma(S_{1})| = |\Gamma(S_{3})| = 1</tex>, <tex>|\Gamma(S_{2})| = |\Gamma(S_{4})| = 2</tex>. Возьмем <tex>S_{1}</tex>. В ней цепь <tex>\{2, 5\}</tex>, которую мы уложим в грань <tex>\Gamma_{2}</tex>, после чего этот сегмент исчезнет. Теперь картина будет следующая (рис. 5):
{| cellpadding="2"
| || [[Файл:Гамма-алгоритм5.jpg|thumb|left|500px|Рис. 5. Граф и сегменты после третьего этапа.]]
|}
На следующем шаге <tex>|\Gamma(S_{1})| = |\Gamma(S_{3})| = 2</tex>, <tex>|\Gamma(S_{2})| = 1</tex>. Выбираем сегмент <tex>S_{2}</tex>, содержащий цепь <tex>\{3, 5\}</tex>. Уложим ее в грань <tex>\Gamma_{2}</tex>, после чего этот сегмент снова исчезнет (рис. 6).
{| cellpadding="2"
| || [[Файл:Гамма-алгоритм6.jpg|thumb|left|500px|Рис. 6. Граф и сегменты после четвертого этапа.]]
|}
Теперь <tex>|\Gamma(S_{1})| = 1</tex>, а <tex>|\Gamma(S_{3})| = 2</tex>. Уложим сначала цепь <tex>\{2, 4\}</tex> из первого сегмента, он пропадет, потом уложим цепь <tex>\{6, 7, 5\}</tex> из третьего. В результате граф будет полностью уложен на плоскость, множество сегментов останется пустым (рис. 7).
{| cellpadding="2"
| || [[Файл:Гамма-алгоритм7.jpg|thumb|left|300px|Рис. 7. Плоская укладка графа.]]
|}
Таким образом, мы получили плоскую укладку исходного графа <tex>G</tex>.
Опишем алгоритм коротко и формально:
# Инициализация. Выбирается простой цикл в исходном графе и изображается на плоскости.
# Общий шаг. Этот шаг повторяется до тех пор, пока граф не будет уложен или пока не будет получено, что граф не планарен.
#* строится множество сегментов
#* для каждого сегмента вычисляется величина <tex>|\Gamma(S)|</tex>. Если существует <tex>i</tex>: <tex>|\Gamma(S_{i})| = 0</tex>, то граф не планарен, алгоритм завершает работу
#* выбирается сегмент с минимальным числом <tex>|\Gamma(S_{i})|</tex>
#* в этом сегменте выбирается цепь между двумя контактными вершинами
#* эта цепь укладывается в любую грань, вмещающую данный сегмент
# Либо получена плоская укладка графа, либо граф оказался не планарен.
