„Minimális feszítőfa” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
→Tulajdonságai: Kapcsolata a gráf köreivel és vágásaival |
→Tulajdonságai: minimális költségű él |
||
18. sor:
Ugyanis, ha egy feszítő fában nincs benne ez az él, akkor hozzávéve keletkezik egy kör. Elhagyva a körnek azt a másik élét, ami éle ''C''-nek is, a feszítő fa költsége csökken.
Ezek az állítások csak arra az esetre igazak, ha a kör, illetve a vágás élei között egyértelműen van legnagyobb, illetve legkisebb költségű.
===Minimális költségű él===
Ha a gráfban van egy egyértelmű legkisebb költségű él, akkor a gráf minimális költségű feszítő fáinak mindegyike tartalmazni fogja ezt az élt. Különben a vágásokra alkalmazott érveléssel kimutatható, hogy az adott feszítő fa nem minimális költségű.
==Lásd még==
| |||