|
|
Дискретная Математика. Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200
3.20. Планарность графов
Ранее уже отмечалось, что возможно несколько изображений одного графа, поскольку все изоморфные графы несут одну и ту же информацию. На практике при изготовлении микросхем необходимо выяснить можно ли схему радиоэлектронного устройства, которая представляет собой граф, изобразить на плоскости без пересечений проводников.
Аналогичная задача возникает при проектировании железнодорожных и других путей, где нежелательны переезды.
Таким образом, возникает задача построения и исследования плоского графа.
Плоским графом называется граф, вершины которого являются точками плоскости, а ребра – непрерывными плоскими линиями без самопересечений, причем никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины. Любой граф, изоморфный плоскому графу, называется планарным.
Все планарные графы укладываются на плоскости (имеют плоскую укладку). На рисунке 3.47 изображен планарный граф G и его плоская укладка G
Очевидно, что 1) всякий подграф планарного графа планарен и 2) граф планарен тогда и только тогда, когда каждая связная компонента этого графа – планарный граф.
Гранью планарного графа называется множество точек плоскости, каждая пара которых может быть соединена плоской кривой, не пересекающей ребер этого графа.
Границей грани называется множество вершин и ребер, принадлежащих этой грани.
Например, граф
1
x
2
x
3
x
1
x
2
x
3
x
8
:
G
:
G
2
4
7
1
3
5
6
7
x
6
x
5
x
4
x
7
x
6
x
5
x
4
x
Рис. 3.47.
G
на рисунке 3.47 имеет восемь граней:
8 2
1
,...,
,
. Неограниченная грань
1
называется внешней, а остальные грани
8 3
2
,...,
,
- внутренними.
Пусть
f
m
n
,
,
- соответственно число вершин, ребер и граней планарного графа.
Теорема 3.21 (теорема Эйлера). Для всякого связного планарного графа верно
равенство
2
f
m
n
. (3.20.1)
Доказательство. Пусть G - связный планарный n - вершинный граф. Рассмотрим некоторый остов
/
G
этого графа. Остов имеет всего одну внешнюю грань, n вершин и
1
n
ребер, поэтому формула (3.20.1) для остова
/
G
выполняется. Будем поочередно добавлять к остову
/
G
недостающие ребра графа G . При каждом добавлении число вершин не изменится, число ребер увеличится на единицу, так же как и число граней, поскольку при добавлении к остову ребра, связывающего две несмежные вершины, получается цикл, разделяющий текущую грань на две грани.
Таким образом, формула (3.20.1) будет верна для всякого графа, получающегося в результате таких операций, а поскольку графом G заканчивается вся эта процедура, то формула (3.20.1) будет верна и для него.
Имеется несколько критериев планарности и найдены эффективные алгоритмы, осуществляющие плоскую укладку планарного графа. Для формулировки критерия планарности ведем понятие гомеоморфизма графов. Рассмотрим операцию подразбиения
90 ребра в графе
U
S
G
,
. После подразбиения ребра
U
y
x
,
получается граф
/
/
/
,U
S
G
, где
y
xy
xy
x
y
x
U
U
xy
S
S
,
,
,
,
\
,
/
/
, т. е. ребро
y
x,
заменяется на
y
x,
- цепь длины два. Два графа называются гомеоморфными, если
:
G
:
1
G
:
2
G
они оба могут быть получены из одного и того же графа подразбиением его ребер. На рисунке 3.48 изображены
x
y
исходный граф G и два гомеоморфных графа
1
G и
2
G .
Теорема 3.22 (теорема Понтрягина
-Куратовс-
кого
) Граф планарен тогда и только тогда, когда он
не содержит подграфов, гомеоморфных
5
K или
3
,
3
K
.
Рис. 3.48.
Эквивалентная форма критерия планарности описана в следующей теореме.
Теорема 3.23. Граф планарен тогда и только тогда, когда в нем нет подграфов,
стягиваемых (т. е. получаемых последовательностью отождествлений вершин,
связанных ребрами) к графам
5
K или
3
,
3
K
.
Для непланарных графов вводятся характеристики, представляющие ту или иную меру непланарности. Если граф непланарен, то для его геометрической реализации удаляют отдельные ребра (переносят их на другую плоскость). Наименьшее число ребер, удаление которых приводит к планарному графу, называется числом планарности или искаженностью
G
sk
графа G . Для числа планарности полного графа справедлива следующая формула
3
,
6 3
2
n
n
C
G
sk
n
. (3.20.2)
Важнейшей характеристикой непланарного графа является его толщина
G
t
. Это наименьшее число планарных подграфов графа G , объединение которых дает сам граф.
Толщина графа равна минимальному числу плоскостей l , при котором граф G разбивается на плоские части
l
G
G
G
,...,
,
2 1
. Очевидно, что толщина планарного графа равна единице. Для толщины связанного
m
n,
- графа справедливы такие оценки
6 3
7 3
,
6 3
n
n
m
G
t
n
m
G
t
, (3.20.3) где
... - целая часть числа, а
1
3.21. Алгоритм укладки графа на плоскости
Критерии планарности в практическом применении не всегда просты и не дают информации о том, как строить укладку графа на плоскости, если он планарен. Все это вызвало появление алгоритмов, которые проверяют граф на планарность и строят его плоскую укладку. Рассмотрим один из таких алгоритмов.
Этот алгоритм представляет собой процесс последовательного присоединения к некоторому уложенному подграфу G
графа G новой цепи L , оба конца которой принадлежат G . После этого в качестве подграфа G
выбирается любой простой цикл графа
G и процесс присоединения новых цепей продолжается до тех пор, пока не будет построен плоский граф, изоморфный G или присоединение новой простой цепи на некотором этапе окажется невозможным, что свидетельствует о непланарности исходного графа G .
Лев Семенович Понтрягин (1908 – 1988) – советский математик.
Казимеж Куратовский (1896 – 1980) – польский математик.
91
Введем несколько определений. Пусть имеется некоторая плоская укладка подграфа
G
графа G . Сегментом
i
G относительно
U
S
G
,
называется подграф графа
U
S
G
,
следующих двух видов:
1) ребро
U
y
x
u
,
такое, что
S
y
x
U
u
,
,
;
2) связная компонента графа
G
G
\
, дополненная всеми ребрами графа G , инцидентными вершинам взятой компоненты, и концами этих ребер.
Вершина u сегмента
i
G называется контактной, если
S
u
. Граф G
- плоский, следовательно, он разбивает плоскость на грани. Допустимой гранью для сегмента
i
G относительно G
называется грань
графа G
, содержащая все контактные вершины сегмента
i
G . Обозначим через
i
G
- множество допустимых граней для
i
G . Для непланарных графов может быть
i
G
. Рассмотрим простую цепь L , сегмента
i
G , соединяющую две различные контактные вершины и не содержащую других контактных вершин. Такие цепи называются α -цепями. Всякая α -цепь может быть уложена в любую грань, допустимую для данного сегмента.
Два сегмента
1
G и
2
G относительно G
называются конфликтующими, если
1)
2 1
θ
G
G
,
2) существуют две α -цепи
1 1
G
L
и
2 2
G
L
, которые без пересечений нельзя уложить одновременно ни в какую грань
θ
Пусть G
- плоская укладка некоторого подграфа графа G . Для каждого сегмента
i
G относительно G
находим множество допустимых граней. Тогда могут осуществляться только следующие три случая.
1) Существует сегмент
i
G , для которого
i
G
. В этом случае исходный граф G непланарен.
2) Для некоторого сегмента
i
G существует единственная допустимая грань
. Тогда можно расположить любую
α -цепь сегмента
i
G в грани
. При этом грань
разобьется на две грани.
3)
2
i
G
для
i
. В этом случае можно расположить
α -цепь в любой допустимой грани.
Сам алгоритм укладки планарного графа G на плоскость состоит из следующих шагов.
Шаг 1. Выбирается любой простой цикл C графа G . Этот цикл укладывается на плоскости и полагается
C
G
Шаг 2. Находятся все грани графа G
и все сегменты
i
G относительно G
. Если множество сегментов пусто, происходит переход на шаг 7.
Шаг 3. Для каждого сегмента
i
G определяется множество допустимых граней
i
G
Если найдется сегмент
i
G
, для которого
i
G
, то исходный граф G непланарен; конец алгоритма, иначе переход на шаг 4.
Шаг 4. Если существует сегмент
i
G
, для которого имеется единственная допустимая грань
, то происходит переход на шаг 6, иначе на шаг 5.
Шаг 5. Для некоторого сегмента
i
G
, для которого
1
i
G
, выбирается произвольная допустимая грань.
Шаг 6. Произвольная
α -цепь L сегмента
i
G помещается в грань
, G
заменяется на
L
G
и происходит переход к шагу 1.
Шаг 7. Построена укладка G
графа G на плоскости. Конец алгоритма.
92
Пример 1. Пусть граф G изображен на рисунке 3.49. Шаг 1. Выберем простой цикл
1
x
2
x
3
x
4
x
5 4
3 2
1
,
,
,
,
x
x
x
x
x
C
, который разбивает плос- кость на две грани
1
и
2
. Положим
C
G
:
G Шаг 2. На рисунке 3.50 изображен граф
C
G
и сегменты
2 1
,G
G
исходного графа G относитель-
8
x
7
x
6
x
5
x но G
. Контактные вершины обведены кружками.
Рис. 3.49.
2
,
1
,
,
2 1
i
G
i
Шаг 3.
2
,
1
,
i
G
i
1
x
2
x
3
x
8
x
7
x
6
x
3
x
:
G
:
1
G
:
2
G
1
2
5
x
4
x
1
x
4
x
5
x
5
x
Рис. 3.50.
Шаг 4. Нет сегмента, для которого бы существовала единственная допустимая грань.
Шаг 5. Любую
α -цепь можно уложить в
1
или в
2
. Выберем для укладки грань
1
Шаг 6. Пусть
5 6
7 8
1
,
,
,
,
x
x
x
x
x
L
. Поместим эту
α -цепь в
1
. Возникает новый граф
G
и его сегменты (см. рис. 3.51)
3 2
1
,
,
G
G
G
. Появляется и новая грань
3
. Переходим к первому шагу.
Шаг 1. Новых сегментов три:
3 2
1
,
,
G
G
G
Шаг 2.
1 1
G
,
1 2
G
,
3 1
3
,
G
Шаг 3.
3
,
2
,
1
,
i
G
i
8
x
1
x
2
x
3
x
8
x
6
x
3
x
:
G
3
:
1
G
:
2
G
:
3
G
1
2
7
x
6
x
5
x
4
x
4
x
4
x
5
x
Рис. 3.51.
Шаг 4.
1 2
1
G
G
, переход на шаг 6.
Шаг 6.
α -цепь
8 4
1
, x
x
L
поместим в грань
1
,
α -цепь
6 4
2
, x
x
L
также помещаем в эту же грань. В результате возникает новый граф G
, изображенный на рисунке 3.52. Этот граф имеет пять граней и один
8
x
1
x
2
x
3
x
3
x сегмент.
4
Шаг 1.
1
G - ребро
5 3
, x
x
:
G
3
:
1
G Шаг 2.
3 1
G
1
2
Шаг 3.
1
G
7
x
6
x
5
x
4
x
5
x Шаг 4.
3 1
G
, переход на
5
шестой шаг.
Рис. 3.52.
Шаг 6.
α -цепь
5 3
1
, x
x
L
по- местим в грань
3
. Новый граф G
на рисунке 3.53 является плоской укладкой исходного планарного графа.
3
x
93 8
x
1
x
2
x
3
x
:
5
K
6
2
x
4
x
:
G
3
1
2
4
7
x
6
x
5
x
4
x
1
x
5
x
5
Рис. 3.54.
Рис. 3.53.
Пример 2. Попытаемся получить плоскую укладку графа
5
K , изображенного на рисунке 3.54. Поскольку известно, что граф непланарен, алгоритм должен закончить работу на третьем шаге.
Шаг 1. Выберем простой цикл
5 4
3 2
1
,
,
,
,
x
x
x
x
x
C
,
C
G
Шаг 2. Граней у графа G
две:
1
и
2
, сегментов пять, все они показаны на рис. 3.55.
3
x
1
x
1
x
2
x
2
x
3
x Шаг 3.
5
,
1
,
2
i
G
i
Шаг 4.
5
,
1
,
1
i
G
i
:
G
:
1
G
:
2
G
:
3
G
:
4
G
:
5
G
Шаг 5. Выберем для
1
G и
2
x
4
x
5
G грань
2
в качестве до-
1
2
пустимой грани.
1
x
5
x
3
x
4
x
4
x
5
x
5
x Шаг 6.
α -цепи
3 1
1
, x
x
L
Рис. 3.55.
и
5 3
2
, x
x
L
присоединим к графу G
. Получим новый граф G и три сегмента
3 2
1
,
,
G
G
G
. (см. рис. 3.56).
Шаг 1-2. Новых граней у графа G
четыре:
4 3
2 1
,
,
,
3
x
1
x
2
x
2
x Шаг 3.
1 1
G
,
1 2
G
,
1 3
G
:
G
:
1
G
:
2
G
:
3
G
Шаг 4. Для
1
G и
2
G выберем грань
1
2
x
2
4
4
x Шаг 6.
α -цепи
4 1
1
, x
x
L
и
4 2
2
, x
x
L
1
3
поместим в грань
1
и присоединим к G
1
x
5
x
4
x
4
x
5
x Шаг 1. G
и сегмент
1
G показаны на рис.
Рис. 3.56.
3.57.
Шаг 2. Граней у графа G
теперь шесть:
6 5
4 3
2 1
,
,
,
,
,
3
x
6
2
x
3
x
:
G
:
1
G
2
x
4
x
2
x
2
4
4
x
1
3
1
x
5
x
5
x
1
x
5
x
5
Рис. 3.57.
Рис. 3.58.
Шаг 3.
1
G
. Исходный граф G непланарен, конец алгоритма.
94 В заключение найдем число планарности и толщину полного графа 5 K . По формуле (3.20.2) 1 6 15 10 6 5 3 2 5 5 CKsk. Это соответствует действительности, у графа Gостался один не присоединенный сегмент 1 G (см. рис. 3.57). Для толщины полного графа модификация формул (3.20.3) дает точную оценку 2 6 7 5 6 7 5 nKt. Таким образом, этот граф можно представить в виде объединения планарных графов на двух плоскостях (см. рис. 3.58). |
|
|
Скачать 6.37 Mb.