Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse Newsgroups: comp.programming,alt.algebra.help Subject: Re: on cut edges and bonds, graph theory Date: Wed, 20 Sep 2017 17:43:05 +0100 Organization: A noiseless patient Spider Lines: 121 Message-ID: <87a81p723q.fsf@bsb.me.uk> References: <86wp4w3sz5.fsf@toledo.com> <87shfjpzgs.fsf@bsb.me.uk> <86lgla3369.fsf@toledo.com> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Injection-Info: reader02.eternal-september.org; posting-host="c18f41db8b21de350c4de23a11baeead"; logging-data="29801"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+W12X1IqEXzQFeWUpYy8+DcX5F0mL4GTU=" Cancel-Lock: sha1:OJZacAmuUiOQ0pU8hhU2aIXO5Qw= sha1:G6wRykj+X0bACzF1fVoPvjOSepM= Xref: csiph.com comp.programming:8018 alt.algebra.help:5006 Daniel Bastos writes: > Ben Bacarisse writes: > >> Daniel Bastos writes: about: >>> ``Graph theory with applications'' by J.A. Bondy and U.S.R. Murty, >>> Department of Combinatorics and Optimization, University of Waterloo, >>> Ontario, Canada. North-Holland, fifth printing, 1982. ISBN: >>> 0-444-19451-7. >>> >>> On page 29, edge cuts are defined. (My writing.) >>> >>> Notation (separation). For subsets S and S' of V, we denote [S, S'] the >>> set of edges with one end in S and the other in S'. >>> >>> Question. It seems [S, S'] is a separation of G into two parts. >> >> I don't know what a separation is, but this seems like an unlikely term. >> For example [V, V] = E. Does your "(my writing)" mean the term >> "separation" is your own? > > Yes. I think I messed that up. You're right, I can put in brackets any > subset whatever. It's a separation (my wording) only when the > complement is involved (when the overline is used.) The use of the > complement does create some sort of separation among the vertices. > Doesn't it? Yup. The usual term (for a set, at least) is a partition. >>> Although the book gave me Figure 2.4 (a), it didn't give me S and S', so >>> I'm not sure which vertices of the picture would be in S. >> >> An edge cut (such as that illustrated in Fig. 2.4 (a)) is a special case >> of [S, S'] where S' = V\S and S is a non-empty proper subset of V. The >> book uses an over bar for that case: [S, S̅]. >> >> For [A, B] to be an edge cut, A ∪ B = V, A ∩ B = {}, A =/= {} and B =/= >> {}. There's really no choice about what vertices are in the two sets >> for Fig. 2.4 (a). > > So here's my attempt at expliciting writing the S for figure 2.4 (b). > First number the vertices from left to right, top to bottom. We get > vertices 1, 2, 3, 4, 5, 6, 7, 8. From either (a) or (b), we know > > E = (1,2) (1,3) (1,4) (2,4) (2,6) (2,7) (3,5) > (3,6) (4,5) (4,6) (4,7) (5,7) (5,8) (7,8) That's the right number of edges and vertices but I'm not sure what your numbering is. > Let S = {5, 7, 8} so that S̅ = {1, 2, 3, 4, 6}. Just by looking at Fig 2.4 (a) you can see that there are 7 edges in the cut and, once cut, four vertices in each partition, so somthing has gone wrong. > Now the edges with one > end in S and the other end in S̅ must be in E. So we're interested in > edges involving 5, 7, or 8. But 8 is linked only with 5 and 7, so it > will not be a part of this bond and we reduce our search for edges > involving only 5 and 7. We find > > [S,S̅] = (4,5) (4,7) (3,5) (2,7) That may be the bond in Fig 2.4 (b) but it can't be the edge cut show in (a). Are you maybe confusing the two? > Now I have a question. > > Definition. An edge cut of G is a subset of E of the form [S, S̅], where > S is a nonempty proper subset of V and S̅ = V\S. (Page 29.) > > So I have an edge cut. Is it a bond? I'm unable to say. To which > property is [S,S̅] minimal? The definition of edge cut doesn't say. Not all edge cuts are bonds. I think that's the purpose of Fig 2.4. Part (a) is an edge cut but not a bone since there are smaller sets of edges that can be removed that result in a disconnected graph. Note that the resulting graphs are not the same. Removing the edge cut gives a four-vertex graph on the left and a four-vertex graph on the right. The one on the right is not itself connected. > A few more lines below, we find something more interesting. > > If G is connected, the a bond B of G is a minimal subset of E such > that G - B is disconnected. > > That sounds more like a theorem. It's definitely a definition! > In the case of figure 2.4, G is connected and so indeed I have a bond. > If I remove any edge from [S,S̅], then G - [S,S̅] is still connected. > Keeping all 4 edges in [S,S̅], G - [S,S̅] is disconnected. > > But what if G were not connected? How would I know I have a bond? Quote: "If G is connected, then a bond B of G is...". I don't think anyone cares about what it might mean for a disconnected graph. I'm sure you can generate some definition, but it really won't matter. > Something here is not clear to me. I expected the definition of edge > cut to say that removing the edge cut from the graph increases the > number of components. I expected some kind of property being > mentioned in the definition of edge cut. It's not necessary to say so because because [X, Y] contains all the edges of G that connect any vertex in X to any vertex in Y. Removing [X, Y] *must* leave G disconnected (or it's a trivial one-vertex graph). How could it not? That's why it's called a cut. > What is an edge cut? Shouldn't it be edges that when removed cut off > the graph somewhere? Yes, it does. -- Ben.