Content deleted Content added
include wikilink within sentence |
It is the cost of the cut C that needs to equal f(x) and not the flow through C. Only the cost of the min-cut and the max-flow are equal. |
||
Line 2:
'''Graph cut optimization''' is a [[combinatorial optimization]] method applicable to a family of [[function (mathematics)|function]]s of [[Continuous or discrete variable|discrete variable]]s, named after the concept of [[cut (graph theory)|cut]] in the theory of [[flow network]]s. Thanks to the [[max-flow min-cut theorem]], determining the [[minimum cut]] over a [[graph (discrete mathematics)|graph]] representing a flow network is equivalent to computing the [[maximum flow]] over the network. Given a [[pseudo-Boolean function]] <math>f</math>, if it is possible to construct a flow network with positive weights such that
* each cut <math>C</math> of the network can be mapped to an assignment of variables <math>\mathbf{x}</math> to <math>f</math> (and vice versa), and
* the
then it is possible to find the [[global optimum]] of <math>f</math> in [[polynomial time]] by computing a minimum cut of the graph. The mapping between cuts and variable assignments is done by representing each variable with one node in the graph and, given a cut, each variable will have a value of 0 if the corresponding node belongs to the component connected to the source, or 1 if it belong to the component connected to the sink.
| |||