6. gyakorlat

Súlyozott gráfok

Gráf vágás

Az összes olyan él halmaza, amely összeköt két tetszőleges részgráfot.

Minimális összköltségű feszítőfa keresésénél:

Vegyünk egy tetszőleges csúcsot. Legyen \(S := \{\text{Az előbb kiválasztott csúcsunk}\}\)
Vegyünk azokat az éleket, amelyek elvágják az \(S\)-beli csúcsokat a többi csúcstől
Ezen élek közül vegyük a legkisebb súlyúhoz tartozó csúcsot
Ezt a csúcsot adjuk hozzá \(S\)-hez.
Ismételjük a 2.-4. pontokat, amíg van olyan pont, ami nincs \(S\)-ben

TBD