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: Thu, 21 Sep 2017 16:20:37 -0300 Organization: Aioe.org NNTP Server Lines: 165 Message-ID: <86y3p7dfju.fsf@toledo.com> References: <86wp4w3sz5.fsf@toledo.com> <87shfjpzgs.fsf@bsb.me.uk> <86lgla3369.fsf@toledo.com> <87a81p723q.fsf@bsb.me.uk> NNTP-Posting-Host: +EftqNJlh2Q68VSRBVDe4Q.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:TIhqP8/E8irb8udYWWLtm1ENqsw= Xref: csiph.com comp.programming:8022 alt.algebra.help:5010 Ben Bacarisse writes: [...] >>>> 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. I numbered the vertices from 1 to 8 by going from left to right, then top to bottom. So the left-most vertice is 1, then to the right of vertice 1 we have vertices 2, 3, 4 (going from top to bottom) and so on. >> 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. You're looking at Fig 2.4 (a) and I described the edge cut (the bond) of Fig 2.4 (b). If you delete the thick lines of Fig 2.4 (b), you disconnect the graph, getting two components, the right most component being composed of 3 vertices --- {5 , 7, 8}. >> 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? Yes, I was describing the bond in Fig 2.4 (b), not the edge cut in (a). The edge cut in (a) --- by by vertex labeling --- is (2, 6) (2, 7) (3, 5) (3, 6) (4, 5) (4, 6) (4, 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. > > 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. I'm gonna comment on this below because the subject converges. > 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! I'm not enjoying what the book is doing. The definition of bond was given previously. A bond is a minimal edge cut. I think they redefine the word on the next phrase. Here's what I think the book should do. Definition 1. For subsets S and S' of V, [S,S̅] is the set of edges with one end in S and the other in S'. Definition 2. An edge cut of G is [S,S̅] where S is a nonempty proper subset of V and S̅ = V - S. Theorem. If C is an edge cut of G, then w(G) < w(G - C). Definition 3. A bond is a minimal edge cut. Theorem. If G is connected and B is a bond of G then G - B is disconnected. That's what I think. :-) >> 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. I think a more general definition of bond was given before this quote. That definition applies to all graphs. A bond is a minimal edge cut. >> 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. Here's my take on this. If a definition implicitly claims that something exists, one must prove that what the definition claims to exist does in fact exist. Here's an example. Definition. We call special the function f:Q-->Z such that f(p/q) = p + q, where p/q satisfies gcd(p,q) = 1. This definition implicitly claims f exists, but it doesn't. So there's no such special function. You might think I'm being unfair here, so let me clarify. We can tag any word whatever to mathematical objects as we like. We can call ``edge cut'' something that has nothing to do with edges or cuts. But if the mathematical object in question has a property which is not expressely in its definition, then it should be demonstrated that such objects do in fact have the property. So it's perfectly fine to define an edge cut as [S,S̅], but no matter how obvious it may be that it cuts off the graph, it should be demonstrated to do so. You did it above. By the way, the trivial graph offers no difficulty as it is implicitly excluded: S is required to be nonempty and proper; the only proper subset of {v} is {}, but S can't be empty. Thanks very much! [...]