Path: csiph.com!aioe.org!.POSTED!not-for-mail From: Daniel Bastos Newsgroups: comp.programming,alt.algebra.help Subject: Re: on cut edges and bonds, graph theory Date: Tue, 19 Sep 2017 16:21:18 -0300 Organization: Aioe.org NNTP Server Lines: 112 Message-ID: <86lgla3369.fsf@toledo.com> References: <86wp4w3sz5.fsf@toledo.com> <87shfjpzgs.fsf@bsb.me.uk> NNTP-Posting-Host: 9g4OKWL8rqXIGMxUPIClDA.user.gioia.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Complaints-To: abuse@aioe.org User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (windows-nt) X-Notice: Filtered by postfilter v. 0.8.2 Cancel-Lock: sha1:gpTKYwUrFPR6Rc1hEz32iwB62uc= Xref: csiph.com comp.programming:8015 alt.algebra.help:5003 Ben Bacarisse writes: > Daniel Bastos writes: > >> This is a question on the definition of cut edges, edge cuts and bonds >> as given by section 2.2, page 27-29 of >> >> ``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. >> >> I understand cut edges. It's defined in page 27. >> >> Definition (cut edge). A cut edge of G is an edge e such that >> w(G - e) > w(G), where w(G) means the number of components of G. >> >> It says e is a a cut edge if removing e from G yields more components >> than we had before. In other words, e is necessary to keep G with the >> components it had. (In particular, if G is connected, then e is >> necessary to keep G connected.) >> >> No problem here. >> >> 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? >> Does >> it mean [S,S'] contains all possible (x,y) edges for x in S, y in S'? > > I'm worried by the phrasing simply because I wonder why you want to > re-word the definition: > > 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' > > That sounds clear to me. I think you mean the same when you talk about > all possible edges for x in S and y in S' but I'm not 100% sure. It's not actually all possible edges for x in S, y in S'. It's only those edges in E. That's what I was missing. Now I can get the S for the bond in figure 2.4 (b). >> 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) Let S = {5, 7, 8} so that S̅ = {1, 2, 3, 4, 6}. 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) 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. 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. 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? 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. What is an edge cut? Shouldn't it be edges that when removed cut off the graph somewhere? Thanks!