Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #8022
| From | Daniel Bastos <dbastos@toledo.com> |
|---|---|
| Newsgroups | comp.programming, alt.algebra.help |
| Subject | Re: on cut edges and bonds, graph theory |
| Date | 2017-09-21 16:20 -0300 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <86y3p7dfju.fsf@toledo.com> (permalink) |
| References | <86wp4w3sz5.fsf@toledo.com> <87shfjpzgs.fsf@bsb.me.uk> <86lgla3369.fsf@toledo.com> <87a81p723q.fsf@bsb.me.uk> |
Cross-posted to 2 groups.
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.
>>>
>>> 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!
[...]
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