Обхващащо дърво и минимално обхващащо дърво

В този урок ще научите за обхващащото дърво и минималното обхващащо дърво с помощта на примери и фигури.

Преди да научим за обхващащи дървета, трябва да разберем две графики: ненасочени графики и свързани графики.

Един ненасочена графика е графика, в която краищата не показват във всяка посока (т.е.. Ръбовете са двупосочни).

Ненасочена графика

А свързан граф е графика, в която винаги има път от връх до връх друг.

Свързана графика

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

Обхващащото дърво е подграфа на ненасочена свързана графика, която включва всички върхове на графиката с минимален възможен брой ръбове. Ако даден връх е пропуснат, тогава той не е обхващащо дърво.

Ръбовете могат да имат или не да имат присвоени тежести.

Общият брой на обхващащи дървета с nвърхове, които могат да бъдат създадени от пълна графика, е равен на .n(n-2)

Ако имаме n = 4, максималният брой на възможните обхващащи дървета е равен на . По този начин, 16 обхващащи дървета могат да бъдат оформени от пълна графика с 4 върха.44-2 = 16

Пример за обширно дърво

Нека разберем обхващащото дърво с примери по-долу:

Нека оригиналната графика бъде:

Нормална графика

Някои от възможните обхващащи дървета, които могат да бъдат създадени от горната графика, са:

Обхващащо дърво Обхващащо дърво Обхващащо дърво Обхващащо дърво Обхващащо дърво Обхващащо дърво

Минимално обхващащо дърво

Минимално обхващащо дърво е обхващащо дърво, при което сборът от теглото на ръбовете е възможно най-малък.

Пример за обширно дърво

Нека разберем горната дефиниция с помощта на примера по-долу.

Началната графика е:

Претеглена графика

Възможните обхващащи дървета от горната графика са:

Минимално обхващащо дърво - 1 Минимално обхващащо дърво - 2 Минимално обхващащо дърво - 3 Минимално обхващащо дърво - 4

Минималното обхващащо дърво от горните обхващащи дървета е:

Минимално обхващащо дърво

Минималното обхващащо дърво от графика се намира, като се използват следните алгоритми:

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

Приложения за обхващащо дърво

  • Протокол за маршрутизиране на компютърна мрежа
  • Клъстер анализ
  • Планиране на гражданската мрежа

Приложения за минимално обхващащо дърво

  • За да намерите пътеки в картата
  • Да проектира мрежи като телекомуникационни мрежи, водоснабдителни мрежи и електрически мрежи.

Интересни статии...