Graph cut optimization: Difference between revisions

Revision as of 15:06, 16 January 2019

Revision as of 21:29, 16 January 2019

Line 8:

== Representability ==

A [[pseudo-Boolean function]] <math>f: \{0, 1\}^n \to \mathbb{R}</math> is said to be ''representable'' if there exists a graph <math>G = (V, E)</math> with non-negative weights and with source and sink nodes <math>s</math> and <math>t</math> respectively, and there existexists a set of nodes <math>V_0 = \{v_1, \dots, v_n\} \subset V - \{s, t\}</math> such that, for each tuple of values <math>(x_1, \dots, x_n) \in \{0, 1\}^n</math> assigned to the variables, <math>f(x_1, \dots, x_n)</math> equals (up to a constant) the value of the flow determined by a minimum [[cut (graph theory)|cut]] <math>C = (S, T)</math> of the graph <math>G</math> such that <math>v_i \in S</math> if <math>x_i = 0</math> and <math>v_i \in T</math> if <math>x_i = 1</math>.<ref name="what" />

It is possible to classify pseudo-Boolean functions according to their order, determined by the maximum number of variables contributing to each single term. All first order functions, where each term depends fromupon at most one variable, are always representable. Quadratic functions

:<math> f(\mathbf{x}) = w_0 + \sum_i w_i(x_i) + \sum_{i < j} w_{ij}(x_i, x_j) . </math>