Математическое моделирование на графах. Часть 1. Берцун В.Н. - 50 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

50 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1
лению в полученном дереве число вершин сохраняется, тогда n = n
1
.
Но дерево с n вершинами имеет n – 1 ребро. Тогда m
1
= n – 1. Поэто-
му m – f = m
1
– 1 = n – 2 или n – m + f = 2. ■
Ответ на вопрос о том, является ли данный граф плоским, очень
часто не является очевидным и требует дополнительного анализа
графа. Рассмотрим, например, задачу о трех домах и трех колодцах.
DEF
A
B
C
Рис. 2.5
Пусть имеется 3 дома и 3 колодца. От каждого дома к каждому
колодцу идет тропинка. Можно ли проложить тропинки так, чтобы
они не пересекались? Решение задачи сводится к определению того,
является ли полный двудольный граф K
3,3
на рис. 2.5 плоским. До-
пустим, что он является плоским [34 – 37]. Для этого графа n = 6,
m = 9 и из формулы (1) получим
f = 2 + 9 – 6 = 5.
Отметим, что у двудольного графа K
3,3
нет простых циклов длины
3, т.е. граница любой грани в плоском представлении содержит не
менее четырех ребер. Тогда число граней
f = f
4
+ f
5
+ f
6
+ ..., (2)
где f
i
– число граней, ограниченных i ребрами. Но каждое ребро яв-
ляется границей двух граней (с учетом внешней грани), поэтому все-
го граней не больше 2m. С другой стороны, удвоенное число ребер
можно вычислить через количество ребер в гранях
2m = 4f
4
+ 5f
5
+ 6f
6
+ ... (3)

Страницы