Átfedő fa és a minimális átfogó fa

Ebben az oktatóanyagban példák és ábrák segítségével megismerheti az átfogó fát és a minimális átfogó fát.

Mielőtt megismerkednénk a fák átívelésével, meg kell értenünk két grafikont: irányítatlan és összekapcsolt grafikonokat.

Az irányítatlan gráf olyan gráf, amelyben az élek nem mutatnak semmilyen irányba (azaz az élek kétirányúak).

Irányítatlan grafikon

Az összekapcsolt gráf olyan gráf, amelyben mindig van egy csúcs és egy másik csúcs közötti út.

Csatlakoztatott grafikon

Feszítőfának

Az átívelő fa egy irányítatlan összekapcsolt gráf részgráfja, amely a gráf összes csúcsát tartalmazza a lehető legkevesebb éllel. Ha egy csúcs hiányzik, akkor az nem átívelő fa.

Az élek súlyokat rendelhetnek hozzá, vagy nem.

A teljes ngráfból létrehozható csúcsokkal rendelkező fák teljes száma megegyezik .n(n-2)

Ha van n = 4, akkor a lehetséges átívelő fák maximális száma megegyezik . Így 16 átívelő fa képezhető egy 4 gráfos teljes gráfból.44-2 = 16

Példa egy átfogó fára

Értsük meg az átívelő fát az alábbi példákkal:

Legyen az eredeti grafikon:

Normál grafikon

Néhány lehetséges átívelő fa, amelyet a fenti grafikon alapján létrehozhatunk:

Átfogó fa Átfogó fa Átfogó fa Átfogó fa Átfogó fa Átfogó fa

Minimális átfogó fa

A minimális átfogó fa olyan átfogó fa, amelyben az élek súlyának összege a lehető legkisebb.

Példa egy átfogó fára

Értsük meg a fenti definíciót az alábbi példa segítségével.

A kezdeti grafikon:

Súlyozott grafikon

A fenti grafikonon átívelő lehetséges fák a következők:

Minimális átfogó fa - 1 Minimális átfogó fa - 2 Minimális átfogó fa - 3 Minimális átfogó fa - 4

A fenti átnyúló fák minimális átfogó fája:

Minimális átívelő fa

A grafikonon a legkisebb átfogó fa a következő algoritmusok segítségével található:

1. Prim algoritmusa
2. Kruskal algoritmusa

Spanning Tree Applications

• Számítógépes hálózati útválasztási protokoll
• Klaszteranalízis
• Civil hálózat tervezése

Minimális Spanning Tree alkalmazások

• Útvonalak megtalálásához a térképen
• Olyan hálózatok tervezése, mint a távközlési hálózatok, a vízellátási hálózatok és az elektromos hálózatok.