Talk:Cut (graph theory)

questions

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

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

Almost entirely off-topc
The following discussion has been closed. Please do not modify it.
SO, I need to quote this edit note: "this uses only very basic graph-theoretic terminology. If you don't understand even that much then you shouldn't be trying to read or judge mathematics article)" This is wildly off-mission. Very wrong-headed. As per policy: WP:NOT - particularly this section: "A Wikipedia article should not be presented on the assumption that the reader is well versed in the topic's field. Introductory language in the lead (and also maybe the initial sections) of the article should be written in plain terms and concepts that can be understood by any literate reader of Wikipedia without any knowledge in the given field before advancing to more detailed explanations of the topic. While wikilinks should be provided for advanced terms and concepts in that field, articles should be written on the assumption that the reader will not or cannot follow these links, instead attempting to infer their meaning from the text." The WP:TECHNICAL guideline goes into detail about what this means. Technical information doesn't need to be removed, but as I wrote in my edit note: "some improvement but this is still completely opaque and jargon driven. The body should have a comprehensible summary and that summary should be condensed in the lead. please see WP:TECHNICAL" really, that comment was way way off Wikipedia's mission, David Eppstein. Are you here to write an encyclopedia, or not? 22:51, 9 June 2014 (UTC) Your ad-hominem arguments about my attitude are a personal attack and are not acceptable here. As for WP:TECHNICAL, a Wikipedia article should be "presented in the most widely understandable manner possible". That does NOT mean that it should be accessible to all audiences. This is a perennial topic at WT:WPM as there is much important material in mathematics where the choice is to present material in a way that needs a certain level of preparedness or not to present it at all. My usual rule of thumb is that the start of an article, at least, should be readable at one major level of education below where it is primarily presented, and should then progress to cover all important aspects of the topic at the full level required.. A topic that is typically taught in secondary school should have a first section readable by all; a topic that is typically taught at the college level should have a first section readable by a high school graduate; a topic that is typically reserved to graduate school should have a first section readable by a college graduate; and a topic that is an active area of current research should have a first section readable by a graduate student in that general area. Your edits show no sensitivity to these distinctions and seem to take the position that we should only present material here that is accessible to all readers. That would leave us constructing an encyclopedia of Pokemons and celebrities rather than one that has any technical depth to it. Basically, I think you are grossly misunderstanding the purpose of the technical tag: it should not be for articles that you personally find hard to understand, but rather for articles that you do understand well enough to tell that the material is being presented at an unnecessarily high level. As such I don't think your opinion of the technicality of this article should carry much weight. —David Eppstein (talk) 01:13, 10 June 2014 (UTC) the comment "you shouldn't be trying to read... mathematics article" is reprehensible, from the point of view of WP's mission. I can't believe any decent editor would write that. If you strike that, I am willing to talk. With that, you are so far outside the boundaries of acceptable editing that I don't even know how to talk to you rationally. Jytdog (talk) 02:48, 10 June 2014 (UTC) what brought me here, by the way, was a reference I came across the use of graph cuts in post-processing of medical imaging. I wanted to get a better understanding of that, so I started with Graph cuts in computer vision which indeed says that it has "wide applicability in general computer vision problems." That article was also written by-experts-for-experts, so I kicked back a level to see if this article was less obscure, and found it more obscure. I have found and read other, more accessible explanations. It is far from impossible to do. As a professor you should be ashamed of yourself for being not able to provide a decent lay explanation of this and to actually insult someone ("Pokemon" my ass) who calls your attention to Wikipedia's policies on this. Un-be-liev-able. Jytdog (talk) 03:01, 10 June 2014 (UTC) I'm not striking anything, and there is neither any content nor any attempt to engage in your supposed response. This article is on a basic basic topic in graph theory and its lead is written using only even more basic topics (vertices and sets). Expanding those terms into their underlying definitions would make this harder to read, not easier. Come back when you have explicit constructive suggestions for what to do with the article rather than "I can't read it and I refuse to believe that the reason is my unwillingness to click the links and read about the preliminary concepts first". In the mean time I'm removing the technical tag again, because it accomplishes nothing towards improving the encyclopedia. —David Eppstein (talk) 03:33, 10 June 2014 (UTC) PS I had a look at some of the other material you edit. Let's compare Preimplantation genetic diagnosis, not because I want to pick on you but because I think you might understand my position a little better with a more familiar example. That article uses as undefined terms in its first sentence, that it expects readers to understand, jargon such as "genetic", "embryos", "implantation", "embryo profiling", "implantation", and "oocytes". Is it too technical because of this? Well maybe because of oocytes, but terms like "genetic" are things that (while still having a specific technical meaning) are things you would expect any reader to either understand already or recognize as something they should understand, read about, and come back to. You are complaining about the same level of basic terminology from a different field. It's not one you're already familiar with, I'm guessing, so things like "vertex" and "partition" look like scary jargon to you rather than like the right way to use simpler words to explain the topic of the article, just like "genetic" and "embryo" might look like scary jargon to someone ignorant of biology, but really these are simpler words and you should either understand them already or read about them and come back. Preferably with less of a chip on your shoulder. —David Eppstein (talk) 03:56, 10 June 2014 (UTC) I have barely edited that article. When people do engage me on articles I work on and ask for clarification, you know what I do? I listen to them and work with them. You are utterly resistant to hearing me. So I'm done. Take the tag off if you like. Your article is not a useful WP article, but you cannot hear that and instead consider me stupid. 100% typical university professor. Jytdog (talk) 04:37, 10 June 2014 (UTC) (striking comment I don't stand by Jytdog (talk) 05:32, 10 June 2014 (UTC)) I just want to re-iterate something. You, a wikipedia editor, and a professor at state university, actually wrote the words to someone interested in your field, that they shouldn't be trying to read an article in your field. SHOULD. NOT. TRY. That has got to be about as low as it gets with regard to the mission of WP and the mission of a publicly funded university. you. wrote. that. blows my mind. Jytdog (talk) 04:55, 10 June 2014 (UTC) You're still not being specific about what parts of this article you're stuck on. Care to at least try to explain why you think that, after my attempts earlier today at making it less technical, it's still not good enough? Or would you rather use this talk page to talk about how much respect and admiration you're entitled to here merely by virtue of someone else's day job? You are not a student in one of my classes; why should I have to treat you as if you were one? And if a student in one of my classes came in with the same attitude I'd suggest that perhaps they should try taking one of the prerequisite courses before this one. —David Eppstein (talk) 05:05, 10 June 2014 (UTC) I did not have "attitude" when I started, but I definitely reacted poorly to being told I SHOULD NOT TRY. What you wrote and your refusal to step away from it, is unforgivable for someone who does what you do both 'here at Wikipedia where you actually wrote it and in your classroom. You can see that, or not. Not taking more of my time with you. There is work to be done and people with their head on straight to work with. (I will work on the preimplantation diagnosis article, by the way - that one has been on my to-do list for a while. I think it is pretty sucky now too.) Jytdog (talk) 05:32, 10 June 2014 (UTC) And I undid the hat and your description of it, which was a dickish move on your part.Jytdog (talk) 05:36, 10 June 2014 (UTC) It had nothing to do with penises. It was an attempt to get the discussion BACK ONTO THE TOPIC OF HOW TO IMPROVE THE ARTICLE. A "technical" tag doesn't do much good if you refuse to explain it. —David Eppstein (talk) 05:49, 10 June 2014 (UTC) I was and remain willing to discuss the problems with the article. After my opening comment, I expected a response along the lines of "Wow, yes I see what you mean about my edit note. Sorry about that. What are the issues you see?" - and this would have been an entirely different exchange. The "don't be a dick" essay is about the downsides of acting like a dick -- the way it destroys any good you might do around here and prevents productive discussion. The reason this is off topic is due to your behavior. As I wrote above, you are so far outside the boundaries of acceptable editing that I don't even know how to talk to you rationally. You don't even seem to even be able to see how offensive SHOULD NOT TRY TO READ is. Shameful. In any case, thank you for the more neutral hatnote. Still not adult behavior, but less dickish.Jytdog (talk) 11:54, 10 June 2014 (UTC)

Cut space

This paragraph has the following sentence: "Each edge of this [Gomory-Hu] tree is associated with a bond in the original graph". Is it true? I thought edges of the Gomory-Hu tree do not have to be edges of the original graph. 91.114.252.65 (talk) 05:15, 4 August 2022 (UTC)

Associated with a bond is not the same as being an edge itself. —David Eppstein (talk) 05:30, 4 August 2022 (UTC)