Talk:Cut (graph theory)

From Wikipedia, the free encyclopedia

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)