Розширювальне дерево та мінімальне обширне дерево

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

Перш ніж ми дізнаємося про охоплення дерев, нам слід зрозуміти два графіки: ненаправлені графіки та пов'язані графіки.

Неорієнтовані граф являє собою графік , в якому ребро не указ в будь-якому напрямку (тобто. Краї є двонаправленими).

Непрямий графік

Зв'язний граф є графік , в якому завжди є шлях від вершини до будь-якої іншої вершини.

Підключений графік

Обширне дерево

Дерево, що охоплює - це підграф ненаправленого зв’язаного графа, що включає всі вершини графа з мінімально можливою кількістю ребер. Якщо вершина пропущена, то це не дерево, що охоплює.

На ребрах можуть бути присвоєні, а можуть і не вагомі значення.

Загальна кількість дерев, що охоплюють nвершини, які можна створити з повного графіка, дорівнює .n(n-2)

Якщо ми маємо n = 4, максимальна кількість можливих охоплюючих дерев дорівнює . Таким чином, з повного графіка з 4 вершинами можна сформувати 16 дерев, що охоплюють.44-2 = 16

Приклад обширного дерева

Давайте розберемося в дереві, що охоплює, на прикладах нижче:

Нехай оригінальний графік буде таким:

Звичайний графік

Деякі з можливих охоплюючих дерев, які можна створити з наведеного графіку:

Дерево, що охоплює Дерево, що охоплює Дерево, що охоплює Дерево, що охоплює Дерево, що охоплює

Мінімальне дерево, що охоплює

Мінімальне розширювальне дерево - це обшивне дерево, в якому сума ваги країв є якомога мінімальною.

Приклад обширного дерева

Давайте розберемося у наведеному вище визначенні за допомогою прикладу нижче.

Початковий графік:

Зважений графік

Можливими охоплюючими деревами з наведеного графіку є:

Мінімальне обшивне дерево - 1 Мінімальне обшивне дерево - 2 Мінімальне обшивне дерево - 3 Мінімальне обшивне дерево - 4

Мінімальне охоплююче дерево з вищезазначених охоплюючих дерев:

Мінімальне охоплююче дерево

Мінімальне дерево охоплення з графіка знайдено за допомогою таких алгоритмів:

1. Алгоритм Прима
2. Алгоритм Крускала

Програми для обширного дерева

• Протокол маршрутизації комп’ютерних мереж
• Кластерний аналіз
• Планування цивільної мережі

Застосування мінімального дерева обшивки

• Щоб знайти шляхи на карті
• Спроектувати мережі, такі як телекомунікаційні мережі, мережі водопостачання та електричні мережі.