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: Sat, 23 Sep 2017 13:42:49 -0300 Organization: Aioe.org NNTP Server Lines: 81 Message-ID: <86377d9xiu.fsf@toledo.com> References: <86wp4w3sz5.fsf@toledo.com> <87shfjpzgs.fsf@bsb.me.uk> <86lgla3369.fsf@toledo.com> <87a81p723q.fsf@bsb.me.uk> <86y3p7dfju.fsf@toledo.com> <87bmm3daus.fsf@bsb.me.uk> NNTP-Posting-Host: x/NSojQT0SEhetcSIZcbhQ.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) Cancel-Lock: sha1:Gpb19TATDG1C7kdp7ZocdcdK9Fo= X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com comp.programming:8038 alt.algebra.help:5024 Ben Bacarisse writes: [...] >> 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']) Yes! Thanks! >> 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. Sounds good. >> Theorem. If C is an edge cut of G, then >> >> w(G) < w(G - C). > > OK, but that's not much of a theorem. Agreed. >> 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. Agreed. >>>> 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. Agreed, but I understood exactly what you meant. >> 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. Precisely. >> 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. Agreed. [...]