Деревья. Их свойства

Определение 5.1. Неориентированным деревом называют ациклический связный граф. Ориентированным деревом называют ориентированный бесконтурный граф, у которого полустепень захода каждой вершины не больше 1 и существует ровно одна вершина, называемая корнем ориентированного дерева, полустепень захода которой равна 0. Граф, компоненты связности которого представляют собой деревья, называется лесом.

Определение 5.2. Вершина v_i ориентированного дерева называется потомком вершины v_j, если существует путь ненулевой длины из v_j в v_i. В этом же случае вершина v_j называется предком вершины v_i. Если длина пути из v_j в v_i равна 1, то v_i называется сыном v_j, а v_j – отцом v_i. Вершина, не имеющая потомков, называется листом.

Теорема 5.1 (первый критерий дерева). Неориентированный граф G является деревом тогда и только тогда, когда любые две его вершины соединяются единственной цепью.

Доказательство.

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

Для доказательства используем тот факт, что прямая теорема и ее контрапозиция эквивалентны (равносильны) в логическом смысле. Докажем контрапозицию. Контрапозиция формулируется следующим образом: Если в графе некоторые две вершины соединяются разными цепями, то этот граф не является деревом. Предположим, что для некоторых вершин a и b графа существуют две разных цепи, соединяющие a и b, например, P: a,v₁,v₂v₃, …,v _n-1,b и P’: a,v₁’,v₂ ‘,v₃’, …,v _m-1’,b. Поскольку начальные вершины этих цепей совпадают и совпадают также их конечные вершины, а пути разные, то должна существовать вершина, в которой эти цепи расходятся (пусть это будет вершина v_i= v_i’) и вершина, в которой пути должны сойтись (пусть это будет вершина v_j= v_к’). Тогда С: v_i,v _i+1,v_i+2,…,v_j-1,v_j,v_к-1’,…,v_i-1’, v_i - некоторый цикл в исходном графе и, следовательно, граф не является деревом. Контрапозиция, а вместе с ней и необходимость критерия, доказана.

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

Снова докажем контрапозицию, которая в данном случае формулируется следующим образом: Если граф не является деревом, то в нем существуют, по крайней мере, две вершины, которые недостижимы друг из друга или соединяются разными цепями.

Предположим, что граф деревом не является. Тогда либо этот граф не является связным, либо в нем существуют циклы. Если граф не является связным, то в нем существуют, по крайней мере, две вершины, недостижимые друг из друга и в этом случае контрапозиция доказана. Пусть в графе существуют циклы. Зафиксируем один из них С: a,v₁,v₂v₃, …,v _n-1, a. Тогда Р₁: v₂v₃, …,v _n-1, a и Р₂:v₂ ,v₁, a - две разные цепи, соединяющие, например. вершины v₂ и a. И в этом случае контрапозиция доказана, а, значит, доказательство достаточности критерия завершено.

Пример 5.1. Пусть нам задан граф G:

v₁v₂ v₃

G: v₄v₅v₆ v₇

v₈v₉v₁₀

Нетрудно видеть, что этот граф в силу определения или первого критерия является деревом. Предположим, что дерево подвижно в своих вершинах и подвесим его, например, за вершину v₅ так, что остальная часть дерева повиснет ниже этой вершины. Получим то же дерево G в виде

v₅

G: v₄v₉v₆

v₁ v₈v₂v₇

v₁₀v₃

Такая форма представления деревьев является стандартной. Если рассмотреть ориентированное дерево G’ (выбирая в качестве корня вершину v₅), для которого предыдущее дерево является ассоциированным графом, получим:

v₅

G’: v₄v₉v₆

v₁ v₈v₂v₇

v₁₀v₃

Такое ориентированное дерево называется порожденным деревом G. В дереве G’ вершина v₅ – корень дерева, вершины v₁,v₈,v₉, v₂, v₁₀, v₃ – листья. По аналогии с ориентированными деревьями понятия корневой вершины и листьев используется и для неориентированных деревьев. Таким образом, любое дерево рисуется от корня вниз. При этом вершины дерева располагаются по ярусам (уровням), номера которых равны длине пути от корня к вершинам данного яруса. В последнем примере на нулевом ярусе (уровне) находится корень дерева (вершина v₅), на первом ярусе – вершины v₄, v₉, v₆, на втором ярусе – вершины v₁, v₈, v₂, v₇, на третьем – вершины v₁₀, v₃. В ориентированном дереве направления ребер всегда выбираются от вершин некоторого уровня к вершинам следующего по номеру уровня.

Определение 5.3. Длина самого длинного пути из корня дерева к его листьям называется высотой дерева.

В рассмотренном выше примере 5.1 высота дерева (ориентированного или нет) равна 3.

Теорема 5.2 (второй критерий дерева). Связный граф G является деревом тогда и только тогда, когда в нем количество вершин ровно на единицу больше количества ребер.

Дата добавления: 2014-12-16