Деревья

Слайд 2

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

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

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

Слайд 3

Для любого графа G(X,U)

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

Для любого графа G(X,U) Остовным деревом называется подграф-дерево графа G, содержащий все
вершины.

являющегося деревом, справедливо равенство: n = m + 1.

Один и тот же граф может иметь несколько остовов.