Напомним, что граф – это комплекс конечного числа точек (вершин графа) и конечного набора линий (рёбер графа), причём некоторые из точек попарно соединяются данными линиями.
Дерево – это связный граф, не имеющий циклов.
Роль дерева
– это представление:
Число рёбер в дереве на единицу меньше числа вершин.
Обычно рассматривают ориентированные деревья. В них дуги имеют направления.
Корень дерева – это самая первая вершина, из которой выходят дуги.
Висячие вершины (листья) – это вершины, из которых не выходит ни одна дуга. У каждого дерева, состоящего более чем из одной вершины, есть хотя бы одна концевая вершина.
Лес – это упорядоченное множество упорядоченных деревьев.
Если у дерева удалить ребро, граф перестанет быть связным.
