Теория графов: Дерево, эквивалентные определения

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

Дерево - граф, который является связным и число его ребер равно на единицу меньше числа вершин.

Дерево - граф, любые две различные вершины которого можно соединить единственной, и при этом простой, цепью (ацикличность - означает, что между любой парой вершин в дереве существует только один путь).

Дерево - граф, не содержащий циклов, но такой, что добавляя к нему любое новое ребро, получаем ровно один (с точностью до направления обхода и начальной вершины обхода) и при том простой цикл (проходящий через добавляемое ребро).

См. также:  Алгоритмы решения экстремальных задач, Романовский, страница 106.

Граф G, все компоненты связности которого являются деревьями, называется лесом.

Если у дерева G есть по крайней мере одно ребро, то у него обязательно найдется висячая вершина.

Пусть G-связный граф, v – висячая вершина в G, G' – граф полученный из G в результате удаления вершины v и инцидентного ей ребра. Тогда G' - связный граф.

Пусть G – дерево с n вершинами и m ребрами. Тогда m = n – 1.

Пусть G' - граф являющийся деревом, G - граф полученный в результате добавления к G' новой вершины v и ребра {v, W} где W -- некоторая вершина графа G'. Тогда G - дерево.

Пусть G = (v, X) – связный граф с n ребрами и m вершинами и пусть так же выполняется равенство m = n – 1. Тогда G – дерево.


Двоичное дерево (оно же бинарное дерево): Неориентированное дерево, в котором степени вершин не превосходят 3, либо ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят 2.