SPANNING TREE - ПІДРУЧНИК DS

У цій статті ми обговоримо остовне дерево та мінімальне остовне дерево. Але перш ніж перейти безпосередньо до охоплюючого дерева, давайте спочатку подивимося короткий опис графа та його типів.

Графік

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

Неорієнтований граф:Неорієнтований граф — це граф, у якому всі ребра не вказують на певний напрямок, тобто вони не є односпрямованими; вони двонаправлені. Його також можна визначити як граф із набором V вершин і набором E ребер, кожне ребро з’єднує дві різні вершини.Підключений граф:Зв'язний граф - це граф, в якому завжди існує шлях від вершини до будь-якої іншої вершини. Граф є зв’язним, якщо ми можемо досягти будь-якої вершини з будь-якої іншої вершини, слідуючи ребрам у будь-якому напрямку.Спрямований граф:Орієнтовані графи також відомі як орграфи. Граф є орієнтованим графом (або орграфом), якщо всі ребра, присутні між будь-якими вершинами або вузлами графа, спрямовані або мають визначений напрямок.

Тепер давайте перейдемо до охоплюючого дерева теми.

Що таке остовне дерево?

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

Остовне дерево складається з (n-1) ребер, де 'n' — це кількість вершин (або вузлів). Ребра охоплюючого дерева можуть мати, а можуть і не мати ваги. Усі можливі остовні дерева, створені з даного графа G, мали б однакову кількість вершин, але кількість ребер у остовному дереві дорівнювала б кількості вершин у даному графі мінус 1.

Повний неорієнтований граф може мати п^n-2 кількість остовних дерев де п кількість вершин у графі. Припустимо, якщо n = 5 , кількість максимально можливих охоплюючих дерев буде 5^5-2= 125.

Застосування остовного дерева

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

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

Тепер давайте розберемося з остовним деревом за допомогою прикладу.

Приклад остовного дерева

Припустимо, що графік -

Як обговорювалося вище, охоплююче дерево містить таку ж кількість вершин, як і граф, кількість вершин у наведеному вище графі дорівнює 5; отже, остовне дерево буде містити 5 вершин. Ребра в остовному дереві дорівнюватимуть числу вершин у графі мінус 1. Отже, у остовному дереві буде 4 ребра.

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

Властивості остовного дерева

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

Може бути більше одного остовного дерева зв’язного графа G.
Остовне дерево не має жодних циклів або циклів.
Остовне дерево є мінімальний зв'язок, тому видалення одного ребра з дерева зробить граф роз’єднаним.
Остовне дерево є максимально ациклічний, тому додавання одного краю до дерева створить петлю.
Може бути максимум п^n-2 кількість охоплюючих дерев, які можна створити з повного графа.
Остовне дерево має n-1 ребра, де 'n' — кількість вузлів.
Якщо граф є повним графом, то остовне дерево можна побудувати шляхом видалення максимальних (e-n+1) ребер, де «e» — кількість ребер, а «n» — кількість вершин.

Таким чином, остовне дерево є підмножиною зв’язного графа G, і не існує остовного дерева роз’єднаного графа.

Мінімальне остовне дерево

Мінімальне остовне дерево можна визначити як остовне дерево, в якому сума ваг ребра мінімальна. Вага остовного дерева - це сума ваг, наданих ребрам остовного дерева. У реальному світі ця вага може розглядатися як відстань, навантаження на транспорт, затори або будь-яке випадкове значення.

Приклад мінімального остовного дерева

Розберемося з мінімальним остовним деревом на прикладі.

Сума ребер наведеного вище графа дорівнює 16. Деякі з можливих остовних дерев, створених із наведеного вище графа, такі:

Таким чином, мінімальне охоплююче дерево, вибране з наведених вище охоплюючих дерев для даного зваженого графа, є -

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

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

Мінімальне остовне дерево може використовуватися для проектування мереж водопостачання, телекомунікаційних мереж, електричних мереж.
Його можна використовувати для пошуку шляхів на карті.

Алгоритми мінімального остовного дерева

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

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

Давайте подивимося короткий опис обох перерахованих вище алгоритмів.

Алгоритм Прима - Це жадібний алгоритм, який починається з порожнього остовного дерева. Він використовується для знаходження мінімального остовного дерева з графіка. Цей алгоритм знаходить підмножину ребер, яка включає кожну вершину графа, так що суму ваг ребер можна мінімізувати.

пояснити незалежність даних

Щоб дізнатися більше про алгоритм прим, ви можете натиснути посилання нижче - https://www.javatpoint.com/prim-algorithm

Алгоритм Крускала - Цей алгоритм також використовується для знаходження мінімального остовного дерева для зв’язного зваженого графа. Алгоритм Крускала також дотримується жадібного підходу, який знаходить оптимальне рішення на кожному етапі замість зосередження на глобальному оптимумі.

Щоб дізнатися більше про алгоритм прим, ви можете натиснути посилання нижче - https://www.javatpoint.com/kruskal-algorithm

Отже, це все про статтю. Сподіваюся, стаття буде для вас корисною та інформативною. Тут ми обговорили охоплююче дерево та мінімальне охоплююче дерево, а також їхні властивості, приклади та застосування.