Snitt (grafteori)

Från Wikipedia
Hoppa till: navigering, sök
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.


Minsta snitt[redigera | redigera wikitext]

Huvudartikel: Max-flöde, minsta-snitt

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 snitt[redigera | redigera wikitext]

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 även[redigera | redigera wikitext]

Office-book.svg
Den här artikeln ingår i boken: 
Grafteori 

Referenser[redigera | redigera wikitext]

Noter[redigera | redigera wikitext]

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