Snitt (grafteori)

Ett snitt i en graf med 5 noder. Detta snitt har minsta möjliga värde.
Ett annat möjligt snitt som har maximalt värde

Ett snitt är en uppdelning av alla noder i en graf i två disjunkta delmängder. Mängden av bågar som går mellan de två delmängderna kallas skurna bågar.

I en graf utan vikter på bågarna är snittets värde antalet skurna bågar. I en viktad graf är värdet summan av alla skurna bågars vikter.


From Wikipedia, the free encyclopedia · View on Wikipedia

Developed by Nelliwinne