TechCodeview

Ebben a cikkben a feszítőfát és a minimális feszítőfát tárgyaljuk. Mielőtt azonban közvetlenül a feszítőfa felé haladnánk, először lássuk a gráf és típusainak rövid leírását.

Grafikon

A gráf csúcsok és élek csoportjaként definiálható, hogy ezeket a csúcsokat összekapcsolja. A grafikonok típusai a következők:

Irányítatlan grafikon:Az irányítatlan gráf olyan gráf, amelyben az összes él nem mutat egyetlen irányt sem, azaz nem egyirányú; kétirányúak. Definiálható gráfként is, amelyben V csúcsok és E élek halmaza található, és mindegyik él két különböző csúcsot köt össze.Összekapcsolt grafikon:Az összefüggő gráf olyan gráf, amelyben mindig létezik egy út egy csúcstól bármely másik csúcsig. Egy gráf akkor összefüggő, ha bármelyik csúcsból bármelyik csúcsot elérhetjük az élek bármelyik irányba történő követésével.Irányított grafikon:Az irányított gráfokat digráfoknak is nevezik. A gráf irányított gráf (vagy digráf), ha a gráf bármely csúcsa vagy csomópontja között lévő összes él irányított vagy meghatározott irányú.

Most pedig térjünk át a fán átívelő téma felé.

Mi az az átívelő fa?

Egy feszítőfa egy irányítatlan összefüggő gráf részgráfjaként definiálható. Tartalmazza az összes csúcsot a lehető legkevesebb éllel együtt. Ha valamelyik csúcs kimarad, az nem feszítőfa. A feszítőfa a gráf egy olyan részhalmaza, amelynek nincsenek ciklusai, és nem is lehet szétválasztani.

Egy feszítőfa (n-1) élből áll, ahol 'n' a csúcsok (vagy csomópontok) száma. A feszítőfa éleihez lehet súly hozzárendelve, de lehet, hogy nincs. Az adott G gráfból létrehozott összes lehetséges feszítőfának ugyanannyi csúcsa lenne, de a feszítőfában az élek száma egyenlő lenne az adott gráf csúcsainak számával mínusz 1.

Egy teljes irányítatlan gráfnak lehet n^n-2 átívelő fák száma hol n a gráf csúcsainak száma. Tegyük fel, ha n = 5 , a maximálisan lehetséges átívelő fák száma lenne 5^5-2= 125.

A feszítőfa alkalmazásai

Alapvetően egy feszítőfát használnak a gráf összes csomópontjának összekötéséhez szükséges minimális útvonal megtalálására. A feszítőfa néhány gyakori alkalmazása az alábbiakban található:

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

Most egy példa segítségével értsük meg az átívelő fát.

Példa feszítőfára

Tegyük fel, hogy a grafikon -

Mint fentebb tárgyaltuk, egy feszítőfa ugyanannyi csúcsot tartalmaz, mint a gráf, a fenti gráf csúcsainak száma 5; ezért a feszítőfa 5 csúcsot fog tartalmazni. A feszítőfában lévő élek egyenlőek lesznek a gráf csúcsainak számával mínusz 1. Tehát a feszítőfában 4 él lesz.

A fenti grafikonból létrehozandó lehetséges átívelő fák némelyike ​​a következő:

A feszítőfa tulajdonságai

A feszítőfa néhány tulajdonsága a következő:

• Egy összefüggő G gráfnak egynél több feszítőfája lehet.
• Egy feszítőfának nincsenek ciklusai vagy hurkai.
• Egy átívelő fa az minimálisan csatlakoztatva, így a fa egyik élének eltávolításával a gráf megszakad.
• Egy átívelő fa az maximálisan aciklikus, így az egyik él hozzáadása a fához hurkot hoz létre.
• Maximum lehet n^n-2 a teljes gráfból létrehozható feszítőfák száma.
• Egy átívelő fának van n-1 élek, ahol „n” a csomópontok száma.
• Ha a gráf egy teljes gráf, akkor a feszítőfa a maximális (e-n+1) élek eltávolításával állítható össze, ahol 'e' az élek száma, 'n' pedig a csúcsok száma.

Tehát egy feszítőfa a G összefüggő gráf egy részhalmaza, és nincs feszítőfa egy szétkapcsolt gráfnak.

Minimális feszítőfa

Minimális feszítőfa az a feszítőfa, amelyben az él súlyainak összege minimális. A feszítőfa súlya a feszítőfa éleihez adott súlyok összege. A való világban ez a súly tekinthető távolságnak, forgalmi terhelésnek, torlódásnak vagy bármilyen véletlenszerű értéknek.

Példa a minimális feszítőfára

Értsük meg egy példa segítségével a minimális feszítőfát.

A fenti gráf éleinek összege 16. A fenti gráfból létrehozott lehetséges feszítőfák közül néhány:

Tehát az adott súlyozott gráfhoz a fenti feszítőfák közül kiválasztott minimális feszítőfa:

Minimális feszítőfa alkalmazásai

A minimális feszítőfa alkalmazásai a következők:

• A minimális feszítőfa vízellátó hálózatok, távközlési hálózatok és elektromos hálózatok tervezésére használható.
• Használható útvonalak keresésére a térképen.

Algoritmusok a minimális feszítőfához

Egy súlyozott gráfból egy minimális feszítőfát találhatunk az alábbi algoritmusok segítségével -

• Prim algoritmusa
• Kruskal algoritmusa

Nézzük meg a fent felsorolt ​​mindkét algoritmus rövid leírását.

Prim algoritmusa - Ez egy mohó algoritmus, amely egy üres feszítőfával kezdődik. Arra használják, hogy megtalálják a gráfból a minimális feszítőfát. Ez az algoritmus megkeresi az élek azon részhalmazát, amely a gráf minden csúcsát tartalmazza úgy, hogy az élek súlyának összege minimalizálható.

mutató a c

Ha többet szeretne megtudni a prim algoritmusáról, kattintson az alábbi linkre - https://www.javatpoint.com/prim-algorithm

Kruskal algoritmusa - Ezt az algoritmust arra is használják, hogy megtalálják a minimális feszítőfát egy összekapcsolt súlyozott gráfhoz. Kruskal algoritmusa is a mohó megközelítést követi, amely minden szakaszban megtalálja az optimális megoldást ahelyett, hogy a globális optimumra koncentrálna.

Ha többet szeretne megtudni a prim algoritmusáról, kattintson az alábbi linkre - https://www.javatpoint.com/kruskal-algoritm

Szóval ennyi a cikkről. Reméljük, hogy a cikk hasznos és informatív lesz az Ön számára. Itt tárgyaltuk a feszítőfát és a minimális feszítőfát, valamint azok tulajdonságait, példáit és alkalmazásait.