• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Дерева і ліси

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

Означення 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 називають гілкамидерева Т, а ребра відповідно кодерева – хордами або зв’язками.

Читайте також:

1. Вимоги до побудови «дерева цілей».
2. Діаграми дерева вузлів і FEO
3. Довідником називається об'єкт програми, що дозволяє користу вачу вводити, зберігати і одержувати інформацію, структуруючи її у вигляді дерева.
4. Догляд за деревами і чагарниками
5. Лекція 7. Ухвалення рішення в ситуації ризику. Метод дерева рішень
6. Мал. Визначення сторін горизонту за річними кільцями зрізаного дерева
7. Метод аналізу ризику з використанням дерева рішень
8. Побудова дерева цілей
9. Приклад використання «дерева відмов».
10. Приклад використання «дерева подій».
11. Рекурсивный алгоритм формирования бинарного дерева

Переглядів: 561