ВУЗ:
Составители:
Рубрика:
62
Теорема (Понтрягина). Граф планарен тогда и только тогда, ко-
гда он не содержит подграфа или частичного графа, гомеоморфного
графу F
5
или графу K
3, 3
(рис. 26, а, б). ■
Основываясь на критерии Понтрягина, можно получить ещё один
критерий планарности. Этот критерий использует понятие элементарно-
го стягивания, заключающегося в следующем. При стягивании какого-
либо ребра графа оно исчезает, а вершины, коинцидентные этому ребру
отождествляются. Например, в результате стягивания ребра {a, b} графа,
изображённого на рис. 27, а, получаем граф, представленный на рис. 27, б.
При этом полученная вершина a(b) коинцидентна тем же рёбрам, что и
вершины a, b в исходном графе (кроме ребра, которое выброшено).
Теорема. Граф планарен тогда и только тогда, когда он не содер-
жит подграфа или частичного графа, стягиваемых к графу F
5
или к
графу K
3, 3
. ■
Толщиной t(G) графа G называется наименьшее число планарных
графов, объединение которых даёт граф G. Заметим, что толщина пла-
нарного графа равна 1. Нижняя оценка толщины t(G) графа G = < V, U >
определяется неравенством
t(G) ≥ 1 +
−
−
∑
=
)2(6
2
1
n
s
n
i
i
,
где
]
[
– целая часть; n – мощность множества V; s
i
– степень i-й вершины.
а)
б)
Рис. 26
a
c
d
e
g
f
b
a(b)
c
d
e
f
g
Рис. 27
а)
б)
Страницы
- « первая
- ‹ предыдущая
- …
- 60
- 61
- 62
- 63
- 64
- …
- следующая ›
- последняя »
