Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #8026
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.programming, alt.algebra.help |
| Subject | Re: on cut edges and bonds, graph theory |
| Date | 2017-09-21 22:02 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <87bmm3daus.fsf@bsb.me.uk> (permalink) |
| References | <86wp4w3sz5.fsf@toledo.com> <87shfjpzgs.fsf@bsb.me.uk> <86lgla3369.fsf@toledo.com> <87a81p723q.fsf@bsb.me.uk> <86y3p7dfju.fsf@toledo.com> |
Cross-posted to 2 groups.
Daniel Bastos <dbastos@toledo.com> writes:
> Ben Bacarisse <ben.usenet@bsb.me.uk> 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.
<snip>
>>> 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)
>>
<snip>
>>> 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).
<snip>
>>> 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.
<snip>
>>> 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.
<snip>
> 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.
<snip>
> 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.
Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
on cut edges and bonds, graph theory Daniel Bastos <dbastos@toledo.com> - 2017-09-18 12:51 -0300
Re: on cut edges and bonds, graph theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-18 20:40 +0100
Re: on cut edges and bonds, graph theory William Elliot <marsh@panix.com> - 2017-09-18 21:39 -0700
Re: on cut edges and bonds, graph theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-19 13:05 +0100
Re: on cut edges and bonds, graph theory William Elliot <marsh@panix.com> - 2017-09-19 19:47 -0700
Re: on cut edges and bonds, graph theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-20 14:28 +0100
Re: on cut edges and bonds, graph theory William Elliot <marsh@panix.com> - 2017-09-20 21:06 -0700
Re: on cut edges and bonds, graph theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-21 17:03 +0100
Re: on cut edges and bonds, graph theory Daniel Bastos <dbastos@toledo.com> - 2017-09-21 15:06 -0300
Re: on cut edges and bonds, graph theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-21 21:24 +0100
Re: on cut edges and bonds, graph theory Daniel Bastos <dbastos@toledo.com> - 2017-09-21 17:57 -0300
Re: on cut edges and bonds, graph theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-21 23:40 +0100
Re: on cut edges and bonds, graph theory William Elliot <marsh@panix.com> - 2017-09-21 20:45 -0700
Re: on cut edges and bonds, graph theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-23 02:27 +0100
Re: on cut edges and bonds, graph theory William Elliot <marsh@panix.com> - 2017-09-22 19:49 -0700
Re: on cut edges and bonds, graph theory Richard Heathfield <rjh@cpax.org.uk> - 2017-09-23 08:04 +0100
Re: on cut edges and bonds, graph theory Daniel Bastos <dbastos@toledo.com> - 2017-09-23 08:41 -0300
Re: on cut edges and bonds, graph theory Paul N <gw7rib@aol.com> - 2017-09-24 14:00 -0700
Re: on cut edges and bonds, graph theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-23 14:50 +0100
Re: on cut edges and bonds, graph theory William Elliot <marsh@panix.com> - 2017-09-23 22:04 -0700
Re: on cut edges and bonds, graph theory Richard Heathfield <rjh@cpax.org.uk> - 2017-09-24 07:39 +0100
Re: on cut edges and bonds, graph theory William Elliot <marsh@panix.com> - 2017-09-25 01:13 -0700
Re: on cut edges and bonds, graph theory Richard Heathfield <rjh@cpax.org.uk> - 2017-09-25 09:46 +0100
Re: on cut edges and bonds, graph theory William Elliot <marsh@panix.com> - 2017-09-25 21:38 -0700
Re: on cut edges and bonds, graph theory Richard Heathfield <rjh@cpax.org.uk> - 2017-09-26 10:19 +0100
Modern Trash William Elliot <marsh@panix.com> - 2017-09-26 03:37 -0700
Re: Modern Trash David Brown <david.brown@hesbynett.no> - 2017-09-26 12:52 +0200
Re: Modern Trash Richard Heathfield <rjh@cpax.org.uk> - 2017-09-26 23:10 +0100
Re: on cut edges and bonds, graph theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-24 22:33 +0100
Re: on cut edges and bonds, graph theory William Elliot <marsh@panix.com> - 2017-09-25 01:08 -0700
Re: on cut edges and bonds, graph theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-25 20:44 +0100
Re: on cut edges and bonds, graph theory William Elliot <marsh@panix.com> - 2017-09-25 21:36 -0700
Re: on cut edges and bonds, graph theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-26 12:04 +0100
Re: on cut edges and bonds, graph theory William Elliot <marsh@panix.com> - 2017-09-26 23:15 -0700
Re: on cut edges and bonds, graph theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-27 12:52 +0100
Re: on cut edges and bonds, graph theory William Elliot <marsh@panix.com> - 2017-09-27 19:55 -0700
Re: on cut edges and bonds, graph theory Ike Naar <ike@iceland.freeshell.org> - 2017-09-24 16:55 +0000
Re: on cut edges and bonds, graph theory David Brown <david.brown@hesbynett.no> - 2017-09-22 10:23 +0200
Re: on cut edges and bonds, graph theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-22 21:18 +0100
Re: on cut edges and bonds, graph theory Daniel Bastos <dbastos@toledo.com> - 2017-09-23 08:48 -0300
Re: on cut edges and bonds, graph theory David Brown <david.brown@hesbynett.no> - 2017-09-25 10:17 +0200
Re: on cut edges and bonds, graph theory Daniel Bastos <dbastos@toledo.com> - 2017-09-25 07:31 -0300
Re: on cut edges and bonds, graph theory David Brown <david.brown@hesbynett.no> - 2017-09-25 13:30 +0200
Re: on cut edges and bonds, graph theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-25 20:32 +0100
Re: on cut edges and bonds, graph theory David Brown <david.brown@hesbynett.no> - 2017-09-26 10:12 +0200
Re: on cut edges and bonds, graph theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-26 11:53 +0100
Re: on cut edges and bonds, graph theory David Brown <david.brown@hesbynett.no> - 2017-09-26 13:24 +0200
Re: on cut edges and bonds, graph theory Daniel Bastos <dbastos@toledo.com> - 2017-09-19 16:21 -0300
Re: on cut edges and bonds, graph theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-20 17:43 +0100
Re: on cut edges and bonds, graph theory Daniel Bastos <dbastos@toledo.com> - 2017-09-21 16:20 -0300
Re: on cut edges and bonds, graph theory Daniel Bastos <dbastos@toledo.com> - 2017-09-21 17:52 -0300
Re: on cut edges and bonds, graph theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-21 22:02 +0100
Re: on cut edges and bonds, graph theory Daniel Bastos <dbastos@toledo.com> - 2017-09-23 13:42 -0300
csiph-web