Пояснение к работе

Практическое занятие № 8

Тема: «Планарные графы»

Цель занятия:

усвоение таких понятий, как планарный граф, плоский граф, грани графа, эйлерова характеристика, гамма-алгоритм укладки графа.

Время выполнения практического задания – 2 часа.

Последовательность выполнения

1. Руководствуясь приведенным теоретическим материалом, ответить на следующие вопросы:

Какое соотношение называется эйлеровой характеристикой поверхности?

Какой граф является планарным?

Какие вершины называются контактными?

Что такое сегмент плоского графа?

В чем заключается гамма-алгоритм укладки графа?

2. Дать определение следующих понятий:

– плоский граф;

– грань в плоском графе:

– внешняя грань в плоском графе.

3. Записать первое и второе следствие из формулы Эйлера.

4. Выполнить задания для аудиторных занятий.

5. Выполнить задания для самостоятельной работы.

8.1. Планарные графы

Помимо использования в дискретной математике, графы находят применение и в непрерывной математике, особенно в топологии. При этом графы представляют геометрические объекты на некоторой поверхности (часто на плоскости или на поверхности сферы).

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

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

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

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

Рис. 23	Рис. 24

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

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

8.2. Эйлерова характеристика

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

Теорема (формула Эйлера). В связном планарном графе справедливо следующее соотношение: p – q + r = 2, где р – число вершин, q – число ребер, r – число граней с учетом внутренних и внешних граней.

Следствие. Если G – связный планарный граф (р > 3), то q £ 3 p - 6.

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

Каждая грань ограничена по крайней мере тремя ребрами, каждое ребро ограничивает не более трех граней, отсюда 3 r £ 2 q. Имеем:

2 = p – q + r £ p - q + 2 q /3 Þ 3 p - 3 q + 2 q ³ 6 Þ q £ 3 p – 6.

Следствие: К ₅ и К _3,3 непланарны.

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

1. Рассмотрим К ₅. Имеем: p = 5, q = 10. Если К ₅ планарен, то по предыдущему следствию q = p (p - 1)/2 = 10 £ 3 p – 6 = 3×5 – 6 = 9 – противоречие.

2. Рассмотрим К _3,3. Имеем: p = 6, q = 9. В этом графе нет треугольников, значит, если этот граф планарен, то в его плоской укладке каждая грань ограничена не менее чем четырьмя ребрами и, следовательно, 4 r £ 2 q или 2 r £ q. По формуле Эйлера, 6 – 9 + r = 2, откуда r = 5. Имеем: 2 r = 2×5 = 10 £ q = 9 – противоречие.

Замечание. Граф планарен тогда и только тогда, когда он не содержит в качестве подграфов ни К ₅, ни К _3,3.

Следствие. В любом планарном графе существует вершина, степень которой не больше 5.

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

От противного. Пусть " ν Î V d(v) ³ 6. Тогда 6 p £ = 2 q Þ 3 p £ q, но q £ 3 p - 6. Имеем: 3 p £ 3 p - 6, противоречие.

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

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

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

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

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

Для плоской укладки графа и попутной проверки, планарен ли он, удобно пользоваться гамма-алгоритмом. На вход подаются графы, обладающие следующими свойствами: 1) граф связный; 2) граф имеет хотя бы один цикл; 3) граф не имеет мостиков, т. е. ребер, после удаления которых граф распадается на две компоненты связности.

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

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

Сначала изложим алгоритм на конкретном примере. Пусть дан граф G (рис. 25). Инициализация алгоритма производится так: выбираем любой простой цикл; в нашем примере {1, 2, 3, 4, 5, 6, 7, 8} и получаем две грани: Γ 1 – внешнюю и Γ 2 – внутреннюю (рис. 26). Обозначим выбранный цикл как G′. На каждом шаге будем строить множество сегментов. Каждый сегмент S относительно уже построенного графа G′ представляет собой одно из двух: ребро, оба конца которого принадлежат G′, но само оно не принадлежит G′; связную компоненту графа G–G′, дополненную всеми ребрами графа G, один из концов которых принадлежит связной компоненте, а второй из графа G′.

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

Рис. 25	Рис. 26	Рис. 27

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

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

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

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

Рис. 28

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

Рис. 29	Рис. 30

Задания

Для аудиторных занятий

1. Построить попарно неизоморфные непланарные графы без петель и кратных ребер, содержащие 6 вершин и 11 ребер.

2. Построить однородный 9-вершинный граф без петель и кратных ребер, который не планарен вместе со своим дополнением.

3. Используя формулу Эйлера, доказать непланарность следующих графов:

а) К ₅ (рис. 31 а); б) К _3.3 (рис. 31 б); в) граф Петерсена (рис. 32 а); г) граф на рис. 32 б.

4. Существует ли планарный граф без петель и кратных ребер, у которого:

а) 7 вершин и 16 ребер; б) 8 вершин и 17 ребер.

5. Какое наибольшее число граней может быть у плоского 5-вершинного графа, не имеющего петель и кратных ребер? Изобразить такой граф.

а б

Рис. 31

а б

Рис. 32

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

а) G – граф Петерсена (рис. 32 а); б) G – граф, изображенный на рис. 33.

Рис. 33

7. Какое наименьшее число ребер нужно удалить из графа G, чтобы получить планарный граф, если:

а) G – граф Петерсена (рис. 32 а); б) G = К ₆.

8. Существует ли плоский 6-вершинный граф без петель и кратных ребер, у которого 9 граней?

9. Построить все попарно неизоморфные плоские 6-вершинные графы без петель и кратных ребер, имеющие 8 граней.

10. Доказать, что в каждом планарном графе без петель и кратных ребер есть вершина степени не больше, чем 5.

Для самостоятельной работы

1. Доказать, что в любом планарном графе без петель и кратных ребер, имеющем не менее 4 вершин, найдутся хотя бы 4 вершины, степени которых не больше, чем 5.

2. Какое наименьшее число вершин необходимо удалить, чтобы граф стал планарным (рис. 32 б).

3. Какой из графов G может быть планарным:

а) граф, состоящий из 7 вершин и 16 ребер;

б) граф, состоящий из 8 вершин и 17 ребер;

в) граф, состоящий из 5 вершин и 10 ребер.

4. Используя формулу Эйлера, определить, планарен ли следующий граф:

5.Дать определение плоского графа:

а) плоский граф – это граф, нарисованный на плоскости таким образом, что его ребра пересекаются;

б) плоский граф – это граф, нарисованный на плоскости таким образом, что его ребра не пересекаются;

в) плоский граф – это граф, уложенный на плоскости.

6. Сколько граней имеет заданный плоский граф?

7. Какие вершины плоского графа называются контактными:

а) вершины, которые одновременно принадлежат плоскому графу G′ и какому-то сегменту;

б) вершины, которые одновременно принадлежат графу G и одному из сегментов;

в) вершины, которые одновременно не принадлежат плоскому графу G′ и какому-то сегменту.

8. Дать определение планарного графа:

а) планарный граф – это граф, нарисованный на плоскости таким образом, что его ребра пересекаются;

б) планарный граф – это граф, уложенный на плоскости;

в) планарный граф – это граф, нарисованный на плоскости таким образом, что его ребра не пересекаются.

9. Какой граф представлен записью K _3,3:

а) однородный;

б) двудольный;

в) плоский.

10. С помощью гамма-алгоритма укладки графа на плоскости определить планарнрсть графа (рис. 32 б).

Литература

1. Новиков, Ф. А. Дискретная математика для программистов: учебник для вузов / Ф. А. Новиков. – СПб.: Питер, 2001. – 304 с.
2. Горбатов, В. А. Фундаментальные основы дискретной математики / В. А. Горбатов. – М.: Наука, 2000. – 544 с.

Дата добавления: 2017-02-01