„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: jelölések |
→Tulajdonságai: Minimális költségű részgráf |
||
8. sor:
Legyen ''T''<sub>1</sub> és ''T''<sub>2</sub> is minimális súlyú feszítő fa. ''T''<sub>1</sub> és ''T''<sub>2</sub> különbözőek, tehát van egy ''e''<sup>1</sup> él ''T''<sub>1</sub>-ben, ami nincs ''T''<sub>2</sub>-ben, és ''T''<sub>2</sub>-ben egy ''e''<sup>2</sup> él, ami nincs ''T''<sub>1</sub>-ben. Ekkor ''e''<sup>2</sup>-t hozzávéve ''T''<sub>1</sub>-hez keletkezik egy kör. Ha most ''e''<sup>1</sup> költsége kisebb, mint ''e''<sup>2</sup>-é, akkor ''e''<sup>1</sup>-t kidobva egy kisebb súlyú feszítő fához jutunk, ami ellentmondás. Fordítva, ha ''e''<sup>1</sup> költsége a nagyobb, szintén ellentmondáshoz jutunk a ''T''<sub>2</sub> fához hozzávéve az ''e''<sup>1</sup> élt, és kidobva ''e''<sup>2</sup>-t.
===Minimális költségű részgráf===
Ha a költségek nem negatívak, akkor a minimális feszítő fa a minimális költségű összefüggő részgráf, mivel a körökből ki lehetne venni egy élt a részgráf szétesése nélkül.
==Lásd még==
| |||