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

9 10 11 12 13 14 15

Пусть , , тогда следующие утверждения попарно эквивалентны:

1. дерево, то есть связный граф без циклов;

2. граф без циклов и ;

3. связный граф и ;

4. связный граф, но при удалении любого ребра становится несвязным;

5. граф без циклов, но при добавлении любого ребра в нем образуется цикл.

Доказательство. Покажем, что из .

: дерево, по теореме о числе ребер в дереве .

: По лемме о числе связных компонент в графе без циклов

, у нас , т.е. связный граф.

: Если и , то , т.е. граф

несвязан.

: Если в графе имеется цикл, то удаление ребра из цикла

оставляет граф связным, что противоречит условию.

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

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

Среди деревьев особое место занимают корневые деревья, которые используются в процедурах поиска в информационных системах.

Дадим индуктивное определение корневого дерева.

1. Граф, имеющий единственную вершину и пустое множество ребер, называется корневым деревом с корнем .

2. Пусть – корневые деревья с корнями и каждое . При этом при .

3. Пусть , тогда граф , где и , называется корневым деревом с корнем . Деревья называются поддеревьями дерева .

Определение. Упорядоченным корневым деревом называется корневое дерево , в котором задан порядок его поддеревьев и каждое поддерево – упорядоченное дерево.

Получим оценку числа упорядоченных корневых деревьев. Для этого введем кодировку упорядоченных корневых деревьев. Кодировать будем согласно индуктивному определению корневого дерева.

1. Дереву поставим в соответствие пустое слово.