“Cut (graph theory)”的意思、由来-开放百科全书

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.

In a flow network, an s–t cut is a cut that requires the source and the sink to be in different subsets, and its cut-set only consists of edges going from the source's side to the sink's side. The capacity of an s–t cut is defined as the sum of the capacity of each edge in the cut-set.

Definition

The cut-set of a cut

is the set

of edges that have one endpoint in S and the other endpoint in T.

If s and t are specified vertices of the graph G, then an s–t cut is a cut in which s belongs to the set S and t belongs to the set T.

In an unweighted undirected graph, the size or weight of a cut is the number of edges crossing the cut. In a weighted graph, the value or weight is defined by the sum of the weights of the edges crossing the cut.

A bond is a cut-set that does not have any other cut-set as a proper subset.

Minimum cut

A cut is minimum if the size or weight of the cut is not larger than the size of any other cut. The illustration on the right shows a minimum cut: the size of this cut is 2, and there is no cut of size 1 because the graph is bridgeless.

The max-flow min-cut theorem proves that the maximum network flow and the sum of the cut-edge weights of any minimum cut that separates the source and the sink are equal. There are polynomial-time methods to solve the min-cut problem, notably the Edmonds–Karp algorithm.^[1]

Maximum cut

A cut is maximum if the size of the cut is not smaller than the size of any other cut. The illustration on the right shows a maximum cut: the size of the cut is equal to 5, and there is no cut of size 6, or |E| (the number of edges), because the graph is not bipartite (there is an odd cycle).

The max-cut problem is also APX-hard, meaning that there is no polynomial-time approximation scheme for it unless P = NP.^[4]

However, it can be approximated to within a constant approximation ratio using semidefinite programming.^[5]

Note that min-cut and max-cut are not dual problems in the linear programming sense, even though one gets from one problem to other by changing min to max in the objective function. The max-flow problem is the dual of the min-cut problem.^[6]

Sparsest cut

The sparsest cut problem is to bipartition the vertices so as to minimize the ratio of the number of edges across the cut divided by the number of vertices in the smaller half of the partition. This objective function favors solutions that are both sparse (few edges crossing the cut) and balanced (close to a bisection). The problem is known to be NP-hard, and the best known approximation algorithm is an

approximation due to {{Harvtxt|Arora|Rao|Vazirani|2009}}.^[7]

Cut space

The family of all cut sets of an undirected graph is known as the cut space of the graph. It forms a vector space over the two-element finite field of arithmetic modulo two, with the symmetric difference of two cut sets as the vector addition operation, and is the orthogonal complement of the cycle space.^[8]^[9] If the edges of the graph are given positive weights, the minimum weight basis of the cut space can be described by a tree on the same vertex set as the graph, called the Gomory–Hu tree.^[10] Each edge of this tree is associated with a bond in the original graph, and the minimum cut between two nodes s and t is the minimum weight bond among the ones associated with the path from s to t in the tree.

See also

References

1. ^{{citation | last1 = Cormen | first1 = Thomas H. | author1-link = Thomas H. Cormen | last2 = Leiserson | first2 = Charles E. | author2-link = Charles E. Leiserson | last3 = Rivest | first3 = Ronald L. | author3-link = Ronald L. Rivest | last4 = Stein | first4 = Clifford | author4-link = Clifford Stein | edition = 2nd | isbn = 0-262-03293-7 | page = 563,655,1043 | publisher = MIT Press and McGraw-Hill | title = Introduction to Algorithms | year = 2001}}.
2. ^{{citation | last1 = Garey | first1 = Michael R. | author1-link = Michael R. Garey | last2 = Johnson | first2 = David S. | author2-link = David S. Johnson | isbn = 0-7167-1045-5 | at = A2.2: ND16, p. 210 | publisher = W.H. Freeman | title = A Guide to the Theory of NP-Completeness | year = 1979}}.
3. ^{{citation | last = Karp | first = R. M. | author-link = Richard Karp | editor1-last = Miller | editor1-first = R. E. | editor2-last = Thacher | editor2-first = J. W. | contribution = Reducibility among combinatorial problems | location = New York | pages = 85–103 | publisher = Plenum Press | title = Complexity of Computer Computation | year = 1972}}.
4. ^{{citation | last1 = Khot | first1 = S. | author1-link = Subhash Khot | last2 = Kindler | first2 = G. | last3 = Mossel | first3 = E. | last4 = O’Donnell | first4 = R. | contribution = Optimal inapproximability results for MAX-CUT and other two-variable CSPs? | pages = 146–154 | title = Proceedings of the 45th IEEE Symposium on Foundations of Computer Science | contribution-url = http://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf | year = 2004}}.
5. ^{{citation | last1 = Goemans | first1 = M. X. | author1-link = Michel Goemans | last2 = Williamson | first2 = D. P. | author2-link = David P. Williamson | doi = 10.1145/227683.227684 | issue = 6 | journal = Journal of the ACM | pages = 1115–1145 | title = Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming | volume = 42 | year = 1995}}.
6. ^{{citation | last = Vazirani | first = Vijay V. | author-link = Vijay Vazirani | isbn = 3-540-65367-8 | pages = 97–98 | publisher = Springer | title = Approximation Algorithms | year = 2004}}.
7. ^{{citation | last1 = Arora | first1 = Sanjeev | author1-link = Sanjeev Arora | last2 = Rao | first2 = Satish | last3 = Vazirani | first3 = Umesh | author3-link = Umesh Vazirani | doi = 10.1145/1502793.1502794 | issue = 2 | journal = J. ACM | pages = 1–37 | publisher = ACM | title = Expander flows, geometric embeddings and graph partitioning | volume = 56 | year = 2009}}.
8. ^{{citation | last1 = Gross | first1 = Jonathan L. | last2 = Yellen | first2 = Jay | contribution = 4.6 Graphs and Vector Spaces | edition = 2nd | isbn = 9781584885054 | pages = 197–207 | publisher = CRC Press | title = Graph Theory and Its Applications | url = https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA197 | year = 2005}}.
9. ^{{citation | last = Diestel | first = Reinhard | contribution = 1.9 Some linear algebra | pages = 23–28 | publisher = Springer | series = Graduate Texts in Mathematics | title = Graph Theory | url = https://books.google.com/books?id=eZi8AAAAQBAJ&pg=PA23 | volume = 173 | year = 2012}}.
10. ^{{citation | last1 = Korte | first1 = B. H. | author1-link = Bernhard Korte | last2 = Vygen | first2 = Jens | contribution = 8.6 Gomory–Hu Trees | isbn = 978-3-540-71844-4 | pages = 180–186 | publisher = Springer | series = Algorithms and Combinatorics | title = Combinatorial Optimization: Theory and Algorithms | volume = 21 | year = 2008}}.