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: Thu, 21 Sep 2017 22:02:03 +0100 Organization: A noiseless patient Spider Lines: 119 Message-ID: <87bmm3daus.fsf@bsb.me.uk> References: <86wp4w3sz5.fsf@toledo.com> <87shfjpzgs.fsf@bsb.me.uk> <86lgla3369.fsf@toledo.com> <87a81p723q.fsf@bsb.me.uk> <86y3p7dfju.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="82804c28d500e09ff9d07e64dec1e385"; logging-data="18601"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19BhuvwWbHqeOuL1F8qQsivsmoOy+gVLp0=" Cancel-Lock: sha1:7ZU+uSpZXkdy86lijQmkAlQGakw= sha1:S/qCyTW70zsoMM0nrP36OHOM6xc= Xref: csiph.com comp.programming:8026 alt.algebra.help:5014 Daniel Bastos writes: > 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. >>> 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}. >> >> 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). Ah, right. I thought you might be. I did not note the (b) and thought you were still talking about (a). >>> 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. I've not read the book. I've just looked at the bits you've asked about! > 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'. (you meant [S, S']) > Definition 2. An edge cut of G is [S,S̅] where S is a nonempty proper > subset of V and S̅ = V - S. In fact I'd probably write [S, V\S] to keep it clear all the time. > Theorem. If C is an edge cut of G, then > > w(G) < w(G - C). OK, but that's not much of a theorem. > 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. Again, given the theorem above, this one is just one tiny step from it. >>> 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. This is too crude. I should have use something like [X, V\X] rather than use Y and leave it hanging that it's the complement. > 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. I don't follow. What is it whose existence you think must be established? I think, rather, that you want the name to be justified which seems to be something else to me. > 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. That's fine but many people hate that approach because it can be very long-winded. I don't want to push the point. Some people like lots of very exact steps, other people prefer a few leaps that keep them thinking. > 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. Ah yes. -- Ben.