Page 53 - 4386

Рисунок 5.3

Основні властивості дерев та лісу є такими.

1. Будь-яке дерево T з n вершинами містить n-1 ребро.

2. Для будь-яких вершин v та w дерева T існує лише один

простий ланцюг, що з’єднує v та w.

3. Дерево T є таким ациклічним графом, що коли будь-які

його несуміжні вершини v та w з’єднати ребром (v, w), то

одержаний граф міститиме рівно один цикл.

4. Для довільного дерева T=(V, E) з n вершинами

виконується ∑ ( δ v) = (2 n − )1 .
v ∈V

5. Будь-яке нетривіальне дерево T=(V, E) має принаймні дві

кінцеві вершини.

6. У графі G з n вершинами, який має більше ніж n−1 ребро,

є принаймні один цикл.

7. Ліс F, який має n вершин і складається з k дерев, містить

n−k ребер.

5.2 Кореневі дерева

Припустимо, що дерево являє собою деякий рухомий у

вершинах фізичний об'єкт, такий, що можна підвісити за кожну з

вершин. Так, наприклад, якщо дерево, зображене на рис. 5.1 а

52