Как сделать планарный граф

Добавил пользователь Morpheus
Обновлено: 04.10.2024

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Инициализация алгоритма производится так: выбираем любой простой цикл; в нашем примере и получаем две грани: Γ₁ — внешнюю и Γ₂ — внутреннюю (см. рис. 4).

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

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

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

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

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

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

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

Определим какие грани вмещают новые сегменты. Теперь сегменты S ₁ и S ₂ вмещаются только в одну грань Γ₁, в то время, как сегмент S ₃ вмещается в две грани Γ₁ и Γ₃. Поэтому берем S ₁. Возьмем в нем цепь между контактными вершинами, например, , и уложим ее в Γ₁. Получим увеличенную часть G ′ и уменьшенную систему сегментов (см. рис. 7 a, b).

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

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

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

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

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

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

   Лемма 1

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

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

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

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

   Лемма 2

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

   Доказательство. Действительно, в противном случае, имея по определению одну общую вмещающую грань Γ₃, они бы имели еще по собственной вмещающей грани Γ₁ и Γ₂соответственно. Тогда любые цепи из S ₁ и S ₂ могли бы разместиться в Γ₁ и Γ₂ соответственно, а значит и в Γ₃, причем без пересечения; следовательно S ₁ и S ₂ не были бы конфликтующими. Противоречие. Лемма доказана.

   Замечание. Из доказанной леммы следует, что, имея сегмент S ₁, и еще сегмент S ₂, конфликтующий с S ₁, затем сегмент S ₃, конфликтующий с S ₂ (но не с S ₁) и т. д., причем каждый вмещается в две грани, то эти грани общие для всех сегментов последовательности, и можно размещать цепь L ₁ из S ₁ в первую грань Γ₁, L ₂ из S ₂ в Γ₂, L ₃ из S ₃ снова в Γ₁ и т. д. до конца последовательности. Если цепочка сегментов замыкается в цикл четной длины, то проблем не будет; если в нечетный цикл, то в конце окажется, что два конфликтующих сегмента нужно разместить без пересечений в общую грань, что невозможно.

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

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

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

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

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

   Необходимость. Если граф несвязный, то проведем доказательство отдельно для каждой компоненты. Пусть граф связный и все циклы в нем четные. Выделим произвольную вершину v ₀и найдем произвольные цепи между v ₀ и всеми остальными вершинами (например, самые короткие алгоритмом Дейкстры). Если одна цепь ( v ₀, v_i ) нечетной длины, то и любая цепь ( v ₀, v_i ) нечетная, иначе бы эти цепи образовали нечетный цикл. Аналогично, если ( v ₀, v_i ) — четная, то и любая ( v ₀, v_i ) — четная. Разобьем вершины на две доли: в одну войдет вершина v ₀ и все, находящиеся от v ₀ на четном расстоянии; в другую долю поместим все вершины, находящиеся от v ₀ на нечетном расстоянии. Если вершины u ₁ и u ₂ принадлежат одной доле, то между ними не может быть ребра, иначе это ребро вместе с цепями ( v ₀, u ₁) и ( v ₀, u ₂) образовали бы нечетный цикл. Ч. т. д.

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

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

   Лемма 3

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

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

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

   Теорема

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

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

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

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

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

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

   Литература

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

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

   Планарность графов
   Один и тот же граф возможно изобразить различными способами
   (с точностью до изоморфизма). При этом большое значение
   уделяется вопросам планарности.
   Примеры: 1) при изготовлении электронных микросхем
   необходимо выяснить, можно ли схему устройства изобразить на
   плоскости без пересечений проводников; 2) при проектировании
   транспортных путей возможно избежать нежелательных
   перекрестков и т.д.
   2
   

   G1 – планарный граф,
   G2 – его плоская укладка
   Граф G1 называется планарным,
   если существует изоморфный
   ему граф G2, в изображении
   которого на плоскости ребра
   пересекаются только в
   вершинах.
   Все планарные графы
   укладываются на плоскости, т.е.
   имеют плоскую укладку.
   3
   

   Теорема 1. Любая часть (подграф) планарного графа есть
   планарный граф.
   Теорема 2. Граф планарен тогда и только тогда, когда каждая
   связная компонента этого графа – планарный граф
   4
   

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

   Граф G имеет три грани: Г1, Г2,
   Г3
   Неограниченная грань Г1 –
   внешняя
   Ограниченные грани Г2 и Г3 –
   внутренние
   6
   

   Пусть n, m, f - число вершин, ребер и граней планарного графа
   соответственно
   Теорема Эйлера
   Для всякого связного планарного графа верно равенство:
   n – m + f =2
   7
   

   Рассмотрим операцию подразбиения ребра
   в графе.
   Операция подразбиения ребра ,
   образованного парой вершин A и B, состоит в
   удалении ребра e и добавлении двух новых
   ребер e1 и e2, отвечающих парам вершин A,
   D и B, D соответственно.
   Здесь D - новая (дополнительная) вершина
   графа.
   G1 - граф до операции подразбиения ребра e,
   G2 – граф, получившийся в результате этой
   операции.
   Два графа называются гомеоморфными, если
   они могут быть получены из одного и того же
   графа подразбиением его ребер.
   8
   

   Вопрос о распознавании планарности графа являлся в свое время
   серьезной математической проблемой, которую на сегодняшний
   день удалось решить.
   12
   

   Некоторые критерии планарности графов
   Теорема Понтрягина-Куратовского. Граф планарен тогда и только
   тогда, когда он не содержит подграфов, гомеоморфных K5 или K3,3.
   Теорема
   Граф планарен тогда и только тогда, когда в нем нет подграфов,
   стягиваемых (т.е. получаемых последовательностью
   отождествлений вершин, связанных ребрами) к графам K5 или K3,3.
   13
   

   Для непланарных графов вводятся характеристики,
   представляющие ту или иную меру непланарности.
   Если граф непланарен, то для его геометрической реализации
   удаляют отдельные ребра – переносят их на другую плоскость.
   Наименьшее число ребер, удаление которых приводит к
   планарному графу, называется числом планарности или
   искаженностью графа G и обозначается sk(G)
   14
   

   Примеры из практики. В электротехнике части цепей наносятся на
   одну сторону непроводящей пластины (печатная плата). Поскольку
   проводники не изолированы, они не могут пересекаться, и
   соответствующие графы должны быть планарными.
   Требуется знать, сколько печатных плат понадобится для
   формирования всей сети.
   С этой целью вводится понятие толщины графа.
   Толщина графа t(G) – наименьшее число планарных графов,
   наложение которых дает G.
   18
   

   Оценку снизу для толщины графа можно получить по теореме
   Эйлера.
   Это довольно грубая оценка.
   Однако часто оказывается истинным значением толщины графа.
   Обозначения:
   [x] – наибольшее целое число, не превосходящее x,
   – наименьшее целое число, не превосходящее x
   20
   

   Теорема о нижней границе толщины графа
   Толщина t(G) графа G удовлетворяет следующим неравенствам:
   m
   t (G )
   3n 6
   m 3n 7
   t (G )
   3
   n
   6
   n – количество вершин, m – количество ребер графа G
   21
   

   2. Укладка графа на плоскости
   Критерии планарности не всегда просты в практическом
   применении. Также они не дают информации о том, как выполнить
   укладку планарного графа на плоскости.
   Рассмотрим некоторые алгоритмы проверки планарности графа и
   построения его плоской укладки.
   22
   

   Алгоритм представляет собой процесс последовательного
   присоединения к некоторому уложенному подграфу G’ графа G
   новой цепи L, оба конца которой принадлежат G.
   Затем в качестве подграфа G’ выбирается любой простой цикл
   графа G, и процесс присоединения новых цепей продолжается до
   тех пор, пока не будет построен плоский граф, изоморфный G.
   Либо присоединение новой простой цепи на некотором этапе
   окажется невозможным. Что будет свидетельствовать о
   непланарности исходного графа G.
   23
   

   Пусть имеется некоторая плоская укладка подграфа G’ = (V’, E’)
   графа G = (V, E).
   Сегментом Gi относительно G’ называется подграф графа G
   следующих двух видов:
   1) ребро e = (u, v) такое, что e E’ , u, v ∈ V’;
   2) Связная компонента графа G \ G’ , дополненная всеми ребрами
   графа G, соединяющими эту компоненту с подграфом G’, и
   концами этих ребер.
   24
   

   Вершина u сегмента Gi называется контактной, если u ∈ V’
   Граф G’ – плоский, значит, он разбивает плоскость на
   грани. Допустимой гранью для сегмента Gi относительно
   G’ называется грань Г графа G’, содержащая все
   контактные вершины сегмента Gi
   25
   

   Обозначим через Γ(Gi) множество допустимых граней для Gi .
   Для непланарных графов может быть Γ(Gi) = ∅.
   Рассмотрим простую цепь L сегмента Gi, соединяющую две
   контактные вершины этого сегменты и не содержащую других
   контактных вершин.
   Такие цепи называются α-цепями.
   Всякая α-цепь может быть уложена в любую грань, допустимую для
   данного сегмента.
   26
   

   Два сегмента Gi и Gj называются конфликтующими, если:
   1) θ = Γ(Gi) ∩ Γ(Gj) ∅;
   2) существуют две α-цепи Li ∈ Gi и Lj ∈ Gj, которые нельзя
   уложить без пересечений одновременно ни в какую
   грань Г ∈ θ.
   27
   

   Пусть G’ – плоская укладка некоторого подграфа графа G.
   Для каждого сегмента Gi относительно G’ находим множество допустимых
   граней.
   Тогда возможны следующие случаи:
   А) существует сегмент Gi, для которого Γ(Gi) = ∅, тогда исходный граф G
   непланарен;
   Б) для некоторого сегмента Gi существует единственная допустимая грань Γ,
   тогда располагаем любую α-цепь сегмента Gi в грани Γ, при этом грань Γ
   разобьется на две грани;
   В) Γ(Gi) ≥ 2 для всех Gi, тогда располагаем любую α-цепь сегмента Gi в любой
   допустимой грани.
   Если на очередном шаге множество сегментов пусто, то построена укладка
   графа на плоскости.
   28
   

   Алгоритм укладки планарного графа на
   плоскости
   Шаг 1. Выбираем любой простой цикл С графа G. Укладываем этот
   цикл на плоскости и полагаем G’ = C.
   Шаг 2. Находим все грани графа G’ и все сегменты Gi относительно
   G’. Если множество сегментов пусто, то укладка графа G на
   плоскости построена, конец алгоритма.
   Шаг 3. Для каждого сегмента Gi определяем множество
   допустимых граней Γ(Gi). Если найдется сегмент Gi, для которого
   Γ(Gi) = ∅, то исходный граф непланарен, конец алгоритма. Иначе
   переход на шаг 4.
   29
   

   Шаг 4. Если существует сегмент Gi, для которого имеется
   единственная допустимая грань С, то переход на шаг 6. Иначе на
   шаг 5.
   Шаг 5. Для некоторого сегмента Gi , для которого Г(Gi)>1, выбираем
   произвольную допустимую грань Г.
   Шаг 6. Произвольная α-цепь L сегмента Gi помещаем в грань Г.
   Полагаем G’ = G’ ∪ L и переход на шаг 1.
   Шаг 7. Построена укладка G’ графа G. Конец алгоритма.
   30
   

   Замечание
   Любой планарный граф можно уложить на сфере, и обратно.
   планарный граф можно уложить на плоскости несколькими
   способами.
   31
   

   Пример. Выполнить укладку графа на
   плоскости
   Шаг 1. Выберем простой
   цикл С=,
   который разбивает
   плоскость на две грани Г1 и
   Г2. Пусть G’=C.
   32
   

   Шаг 2. На рисунке показан граф
   G’=C и сегменты G1 и G2 исходного
   графа G относительно G’.
   Контактные вершины обведены
   кружками.
   Г(Gi)=, i=1, 2.
   Шаг 3. Г(Gi) , i=1, 2.
   Шаг 4. Нет сегмента, для которого
   бы существовала единственная
   допустимая грань.
   Шаг 5. Любую -цепь можно
   уложить в Г1 или Г2. Выберем для
   укладки грань Г1.
   33
   

   Шаг 6. Пусть L=.
   Поместим эту -цепь в Г1.
   Возникает новый граф G’ и его
   сегменты G1, G2, G3. появляется
   новая грань Г3.
   Переходим к шагу 1
   34
   

   Шаг 1. Имеем новые сегменты
   G1, G2, G3.
   Шаг 2. Г(G1) = , Г(G2)=,
   Г(G3)=
   Шаг 3. Г(Gi) , i=1, 2, 3.
   Шаг 4. Г(G1) = Г(G2)=. Переход
   на шаг 6.
   35
   

   Шаг 6. -цепь L1=
   поместим в грань Г1, -цепь
   L2= также поместим в эту
   грань.
   В результате возникает новый
   граф G’. Он имеет пять граней и
   один сегмент.
   36
   

   Шаг 1. G1 – ребро (x3, x5).
   Шаг 2. Г(G1)=
   Шаг 3. Г(G1)
   Шаг 4. Г(G1)=, переход на шаг
   6
   Шаг 6. -цепь L1=
   поместим в грань Г3. Новый граф
   G’ является плоской укладкой
   исходного планарного графа.
   37
   

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

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

   Содержание

   Два примера непланарных графов

   Полный граф с пятью вершинами

   
   

   Лемма. Полный граф с пятью вершинами (К₅) нельзя уложить на плоскость.
   

   
   

   Задача о трёх колодцах. Есть три дома и три колодца. Можно ли так проложить дорожки между домами и колодцами, чтобы от каждого дома к каждому колодцу вела дорожка, и никакие две дорожки не пересекались бы. Мосты строить нельзя.

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

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

   Очевидно утверждение: если граф G содержит подграф, гомеоморфный K₅ или K_3,3, его невозможно разложить на плоскости. Оказывается, верно и обратное.

   Граф планарен тогда и только тогда, когда не содержит подграфов, стягивающихся в K₅ или K_3,3.

   Признаки непланарных графов

   • достаточное условие — если граф содержит двудольный подграфK_3,3 или полный подграфK₅, то он является не планарным;
   • необходимое условие — если граф не планарный, то он должен содержать больше 4 вершин, степень которых больше 3, или больше 5 вершин степени больше 2.

   Формула Эйлера

   Для связного плоского графа справедливо следующее соотношение между количеством вершин , ребер и граней (включая внешнюю грань):

   
   

   Оно было найдено Эйлером в 1736 г. [1] при изучении свойств выпуклых многогранников. Это соотношение справедливо и для других поверхностей с точностью до коэффициента, называемого эйлеровой характеристикой. Это инвариант поверхности, для плоскости или сферы он равен двум. Формула имеет множество полезных следствий. Если каждая грань ограничена не менее чем тремя ребрами (при условии, что в графе больше двух ребер), а каждое ребро разделяет две грани, то

   
   

   
   

   то есть, при большем числе ребер такой граф заведомо непланарен. Обратное утверждение не верно, например, граф Петерсена. Отсюда следует, что в планарном графе всегда можно найти вершину степени не более 5.

   Планарные графы в задачах

   Раскраска карты. Необходимо раскрасить плоскую карту заданным числом красок так, что любые две страны, имеющие общий участок границы, имели различные цвета. Оказывается, что при отсутствии анклавов, всегда достаточно четырех красок, но это утверждение чрезвычайно сложно доказать, см. Проблема четырёх красок.

   Спрямление графа. Любой плоский граф можно перерисовать так, чтобы он остался плоским, а рёбра стали прямолинейными.

   См. также

   Примечания

   1. ↑ Ф. Харари Теория графов УРСС стр. 126

   Ссылки

   • Теория графов
   • Дискретная математика

   Wikimedia Foundation . 2010 .

   Полезное

   Смотреть что такое "Планарный граф" в других словарях:

   ГРАФ ПЛОСКИЙ — планарный граф, граф, допускающий правильную укладку на плоскости (см. Графа укладка). Иными словами, граф G наз. плоским, если он может быть изображен на плоскости так, что вершинам соответствуют различные точки плоскости, а линии,… … Математическая энциклопедия

   Граф Петерсена — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей … Википедия

   Плоский граф — Планарный граф граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим, его … Википедия

   плоский граф — планарный граф — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы планарный граф EN flat graph … Справочник технического переводчика

   Двудольный граф — Биграф Двудольный граф или биграф это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что ка … Википедия

   Планарность — Планарный граф граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим, его … Википедия

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

   Гамма-алгоритм — Гамма алгоритм алгоритм плоской укладки графа и проверки его на планарность. Содержание 1 Определения 2 Алгоритм 3 Реализация … Википедия

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

   Изображение графа на плоскости с соблюдением этого условия называется плоским графом.

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

   Как получить планарное изображение графа?

   Если граф не планарен, то приходится удалять (переносить на другой слой, на другую плоскость) отдельные ребра.

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

   
   

   (K_n) = (n–3)(n–4)/2.

   Из формулы следует, что при n = 4 (K₄) = 0. Для K₅ (K₅) = 1, следовательно, чтобы граф K₅ стал плоским, из него надо удалить одно ребро.

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

   Минимальное число плоскостей, при котором граф разбивается на плоские части, называется толщиной графа и обозначается t(G).

   Толщина произвольного графа удовлетворяет неравенству

   
   

   t(G).

   Здесь [x] – целая часть x.

   Толщина полных графов удовлетворяет неравенству

   
   

   t(K_n).

   Например, для K₅ t(K₅) = 2.

   23.2.2 Условия планарности

   Ответ на первый вопрос: – Граф планарен? – можно получить, если воспользоваться условиями планарности.

   
   

   У связного плоского графа с n3 число ребер m удовлетворяет условию

   
   

   У связного плоского двудольного графа

   
   

   Пример. Полный граф K₄ (рис. 23.1, а) – планарен?

   В этом графе n = 4, m = 6.

   
   

   Р исунок 23.1

   Подставим эти значения в условие планарности

   
   

   Условие выполняется. Следовательно, граф планарен. Действительно, граф K₄ можно представить так, как показано на рис. 23.1, б.

   Из рисунка ясно, что граф K₄ планарен.

   Пример. Полный граф K₅ (рис. 23.1, в) – планарен?

   В этом графе n = 5, m = 10.

   Подставим эти значения в условие планарности

   
   

   Условие не выполняется. Следовательно, граф не планарен.

   Пример. Двудольный полный граф К_3,3 (рис. 23.1, г) – планарен?

   В этом графе n = 6, m = 9.

   Подставим эти значения в условие планарности

   
   

   Условие не выполняется. Следовательно, граф не планарен.

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

   Расположим все вершины на одной прямой рис. 23.2.

   
   

   Р исунок 23.2

   Построим m плоскостей на этой прямой, т. е. для каждого ребра свою плоскость.

   Проведем ребра на своих плоскостях. Ребра не пересекаются (кроме как на своих вершинах).

   Непланарность графов K₅ и К_3,3 используется для оценки планарности “больших графов”: граф не планарен, если он содержит подграфы вида K₅ или К_3,3, или сводимые к ним.

   Грани плоского графа

   У плоского графа кроме вершин и ребер можно выделить еще один геометрический образ – грань.

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

   Внешняя неограниченная грань называется бесконечной гранью.

   Например, граф на рис. 23.1, б обладает четырьмя гранями: f₁, f₂, f₃, f₄, где f₄ бесконечная грань.

   У графа без циклов ровно одна грань – бесконечная. Не следует думать, что она какая–то исключительная. При укладке графа на сферу эта грань ничем не будет отличаться от других.

   Число граней f в связном плоском графе определяется из соотношения

   f = m – n + 2,

   где n – число вершин, m – число ребер.

   23.2.3 Алгоритм построения плоского изображения графа

   Ответ на второй вопрос: – Как получить плоское изображение графа? – дает алгоритм, рассмотренный ниже.

   Пусть задана часть G₁ = (V₁, E₁) графа G = (V, E).

   Будем называть куском графа G относительно G₁:

   
   

   ребро вместе с его концами, которые принадлежат V₁,

   Алгоритм использует последовательный процесс присоединения к некоторому плоскому подграфу цепи , оба конца которой (и только они) – вершины . Эта цепь разобьет одну из граней на две.

   
   

   В качестве начального плоского графа выбирают некоторый цикл графа G.

   Чтобы перейти от подграфа к , предварительно рассматривают все куски P_j графа G относительно .

   
   

   Грань f_k графа и кусок Р_j совместимы, если все его контактные точки принадлежат множеству вершин этой грани.

   Для каждого куска определяем грани, которые с ним совместимы. Возможны три случая:

   
   

   Некоторый кусок не совместим ни с какой гранью графа . Тогда граф не плоский.

   Какой–либо кусок совместим с единственной гранью f_k графа . Тогда выберем в этом куске цепь такую, что оба ее конца (и только они) принадлежат . Дополняя ребрами и вершинами этой цепи, получаем , проводя внутри грани f_k.

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

   Пример. Проиллюстрируем этот алгоритм на примере графа G(V,E) рис. 23.3.

   
   

   Р исунок 23.3

   
   

   Шаг 1. Берем произвольный цикл, например u₀ = (1, 2, 6, 5, 1), представляющий плоский граф (рис. 23.4, а).

   
   

   Грани:

   A₀ — внешняя грань (1, 2, 6, 5, 1),

   В₀ — внутренняя грань (1,2,6,5,1).

   
   

   Куски графа G относительно :

   Читайте также:

     
   • Как сделать презентацию про друга
     
   • Как сделать обложку на паспорт из бисера
     
   • Как сделать зефир без яиц
     
   • Как сделать пряничного человечка из полимерной глины
     
   • Как сделать кольцо из ложки