ВУЗ:
Составители:
Рубрика:
Глава 2. Плоские и планарные графы 51
С учетом (2), можно записать
4f = 4f
4
+ 4f
5
+ 4f
6
+ ... (4)
Тогда 4f ≤ 2m или 2f ≤ m. Но для m = 9, f = 5 получим, что 10 ≤ 9.
Таким образом, граф K
3,3
не плоский. Аналогичным образом можно
показать, что полный граф с пятью вершинами K
5
, имеющий про-
стые циклы длины 3, не плоский. Следовательно, имеется 2 типа не
плоских графов: тип I – граф K
3,3
, тип II – граф K
5
. ■
По критерию Понтрягина – Куратовского необходимое и доста-
точное условие, при котором граф G является планарным, состоит
в том, что граф не должен содержать подграфов типа I и типа II
[15].
Для проверки планарности графа с n вершинами по этому крите-
рию необходимо рассмотреть С
n
5
графов с пятью вершинами и С
n
6
графов с шестью вершинами.
Рассмотрим плоский граф G на рис. 2.6. Если добавить к нему два
ребра (штриховые линии), то он останется
плоским.
Плоский граф называется максимально
плоским если невозможно добавить к не-
му ни одного ребра так, чтобы новый
граф был бы плоским. Каждая грань в
максимально плоском графе имеет 3 вер-
шины, поэтому максимально плоский
граф называется триангулированным и
имеет ровно 3 внешних ребра.
Утверждение 2.2. Для любого планарного графа G существует
плоская укладка, в которой все ребра – прямолинейные отрезки.
Доказательство. Будем рассматривать общий случай – макси-
мально плоских графов. Для n < 4 утверждение очевидно. Если n = 4,
то четвертая вершина А может находиться либо внутри грани (см.
рис. 2.7, a), либо вне ее, но тогда существует граф с прямолинейны-
ми отрезками, изображенный на рис. 2.7, в.
Пусть теорема верна для максимально плоского графа с n верши-
нами A
i
, соединенными прямолинейными отрезками. Добавим еще
одну вершину А
n+1
. Так как граф триангулирован, то эта вершина на-
Рис. 2.6
Страницы
- « первая
- ‹ предыдущая
- …
- 49
- 50
- 51
- 52
- 53
- …
- следующая ›
- последняя »
