Деревья

Граф называется связным, если любая пара его вершин соединена простой цепью.

На рис.4.18 граф G₁ является связным, а G₂ - несвязным.

G₁ G₂

Рис.4.18. Связность графов

Граф называется ациклическим, если в нем нет циклов.

Дерево - это связный ациклический граф.

На рис.4.19 граф G является деревом.

G

Рис.4.19. Дерево

Для любого графа G(X,U), ú Xú = n, ú Uú = m, являющегося деревом, справедливо равенство

n = m + 1

Остовным деревом называется подграф-дерево графа G, содержащий все его вершины.

Один и тот же граф может иметь несколько остовов. На рис.4.20 изображены два остова графа G₁ (рис.4.18).

Рис.4.20. Остовы графа

Пусть граф G является взвешенным. Минимальным остовным деревом называется остовное дерево с минимальным суммарным весом ребер.

На рис.4.21 приведены взвешенный граф и его минимальное остовное дерево, суммарный вес которого равен 14.

7

3 4 8 1 3 4 1

5 6 6

Рис.4.21. Минимальное остовное дерево