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

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

32 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1
На рис. 1.34 изображены все помеченные графы с тремя верши-
нами.
12
3
12
3
12
3
12
3
12
3
12
3
12
3
12
3
Рис. 1.34
Таким образом, четыре различных графа с тремя вершинами по-
рождают 8 помеченных графов, из которых 3 являются помеченны-
ми деревьями с тремя вершинами. Отметим, что число помеченных
корневых деревьев t
pk
= n · t
p
, так как существует n вариантов выбора
корня. Из асимптотической формулы Пойа для числа непомеченных
графов [15] следует, что число таких графов «примерно» в n! раз
меньше числа помеченных графов на n вершинах.
Остовным деревом (каркасом) называется суграф в виде дерева.
На рис. 1.35 представлены каркасы графа G.
Рис. 1.35
При решении задач проектирования сетей часто требуется мини-
мизировать, например, их стоимость или длину. В этом случае воз-
никает задача построения минимального остовного дерева для гра-
фа, ребрам которого приписаны некоторые веса (стоимость, рас-

Страницы