Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #8026

Re: on cut edges and bonds, graph theory

Cross-posted to 2 groups.

Show key headers only | View raw

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

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