Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

6.3. Minimális feszítőfa

6.3. Minimális feszítőfa

6.15. Definíció. Egy irányítatlan gráf feszítőfája a gráfnak az a részgráfja, amely fagráf és tartalmazza a gráf összes cúcspontját.

6.16. Definíció. A fa súlya a

számérték.

6.17. Definíció. Minimális feszítőfáról beszélünk, ha értéke minimális az összes feszítőfára nézve. A minimális feszítőfa nem feltétlenül egyértelmű.

6.18. Definíció. Legyen egy minimális feszítőfa egy része. -ra nézve biztonságos egy él, ha -hoz hozzávéve továbbra is valamely minimális feszítőfa része marad.

6.19. Definíció. Egy irányítatlan gráf vágása a kettéosztása egy és egy halmazra.

6.20. Definíció. Az él keresztezi az vágást, ha annak egyik végpontja -ben, másik végpontja -ben található.

6.21. Definíció. Egy vágás kikerüli az halmazt, ha az A egyetlen éle sem keresztezi a vágást.

6.22. Definíció. Egy él könnyű egy vágásban, ha a vágást keresztező élek közül neki van a legkisebb súlya.

6.23. Tétel. Legyen egy összefüggő, irányítatlan gráf súlyfüggvénnyel. Legyen egy olyan részhalmaza -nek, amelyik valamelyik minimális feszítőfájának is része. Legyen tetszőleges -t kikerülő vágása a -nek. Legyen könnyű él az vágásban. Ekkor az él biztonságos az -ra nézve.

6.24. Következmény. Legyen egy összefüggő, irányítatlan gráf gráf súlyfüggvénnyel. Legyen egy olyan részhalmaza -nek, amelyik valamelyik minimális feszítőfájának is része. Legyen egy összefüggő komponens a erdőben. Ha a -t és a valamely másik komponenesét összekötő könnyű él, akkor az él biztonságos az -ra nézve.

6.3.1. Kruskal-algoritmus

6.1. Példa.

Animációként:

6.3.2. Prim-algoritmus

6.2. Példa.

Animációként: