feszítőfának
Feszítőfának - egy aciklikus csatlakozik részgráfját csatlakoztatott irányítatlan gráf. amely magában foglalja a csúcsot. Informálisan elmondható, feszítőfa áll egy részhalmaza a széleit a gráf úgy, hogy minden csúcsa a grafikon, akkor kap, hogy más vertex, mozgó ezen élek, és nincsenek ciklusok, azaz minden csomópont nem tud bejutni magát, anélkül, hogy néhány él kétszer.
A koncepció egy átívelő erdő kétértelmű, lehet érteni az alábbi részgráfok:
- bármilyen aciklusos részgráf, amely magában foglalja az összes csúcsot, de nem feltétlenül csatlakozik;
- egy szétkapcsolt gráf - részgráfot álló társulásai átívelő fák minden egyes csatlakoztatott komponensek.
Tulajdonságok [szerkesztés]
- Bármilyen feszítőfának egy gráfot, melynek csúcsai pontosan egy él.
- A száma feszít®fája egy teljes gráf expresszálódik a tetejét a jól ismert képlet Cayley. [2]
- Az általános esetben, száma átívelő fák tetszőleges oszlopban lehet segítségével számítjuk ki az úgynevezett Kirchhoff tétel.
Algoritmusok [idézet]
A feszítőfa lehet kialakítani gyakorlatilag minden gráf bejáráshoz, például keresni a mélység vagy szélességi keresést. Ez magában foglalja az összes megfejtést, hogy az algoritmus, szkennelés a felső, feltárja annak adjacencia listáját egy új, még nem azonosított csúcs.
Feszítőfa épült áthaladó gráf algoritmus Dijkstra. a tetejétől kezdve, hogy az ingatlan, hogy a legrövidebb utat a grafikonon a felső, mielőtt bármilyen más - ez a (az egyetlen) kiút a csúcsra ebben a feszítőfa.
Vannak is több párhuzamos és elosztott algoritmusok megtalálásához feszítőfa. Egy gyakorlati példa az elosztott algoritmus eredményezhet az STP.
Ha minden élét hozzárendelve súlya (hossz, költség, és így tovább. P.), majd találni az optimális feszítőfát, amely minimalizálja a súlyok összege a széleit a tagja, részt vesznek számos algoritmusok megtalálásához a minimális feszítőfa [3].
A probléma találni feszítőfának, amelyben a minden csúcsa nem haladja állandó, meghatározott előleg, NP-teljes. [4]