Первая страница / Теория / Графы. Раскраски и укладки /

Плоская укладка

Голосование: 27, 12

В данной статье будет рассмотрена задача на графах о возможности нарисовать тот или иной граф без самопересечений. То есть нарисовать граф так, чтобы его ребра не имели общих внутренних точек. Поставленную задачу принято называть задачей о плоской укладке графа.

Область применения результата, который мы получим, очень обширна. Одна из них — это изготовление электронных схем. Электрические цепи печатным способом наносятся на плату из изолирующего материала. Так как наносимые цепи не изолированы, то они не должны пересекаться. Отсюда вытекает вопрос, как расположить контакты на схеме, чтобы можно было без пересечений нанести цепи на плату. А если так сделать нельзя, то каким минимальным числом плат (слоев графа) можно обойтись.

Мы коснемся только первой части вопроса и ответим, когда и как можно нарисовать граф без самопересечений.

Основные определения

Плоский граф — это граф, нарисованный таким образом, что его ребра не пересекаются. Говорят, что граф допускает плоскую укладку, если его можно нарисовать как плоский. Также плоские графы называют планарными.

  • Граф, изображенный на рис. 1, плоский:

    Рис. 1. Плоский граф
  • Существуют и непланарные графы. На рис. 2 показаны два таких графа: полный пятивершинник и полный двудольный граф. Для них есть специальные обозначения: K5 и K3,3 соответственно.

    Рис. 2. Примеры непланарных графов

Двудольный граф — это граф, вершины которого разбиты на две доли (части), а ребра проходят только между вершинами из разных частей.

В планарном графе можно говорить не только о вершинах и ребрах, но и о гранях.

Грань — это часть плоскости, окруженная простым циклом и не содержащая внутри себя других элементов графа.

Внешняя грань — это вся плоскость, окружающая плоский граф.

Задача о плоской укладке

Задача. Определить, является ли граф планарным, и, если да, то произвести его плоскую укладку.

Замечание. Если на ребра планарного графа нанести произвольное число вершин степени 2, то он останется планарным; равным образом, если на ребра непланарного графа нанести вершины степени 2, то он планарным не станет.

В конце 1920-х годов Куратовский в Польше и Л.С. Понтрягин в СССР независимо доказали поразительную теорему, показывающую, что мешает графу быть планарным.

Теорема (Понтрягин-Куратовский)

Граф планарен тогда и только тогда, когда он не содержит в качестве частей графы К5 и К3,3 (быть может с добавочными вершинами степени 2).

Мы опустим достаточно сложное доказательство этой теоремы. Заинтересованный читатель сможет найти его в [2]. Однако не следует думать, что раз трудностей всего две, то непланарных графов мало: при росте числа вершин непланарны почти все графы.

Рассмотренный критерий очень трудоемок для проверки и поэтому представляет лишь теоретический интерес.

Гамма-алгоритм

Для плоской укладки графа и попутной проверки, планарен ли он, удобно пользоваться гамма-алгоритмом.

На вход подаются графы, обладающие следующими свойствами:

  1. граф связный;
  2. граф имеет хотя бы один цикл;
  3. граф не имеет мостиков, т. е. ребер, после удаления которых граф распадается на две компонеты связности.

Если нарушено свойство (1), то граф нужно укладывать отдельно по компонентам связности.

Если нарушено свойство (2), то граф — дерево и нарисовать его плоскую укладку тривиально.

Случай нарушения свойства (3) рассмотрим более подробно. Если в графе есть мостики, то их нужно разрезать, провести отдельно плоскую укладку каждой компоненты связности, а затем соединить их мостиками. Здесь может возникнуть трудность: в процессе укладки концевые вершины мостика могут спрятаться внутри плоского графа. Нарисуем одну компоненту связности и будем присоединять к ней другие последовательно. Каждую новую компоненту связности будем рисовать в той грани, в которой лежит концевая вершина соответствующего мостика. Так как граф связности мостиками компонент связности является деревом, мы сумеем получить плоскую укладку.

Сначала изложим алгоритм на конкретном примере. Пусть дан граф G (см. рис. 3).

Рис. 3

Инициализация алгоритма производится так: выбираем любой простой цикл; в нашем примере {1, 2, 3, 4, 5, 6, 7, 8} и получаем две грани: Γ1 — внешнюю и Γ2 — внутреннюю (см. рис. 4).

Рис. 4

Обозначим выбранный цикл как G′. На каждом шаге будем строить множество сегментов. Каждый сегмент S относительно уже построенного графа G′ представляет собой одно из двух:

  • ребро, оба конца которого принадлежат G′, но само оно не принадлежит G′;
  • связную компоненту графа G – G′, дополненную всеми ребрами графа G, один из концов которых принадлежит связной компоненте, а второй из графа G′.

Те вершины, которые одновременно принадлежат G′ и какому-то сегменту, назовем контактными. Для нашего примера сегменты и вершины изображены на рис. 5. Контактные вершины обведены в квадрат.

Рис. 5

Если бы в каком-нибудь сегменте не было ни одной контактной вершины, то граф до разрезания был бы несвязный; если бы была только одна, то граф имел бы мостик. Эти возможности заранее исключены, так что каждый сегмент имеет не менее двух контактных вершин. Поэтому в каждом сегменте имеется цепь между любой парой таких вершин.

Если все контактные вершины сегмента S имеют номера вершин какой-то грани Γ, то мы будем говорить, что грань Γ вмещает этот сегмент и обозначать S⊂Γ. Может быть имеется не одна такая грань, вмещающая сегмент S, множество таких граней обозначим Γ(S), а их число |Γ(S)|.

Общий шаг алгоритма следующий: обозреваются все сегменты Si и определяются числа |Γ(Si)|. Если хоть одно из них равно 0, то граф не планарен, конец. Иначе, выбираем сегмент, для которого число |Γ(S)| минимально, или один из множества, если таких сегментов несколько. В этом сегменте найдем цепь между двумя контактными вершинами и уложим ее в любую из граней множества Γ(S), совместив контактные вершины сегмента с соответствующими вершинами грани. При этом данная грань разобьется на две. Уже уложенная часть графа G′ по количеству ребер и вершин увеличится, а сегмент, из которого вынута цепь, исчезнет или развалится на меньшие с новыми контактными вершинами, ведущими к вершинам G′.

В результате повторения общего шага либо будет получена плоская укладка, когда множество сегментов станет пустым, либо будет получено, что граф G не является планарным.

Вернемся к нашему примеру. Пока для любого i: Si⊂{Γ1, Γ2}, |Γ(Si)| = 2. Поэтому возьмем первый по номеру сегмент Si и в нем первую попавшеюся цепь {4, 8}; вставим эту цепь в грань Γ2. Получим увеличенную часть G′ и уменьшенную систему сегментов (см. рис. 6 a, b).

Рис. 6

Определим какие грани вмещают новые сегменты. Теперь сегменты S1 и S2 вмещаются только в одну грань Γ1, в то время, как сегмент S3 вмещается в две грани Γ1 и Γ3. Поэтому берем S1. Возьмем в нем цепь между контактными вершинами, например, {2, 7}, и уложим ее в Γ1. Получим увеличенную часть G′ и уменьшенную систему сегментов (см. рис. 7 a, b).

Рис. 7

Продолжая таким образом, в итоге получим плоскую укладку G (см. рис. 8).

Рис. 8

Еще раз опишем гамма-алгоритм компактно и займемся его обоснованием.

Гамма-алгоритм

  1. (Инициализация). Выберем любой простой цикл C исходного графа G; изобразим его на плоскости в виде грани, которую примем за уже уложенную часть G′; сформируем сегменты Si; если множество сегментов пусто, то перейти к п. 3.
  2. (Общий шаг). Пока множество сегментов непусто:
    1. Для каждого сегмента S найти множество Γ(S). Если существует сегмент S, для которого |Γ(S)| = 0, то граф не планарный, конец.
    2. Выбираем один из сегментов с минимальным числом, вмещающих его граней.
    3. Выбираем одну из подходящих граней для выбранного сегмента.
    4. В данном сегменте выбираем цепь между двумя контактными вершинами и укладываем ее в выбранной грани. Учтем изменения в структуре сегментов и перейдем к п. a).
  3. (Завершение). Построена плоская укладка G′ исходного графа G, конец.

Корректность гамма-алгоритма

Вначале докажем ряд впомогательных утверждений.

Лемма 1

Для любого сегмента |Γ(S)| ≤ 2.

Доказательство. Действительно, если все контактные вершины одного сегмента принадлежат некоторой грани Γ (точнее, циклу, окружающему эту грань), то они могут принадлежать все вместе только одной еще грани, а именно внутренней или внешней. Ч. т. д.

Назовем сегменты S1 и S2 конфликтующими относительно уже уложенной части, если:

  • существует грань, которая вмещает каждый из сегментов;
  • в сегментах S1 и S2 есть две цепи (между контактными вершинами) L1 и L2 соответственно, такие, что их невозможно уложить в одну грань без пересечения.

Лемма 2

Конфликтующие сегменты S1 и S2 обладают следующим свойством: если |Γ(S1)| = 2 и |Γ(S2)| = 2, то Γ(S1) = Γ(S2).

Доказательство. Действительно, в противном случае, имея по определению одну общую вмещающую грань Γ3, они бы имели еще по собственной вмещающей грани Γ1 и Γ2 соответственно. Тогда любые цепи из S1 и S2 могли бы разместиться в Γ1 и Γ2 соответственно, а значит и в Γ3, причем без пересечения; следовательно S1 и S2 не были бы конфликтующими. Противоречие. Лемма доказана.

Замечание. Из доказанной леммы следует, что, имея сегмент S1, и еще сегмент S2, конфликтующий с S1, затем сегмент S3, конфликтующий с S2 (но не с S1) и т. д., причем каждый вмещается в две грани, то эти грани общие для всех сегментов последовательности, и можно размещать цепь L1 из S1 в первую грань Γ1, L2 из S2 в Γ2, L3 из S3 снова в Γ1 и т. д. до конца последовательности. Если цепочка сегментов замыкается в цикл четной длины, то проблем не будет; если в нечетный цикл, то в конце окажется, что два конфликтующих сегмента нужно разместить без пересечений в общую грань, что невозможно.

Сейчас нам понадобится в качестве вспомагательного утверждения теорема Кенига, которая полезна при решении и многих других задач.

Теорема (Кениг)

В графе все циклы четные тогда и только тогда, когда граф является двудольным.

Доказательство.

Достаточность. Рассмотрим двудольный граф. Начнем цикл в верхней доли. Нужно пройти по четному числу ребер, чтобы подняться снова в верхнюю долю. Следовательно, при замыкании цикла число ребер будет четным.

Необходимость. Если граф несвязный, то проведем доказательство отдельно для каждой компоненты. Пусть граф связный и все циклы в нем четные. Выделим произвольную вершину v0 и найдем произвольные цепи между v0 и всеми остальными вершинами (например, самые короткие алгоритмом Дейкстры). Если одна цепь (v0vi) нечетной длины, то и любая цепь (v0vi) нечетная, иначе бы эти цепи образовали нечетный цикл. Аналогично, если (v0vi) — четная, то и любая (v0vi) — четная. Разобьем вершины на две доли: в одну войдет вершина v0 и все, находящиеся от v0 на четном расстоянии; в другую долю поместим все вершины, находящиеся от v0 на нечетном расстоянии. Если вершины u1 и u2 принадлежат одной доле, то между ними не может быть ребра, иначе это ребро вместе с цепями (v0u1) и (v0u2) образовали бы нечетный цикл. Ч. т. д.

Частичной укладкой G′ планарного графа G называется граф, который можно получить из какой-нибудь укладки графа G на плоскости удалением каких-то ребер и вершин. Таким образом, частичная укладка — это правильное начало укладки, в ней еще не сделано ошибок.

В частичной укладке G′ сопоставим каждому сегменту вершину в некотором постороннем служебном графе A(G′), где вершины соединяются ребрами, если соответствующие сегменты являются конфликтующими.

Лемма 3

Если результатом некоторого шага работы гамма-алгоритма является частичная укладка G′ планарного графа G такая, что |Γ(S)| = 2 для любого сегмента S относительно G′, то A(G′) — двудольный граф.

Доказательство. Пусть A(G′) — не двудольный, тогда по теореме Кенига в нем есть цикл нечетной длины. По Лемме 2 все вершины этого цикла вмещаются ровно двумя гранями. Поскольку цикл нечетный, мы не сможем уложить эти сегменты в две грани. Противоречие. Лемма доказана.

Ну вот, мы наконец-то подошли к тому, чтобы доказать нужную теорему.

Теорема

Гамма-алгоритм корректен, то есть, если G — планарный граф, то результатом каждого шага гамма-алгоритма является частичная укладка G′.

Доказательство. Докажем индукцией по числу шагов.

База индукции очевидна: результат инициализации есть плоская укладка, так как уложенный цикл будет в любой укладке.

Пусть граф Gk−1, полученный на (k−1)-м шаге, является частичной укладкой. На текущем шаге к нему присоединится цепь L: Gk = Gk−1 ∪ L. Докажем, что граф Gk — тоже частичная укладка. Среди сегментов на текущем шаге нет такого S, что |Γ(S)| = 0, иначе Gk−1 не был бы частичной укладкой. Значит, либо существует S такой, что |Γ(S)| = 1, либо все S таковы, что |Γ(S)| = 2.

Первый случай означает, что укладка S в Γ неизбежна, так что граф Gk после добавления цепи из S останется частичной укладкой. Во втором случае построим граф A(Gk−1), по Лемме 3 он двудольный. Возьмем его связную компоненту A′, этот граф тоже двудольный. Для сегментов из A′ имеются ровно две грани Γ1 и Γ2, вмещающие их. Раскидаем сегменты A′ по граням Γ1 и Γ2 попеременно. Это необходимо сделать в каждой частичной укладке, следовательно получена частичная укладка.

Фактически, основой последней части доказательства было, что если граф A(Gk−1) — двудольный, то после удаления части ребер и вершин граф A(Gk) тоже двудольный. Таким образом, в результате каждой итерации для планарного графа частичная укладка увеличивается, в конце мы получим плоскую укладку.

Литература

  1. Бондарев В.М., Рублинецкий В.И., Качко Е.Г. Основы программирования. — Харьков: Фолио; Ростов н/Д: Феникс, 1997.
  2. Емеличев Р.И., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. — М.: Наука, 1990.

Джанмухамедов Вадим


Погорский Николай / 2005-01-23 18:17:43

В описании гамма-алгоритма плоской укладки графа содержится грубая ошибка <...> что в дальнейшем может привести к неправильному выводу о непланарности графа.

Спасибо за внимательное изучение материалов сайта! Статья исправлена.

Вот какой бред написан в статье:

Плоский граф — это граф, нарисованный таким образом, что его ребра не пересекаются. Говорят, что граф допускает плоскую укладку, если его можно нарисовать как плоский. Также плоские графы называют планарными.

А вот это уже не бред:

Планарный - это граф, который изоморфен плоскому.
Планарный граф это граф с пересечениями, но допускающий его плоскую укладку.

Нет дороги иди в педагоги!

Терминологическое замечание правильное, и передано автору для внесения исправления.

На обдумывание вашей рекомендации относительно возможного трудоустройства у него есть еще несколько лет до окончания цикла дневного обучения.

Денисов Николай / 2016-10-01 19:32:41

Чем графы могут помочь в программировании?

Граф --- это математическая модель. Для различных моделей разработаны алгоритмы решения соответствующих им задач. Зная алгоритм, можно приступать к программированию.

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий