Деревья. Теорема об эквивалентных определениях дерева

Дерево – это граф, в котором выполняются любые два условия из трех условий следующей теоремы.

Теорема. Пусть для (p, q)-графа G рассматриваются три условия:

(1) G – связный граф;

(2) G – ациклический граф;

(3) p = q +1.

Тогда каждое из условий (1) – (3) следует из двух других.

Доказательство. (1), (2) Þ (3). Докажем методом математической индукции по числу ребер q. При q =1 и q =2 утверждение теоремы легко проверить. Если q ³3, то удалим одно из серединных ребер. Тогда граф G разбивается на 2 подграфа – (p ₁, q ₁)-граф G ₁ и (p ₂, q ₂)-граф G ₂, p = p ₁+ p ₂, q = q ₁+ q ₂+1. Так как q ₁< q, q ₂< q, то по индуктивному предположению, p ₁= q ₁+1, p ₂= q ₂+1, откуда p = p ₁+ p ₂= q ₁+1+ q ₂+1=(q ₁+ q ₂+1)+1= q +1.

(1), (3) Þ (2). Докажем методом от противного. Допустим, что граф G содержит цикл с s вершинами и с s ребрами. Каждый из оставшихся p - s вершин присоединяется к этому циклу или к ранее присоединенному ребру "новым", "своим" ребром. Получается, что q не меньше суммы s +(p - s)= p, что противоречит условию (3). Значит, граф G не содержит циклов.

(2), (3) Þ (1). Докажем методом от противного. Допустим, что граф G состоит из k компонент связности(k ³1). Каждая из них будет связным ациклическим графом G ₁, …, G_k, соответственно с p ₁,…, p_k вершинами и q ₁,…, q_k ребрами, p = p ₁+…+ p_k, q = q ₁+…+ q_k. Для графов G ₁, …, G_k имеем k равенств: p ₁= q ₁+1, …, p_k = q_k +1. Отсюда p = p ₁+…+ p_k =(q ₁+1)+…+(p_k +1)= q + k, что противоречит условию (3). Значит, граф G связный.