Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups: comp.programming,alt.algebra.help
Subject: Re: on cut edges and bonds, graph theory
Date: Mon, 18 Sep 2017 20:40:35 +0100
Organization: A noiseless patient Spider
Lines: 60
Message-ID: <87shfjpzgs.fsf@bsb.me.uk>
References: <86wp4w3sz5.fsf@toledo.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="b9d8f780c97cbc8f39e2784dab48298d"; logging-data="27637"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+e5da5ACw8gBnrQNATKn5zTAeiRgKA7NU="
Cancel-Lock: sha1:MaDQrYGsq6kP7uEO0+4ARXnqDGM= sha1:OcIQNHiHtd9zFBqSjhhOuCIlt7w=
Xref: csiph.com comp.programming:8012 alt.algebra.help:5000

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?

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

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

> Thank you!

-- 
Ben.