Эквивалентные определения дерева

Деревья

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

Существует несколько определений дерева.

1) Связный граф с n вершинами и n – 1 ребрами.

2) Связный граф без циклов.

3) Граф, в котором каждая пара вершин соединена точно одной цепью.

Докажем эквивалентность этих определений.

1) Þ 2). Докажем, что в связном графе с n вершинами и n – 1 ребрами нет циклов. Предположим противное, т.е. цикл есть и e = (u, v) – ребро этого цикла. Удалим это ребро. Тогда граф останется связным, т.к. из u в v можно добраться по другой половинке цикла. В графе G\e n вершин, n – 2 ребер и он связан, т.е. у него 1 компонента связности, k = 1. По 3-й теореме о связности должно быть m = n – 2 ³ n – 1 – противоречие. Следовательно, циклов нет.

2) Þ 3). Хотя бы одна цепь, соединяющая u и v должна быть, т.к. граф связный. Предположим, что цепей не одна, а хотя бы две. Тогда, по свойству 3 маршрута, из них можно составить цикл – противоречие, т.е. 2-й цепи нет.

3) Þ 1). Из 3) следует, что граф связный. Так как каждая пара вершин соединена точно одной цепью, то удаление любого ребра увеличит на 1 число компонент связности. Пусть в графе m ребер. По 3-й теореме о связности должно быть m ³ n – 1. Удалив 1 ребро, получим m – 1³ n – 2, т.к. станет k = 2. Удалив 2 ребра, получим k = 3 и m – 2³ n – 3, и т.д. Удалим n – 1 ребер, получим k = n и m – (n – 1)³ n – n. Но, т.к. k = n, то ребер больше нет. Следовательно, они были удалены за n – 1 шагов, поэтому m = n – 1, ЧТД.

Задание 1. Пусть Т – дерево, Т₁, Т₂ – его поддеревья. Доказать, что – тоже дерево.