Серед зв’язних графів найпростішу структуру мають дерева.
Означення 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 називається орієнтованим деревом (або прадеревом), що росте з кореня х0, якщо:
1) він є деревом без врахування орієнтації;
2) з х0 є орієнтований шлях до всіх інших вершин графа G.
Наприклад,
Ребра остова графа G називають гілкамидерева Т, а ребра відповідно кодерева – хордами або зв’язками.
