Деревья. Лес

Деревом называется связный граф, не имеющий циклов.

Для каждой пары вершин существует единственный соединяющий их путь. Граф, состоящий из одной вершины – дерево.

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

Всякое ребро в дереве и лесе является мостом.

Теорема: Дерево с n вершинами имеет (n-1) ребро.

Остовом или остовым деревом называется связный граф, содержащий все вершины исходного графа и являющийся деревом.

Хордой остова в графе называется произвольное ребро, которое не принадлежит остову. Произвольный граф, состоящий из остова и одного ребра, ему не принадлежащего имеет один цикл.