Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #8018
| 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-20 17:43 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <87a81p723q.fsf@bsb.me.uk> (permalink) |
| References | <86wp4w3sz5.fsf@toledo.com> <87shfjpzgs.fsf@bsb.me.uk> <86lgla3369.fsf@toledo.com> |
Cross-posted to 2 groups.
Daniel Bastos <dbastos@toledo.com> writes:
> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> Daniel Bastos <dbastos@toledo.com> writes:
about:
>>> ``Graph theory with applications'' by J.A. Bondy and U.S.R. Murty,
>>> Department of Combinatorics and Optimization, University of Waterloo,
>>> Ontario, Canada. North-Holland, fifth printing, 1982. ISBN:
>>> 0-444-19451-7.
>>>
<snip>
>>> On page 29, edge cuts are defined. (My writing.)
>>>
>>> Notation (separation). For subsets S and S' of V, we denote [S, S'] the
>>> set of edges with one end in S and the other in S'.
>>>
>>> Question. It seems [S, S'] is a separation of G into two parts.
>>
>> I don't know what a separation is, but this seems like an unlikely term.
>> For example [V, V] = E. Does your "(my writing)" mean the term
>> "separation" is your own?
>
> Yes. I think I messed that up. You're right, I can put in brackets any
> subset whatever. It's a separation (my wording) only when the
> complement is involved (when the overline is used.) The use of the
> complement does create some sort of separation among the vertices.
> Doesn't it?
Yup. The usual term (for a set, at least) is a partition.
<snip>
>>> 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.
> 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.
> 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?
> 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. 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!
> 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.
> 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.
> What is an edge cut? Shouldn't it be edges that when removed cut off
> the graph somewhere?
Yes, it does.
--
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