Snitt (grafteori)
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]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]| Den här artikeln ingår i boken: Grafteori |
Referenser
[redigera | redigera wikitext]- 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
- Christos H. Papadimitriou, Kenneth Steiglitz (1998). Combinatorial Optimization: Algorithms and Complexity. Dover. sid. 120-128. ISBN 0486402584