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-23 13:42 -0300
Organization	Aioe.org NNTP Server
Message-ID	<86377d9xiu.fsf@toledo.com> (permalink)
References	(1 earlier) <87shfjpzgs.fsf@bsb.me.uk> <86lgla3369.fsf@toledo.com> <87a81p723q.fsf@bsb.me.uk> <86y3p7dfju.fsf@toledo.com> <87bmm3daus.fsf@bsb.me.uk>

Cross-posted to 2 groups.

Show all headers | View raw

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

[...]

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

Yes!  Thanks!

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

Sounds good.

>> Theorem.  If C is an edge cut of G, then 
>>
>>   w(G) < w(G - C).
>
> OK, but that's not much of a theorem.

Agreed.

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

Agreed.

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

Agreed, but I understood exactly what you meant.

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

Precisely.

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

Agreed.

[...]

Back to comp.programming | Previous | Next — Previous 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