---
tag: 3AQZHY04B7
kind: concept
name: Graph cut optimization
sources:
  - wikipedia: en:59654517@r1373893701
    locator: Graph cut optimization
    note: adopted
    mention: wikipedia://en/59654517
    sections: [Summary]
same_as:
  wikidata: Q60321144
  wikipedia: Graph cut optimization
inventory: [HZ80Q3SVXK]
---

## Summary

**Graph cut optimization** is a combinatorial optimization method applicable to a family of [[functions|0EPAT51DXQ]] of discrete variables, named after the concept of cut in the theory of flow networks. Thanks to the max-flow min-cut theorem, determining the minimum cut over a [[graph|00C0BR7D7H]] representing a flow network is equivalent to computing the maximum flow over the network. Given a pseudo-Boolean function $f$, if it is possible to construct a flow network with positive weights such that