miniatyr|stående|Ett snitt i en graf med 5 noder. Detta snitt har minsta möjliga värde. miniatyr|stående|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
Det existerar snabba metoder för att hitta det minsta möjliga snittet i en allmän graf.Papadimitriou 1998 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.Boykov 1998,2001 Till exempel kan maximum a priori skattning för vissa markovfält formuleras som grafsnitt.Greig et al. 1989
Största snitt Problemet att för en given graf hitta det största möjliga snittet är NP-fullständigtKarp 1972, vilket gör det svårt att lösa för stora grafer.
Se även Grafteori
Referenser Y. Boykov, O. Veksler and R. Zabih (1998), "Markov Random Fields with Efficient Approximations", International Conference on Computer Vision and Pattern Recognition (CVPR). Y. Boykov, O. Veksler and R. Zabih (2001), "Fast approximate energy minimisation via graph cuts", IEEE Transactions on Pattern Analysis and Machine Intelligence, 29, 1222–1239. D.M. Greig, B.T. Porteous and A.H. Seheult (1989), Exact maximum a posteriori estimation for binary images, Journal of the Royal Statistical Society Series B, 51, 271–279. R. M. Karp, Reducibility among combinatorial problems, in R. E. Miller and J. W. Thacher (eds.), Complexity of Computer Computation, Plenum Press, New York, 85-103 (1972) M. X. Goemans, and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, 42, 6 (Nov. 1995), 1115-1145
Noter
Kategori:Grafteori Kategori:Kombinatorik