Talk:Cut (graph theory)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Mid Importance
 Field: Discrete mathematics

questions[edit]

I believe that the definition at the top of the article should be amended to include something appropriate to directed graphs with weighted edges, where the value of the cut is not simply the sum of the weights of the edges crossing the cut but the sum of the weights of the edges leaving minus the sum of the weights entering. Of course, one must distinguish one half of the cut in order to define "leaving" vs. "entering." --Pqrstuv 05:08, 23 February 2007 (UTC)

No. Only the ones that go from source to sink. I've added it. --Spoon! 01:26, 9 March 2007 (UTC)

Does anyone know what the intended meaning of this sentence is ? It seems to have been truncated in someway. " The max-flow min-cut theorem proves that maximal network flow and the sum of the cut-edge weights of any minimal cut that separates the source and the sink."

They are equal. Thanks for your note; this is now fixed. -- Jitse Niesen (talk) 12:54, 15 May 2006 (UTC)

I don't understand this sentence: "There is a simple 0.5-randomized approximation algorithm, which is also the best purely combinatorial algorithm for maximal cuts." The next sentence claims you cannot get better than 0.8. Also, what is a "best" algorithm? And what would be a not purely combinatorial algorithm? A reference would be nice... --141.35.12.66 10:38, 19 December 2006 (UTC)

It seems to me that this sentence is not accurate: "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." It seems to me that the right-hand side of this equation should be the minimum capacity of an s-t cut, as described at Max-flow_min-cut_theorem#Statement. The sum of the cut-edge weights of any minimum cut that separates the source and the sink need not be the minimum capacity of an s-t cut: looking at the example at the top of the Max_flow article, we see that one minimum cut (as defined here i.e. by minimizing the number of edges) would consist of the set of edges coming out of s. However the sum of their capacities (6) is not the minimum capacity of an s-t cut (5) for that example.

To come at it from another angle, it appears that the term "minimum cut" is used in two different ways: minimizing the number of edges in the cut, and (in a flow network) minimizing the total capacity of the edges in the cut; and that the wrong one of these definitions is used in this sentence. However I'm not an expert in the area, so I'd appreciate confirmation.Huttarl (talk) 10:36, 19 October 2010 (UTC)

"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 same term is defined by the sum of the weights of the edges crossing the cut. [emphasis mine]" The same term here is ambiguous: does it refer to size or weight? I guess the latter, but it's not clear... maybe both? Down below in #Definition, it says "The size of a cut C = (S,T) is the number of edges [never the sum of weights?] in the cut-set. If the edges are weighted, the value of the cut is the sum of the weights." So value is the same as weight? at least if the edges are weighted? We have two sets of definitions, which partially overlap. Probably the terms "weight" and "value" should be explicitly compared side-by-side in one section so that the reader does not have to digest both sets of definitions and try to infer the relationship between those terms.Huttarl (talk) 10:47, 19 October 2010 (UTC)

Added "weight" of cut as synonymous with "value". Zaslav (talk) 19:17, 22 September 2013 (UTC)

Terminology and Notation[edit]

Regarding definition of "cut": The current version reads "A cut C = (S,T) is a partition V of a graph G = (V,E)". I don't think that "V" is a good name for the partition, given that it is the set of all vertices. How about using a "pi" instead? — Preceding unsigned comment added by 91.17.181.99 (talk) 14:27, 15 January 2012 (UTC)

I believe the term "cut" often means what is here called a "cut-set". I added that to the article. Zaslav (talk) 19:12, 22 September 2013 (UTC)


Technical[edit]