Дерева і ліси

Серед зв’язних графів найпростішу структуру мають дерева.

Означення 2.3.4. Деревом називають скінчений зв’язний граф без циклів, який має щонайменше дві вершини.

Граф є деревом тоді і тільки тоді, коли кожна пара різних його вершин з’єднана одним і тільки одним ланцюгом.

Видалення довільного ребра з дерева робить його незв’язним, оскільки це ребро є складовою єдиного ланцюга, що з’єднує будь-які дві точки.

Теорема 2.3.3. Для графа G, який має n (n>1) вершин і m ребер, наступні твердження є еквівалентними:

1) G є деревом;

2) є лише один ланцюг між будь-якими двома вершинами в G;

3) G є зв’язним і m=n-1;

4) G не має циклів і m=n-1;

5) G не має циклів і при з’єднанні ребром довільних двох несуміжних вершин отримуємо граф, який має лише один цикл;

6) G є зв’язним проте втрачає цю властивість, якщо вилучити одне ребро.

Означення 2.3.5. Деревом графа G називають зв’язний підграф графа G, що не має циклів.

Означення 2.3.6. Остовом або покриттям графа G називають дерево графа G, що містить всі вершини графа G.

Означення 2.3.7. Кодерево Т* остова Т графа G – це підграф графа G, що містить всі вершини графа G і лише ті ребра, які не входять в Т.

Орієнтований граф G називається орієнтованим деревом (або прадеревом), що росте з кореня х₀, якщо:

1) він є деревом без врахування орієнтації;

2) з х₀ є орієнтований шлях до всіх інших вершин графа G.

Наприклад,

Ребра остова графа G називають гілкамидерева Т, а ребра відповідно кодерева – хордами або зв’язками.