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.

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

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.


Minsta snittRedigera

Det existerar snabba metoder för att hitta det minsta möjliga snittet i en allmän graf.[1] Detta är av stor vikt inom bildanalys och datorseende, där många problem kan omformuleras till att hitta det minsta möjliga snittet i en stor graf.[2] Till exempel kan maximum a priori skattning för vissa markovfält formuleras som grafsnitt.[3]

Största snittRedigera

Problemet att för en given graf hitta det största möjliga snittet är NP-fullständigt[4], vilket gör det svårt att lösa för stora grafer.

Se ävenRedigera

 
Den här artikeln ingår i boken: 
Grafteori 

ReferenserRedigera

NoterRedigera

  1. ^ Papadimitriou 1998
  2. ^ Boykov 1998,2001
  3. ^ Greig et al. 1989
  4. ^ Karp 1972