Re: on cut edges and bonds, graph theory

From	Daniel Bastos <dbastos@toledo.com>
Newsgroups	comp.programming, alt.algebra.help
Subject	Re: on cut edges and bonds, graph theory
Date	2017-09-19 16:21 -0300
Organization	Aioe.org NNTP Server
Message-ID	<86lgla3369.fsf@toledo.com> (permalink)
References	<86wp4w3sz5.fsf@toledo.com> <87shfjpzgs.fsf@bsb.me.uk>

Cross-posted to 2 groups.

Show all headers | View raw

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Daniel Bastos <dbastos@toledo.com> writes:
>
>> This is a question on the definition of cut edges, edge cuts and bonds
>> as given by section 2.2, page 27-29 of
>>
>>   ``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.
>>
>> I understand cut edges.  It's defined in page 27.
>>
>> Definition (cut edge).  A cut edge of G is an edge e such that 
>> w(G - e) > w(G), where w(G) means the number of components of G.
>>
>> It says e is a a cut edge if removing e from G yields more components
>> than we had before.  In other words, e is necessary to keep G with the
>> components it had.  (In particular, if G is connected, then e is
>> necessary to keep G connected.)
>>
>> No problem here.
>>
>> 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?

>> Does
>> it mean [S,S'] contains all possible (x,y) edges for x in S, y in S'?
>
> I'm worried by the phrasing simply because I wonder why you want to
> re-word the definition:
>
>   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'
>
> That sounds clear to me.  I think you mean the same when you talk about
> all possible edges for x in S and y in S' but I'm not 100% sure.

It's not actually all possible edges for x in S, y in S'.  It's only
those edges in E.  That's what I was missing.  Now I can get the S for
the bond in figure 2.4 (b).

>> 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)

Let S = {5, 7, 8} so that S̅ = {1, 2, 3, 4, 6}.  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)

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.

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.  

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?
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.

What is an edge cut?  Shouldn't it be edges that when removed cut off
the graph somewhere?

Thanks!

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