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

Groups > comp.programming > #8011 > unrolled thread

on cut edges and bonds, graph theory

Back to article view | Back to comp.programming

Contents

  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

Page 3 of 3 — ← Prev page 1 2 [3]

#8046

On 22/09/17 22:18, Ben Bacarisse wrote:
> David Brown <david.brown@hesbynett.no> writes:
> <snip>
>> Out of curiosity, how do you type the S̅?  Is it a combining macron or
>> something?
> 
> A macron is usually shorter: S̄.  It's a combining overline (U+0305).
> 
> I use Emacs as my Usenet client so I use that directly because it can
> auto-complete (and search) Unicode character names.  When I write the
> original, I was not sure what character was the right one (and I did
> indeed try a macron first!) so seeing all the completion options was
> very helpful.
> 

Like this: ̅S ?  I don't use Emacs (I never could feel comfortable with
it), so here I am stuck with ctrl+shift+u 0305 and the S.  I guess if I
needed it often, I could add it as a compose key or an Alt-Gr key.
Usually if I am writing maths, it will be in LaTeX anyway, rather than
Usenet posts.

But my son often has need of odd symbols, especially IPA symbols for
linguistics - I'll suggest he looks at Emacs as a possible convenient
way to enter these, as he is always interested in alternative methods.

[toc] | [prev] | [next] | [standalone]

#8048

David Brown <david.brown@hesbynett.no> writes:

[...]

> Like this: ̅S ?  I don't use Emacs (I never could feel comfortable with
> it), so here I am stuck with ctrl+shift+u 0305 and the S.

[...]

> But my son often has need of odd symbols, especially IPA symbols for
> linguistics - I'll suggest he looks at Emacs as a possible convenient
> way to enter these, as he is always interested in alternative methods.

EMACS is a fantastic software with a fantastic community at
gnu.emacs.help.  There are many books to teach you about EMACS as a
user, but since this is comp.programming, perhaps you could jump right
in a programming book.  ``Introduction to Emacs Lisp'' by Robert
Chassel, included in EMACS itself, will get you comfortable with EMACS.
(To be friends with EMACS I think knowing a little about Lisp is
required.)  Chassel himself recommends you to read the online tutorial
before, which you can bring up in EMACS by invoking the command

  help-with-tutorial

You can also invoke this command by saying

   C-h t

to EMACS.

 C-h t  means hold the CONTROL key while typing the character h,
        then release the CONTROL key and then type t.

[toc] | [prev] | [next] | [standalone]

#8049

On 25/09/17 12:31, Daniel Bastos wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
> [...]
> 
>> Like this: ̅S ?  I don't use Emacs (I never could feel comfortable with
>> it), so here I am stuck with ctrl+shift+u 0305 and the S.
> 
> [...]
> 
>> But my son often has need of odd symbols, especially IPA symbols for
>> linguistics - I'll suggest he looks at Emacs as a possible convenient
>> way to enter these, as he is always interested in alternative methods.
> 
> EMACS is a fantastic software with a fantastic community at
> gnu.emacs.help.  There are many books to teach you about EMACS as a
> user, but since this is comp.programming, perhaps you could jump right
> in a programming book.  ``Introduction to Emacs Lisp'' by Robert
> Chassel, included in EMACS itself, will get you comfortable with EMACS.
> (To be friends with EMACS I think knowing a little about Lisp is
> required.)  Chassel himself recommends you to read the online tutorial
> before, which you can bring up in EMACS by invoking the command
> 
>   help-with-tutorial
> 
> You can also invoke this command by saying
> 
>    C-h t
> 
> to EMACS.
> 
>  C-h t  means hold the CONTROL key while typing the character h,
>         then release the CONTROL key and then type t.
> 

I know Emacs is fantastic.  There are lots of fantastic things I don't
like, or have never felt comfortable with.  There isn't time in life to
learn to appreciate everything.  I am not an Emacs hater - I am just not
an Emacs liker.  (I don't like vim either.)

[toc] | [prev] | [next] | [standalone]

#8051

David Brown <david.brown@hesbynett.no> writes:

> On 22/09/17 22:18, Ben Bacarisse wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>> <snip>
>>> Out of curiosity, how do you type the S̅?  Is it a combining macron or
>>> something?
>> 
>> A macron is usually shorter: S̄.  It's a combining overline (U+0305).
>> 
>> I use Emacs as my Usenet client so I use that directly because it can
>> auto-complete (and search) Unicode character names.  When I write the
>> original, I was not sure what character was the right one (and I did
>> indeed try a macron first!) so seeing all the completion options was
>> very helpful.
>
> Like this: ̅S ?

Yes, except that combining marks go after the glyph they combine with.
Whether Emacs will show the actual combined symbol or not seems to
depend on the font being used.  Not sure why.  Maybe some fonts don't
include the right data.

> I don't use Emacs (I never could feel comfortable with
> it), so here I am stuck with ctrl+shift+u 0305 and the S.

That works fine, too.

> I guess if I
> needed it often, I could add it as a compose key or an Alt-Gr key.
> Usually if I am writing maths, it will be in LaTeX anyway, rather than
> Usenet posts.

Yup.  Having French and Spanish family I need few accents and so on,
but they are all compose sequences in this laptop.

> But my son often has need of odd symbols, especially IPA symbols for
> linguistics - I'll suggest he looks at Emacs as a possible convenient
> way to enter these, as he is always interested in alternative methods.

Emacs has a few IPA input methods so you can type symbols using plain
character sequences.  I don't know how easy they are to use for serious
work.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#8057

On 25/09/17 21:32, Ben Bacarisse wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
>> On 22/09/17 22:18, Ben Bacarisse wrote:
>>> David Brown <david.brown@hesbynett.no> writes:
>>> <snip>
>>>> Out of curiosity, how do you type the S̅?  Is it a combining macron or
>>>> something?
>>>
>>> A macron is usually shorter: S̄.  It's a combining overline (U+0305).
>>>
>>> I use Emacs as my Usenet client so I use that directly because it can
>>> auto-complete (and search) Unicode character names.  When I write the
>>> original, I was not sure what character was the right one (and I did
>>> indeed try a macron first!) so seeing all the completion options was
>>> very helpful.
>>
>> Like this: ̅S ?

> 
> Yes, except that combining marks go after the glyph they combine with.

Interesting - I did not realise there was a difference.  Putting the
combining mark first gives ̅S while putting it last gives S̅.  There is a
noticeable difference in these two glyphs (at least with the fonts I am
using) - putting the combing mark last sets its height to fit the S better.

> Whether Emacs will show the actual combined symbol or not seems to
> depend on the font being used.  Not sure why.  Maybe some fonts don't
> include the right data.
> 
>> I don't use Emacs (I never could feel comfortable with
>> it), so here I am stuck with ctrl+shift+u 0305 and the S.
> 
> That works fine, too.
> 
>> I guess if I
>> needed it often, I could add it as a compose key or an Alt-Gr key.
>> Usually if I am writing maths, it will be in LaTeX anyway, rather than
>> Usenet posts.
> 
> Yup.  Having French and Spanish family I need few accents and so on,
> but they are all compose sequences in this laptop.

With a Norwegian keyboard layout, keys like '`^"~ are all dead keys,
making it easy to type most common Western European accents or letters -
even with Windows.  On Linux there are a lot more on Alt-Gr sequences,
and then the compose key gives another level.

> 
>> But my son often has need of odd symbols, especially IPA symbols for
>> linguistics - I'll suggest he looks at Emacs as a possible convenient
>> way to enter these, as he is always interested in alternative methods.
> 
> Emacs has a few IPA input methods so you can type symbols using plain
> character sequences.  I don't know how easy they are to use for serious
> work.
> 

I will recommend he gives it a shot.  It all comes down to how much you
have to type the symbols.  I don't expect he types whole paragraphs in
IPA - and you have to type a lot before you get used to a new method.  I
believe he does most of his documents in Lyx, which has good toolbars
for IPA (by "good", I mean he finds the ordering and layout logical).
The TeX modes for Emacs could be an alternative.

[toc] | [prev] | [next] | [standalone]

#8061

David Brown <david.brown@hesbynett.no> writes:

> On 25/09/17 21:32, Ben Bacarisse wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>> 
>>> On 22/09/17 22:18, Ben Bacarisse wrote:
>>>> David Brown <david.brown@hesbynett.no> writes:
>>>> <snip>
>>>>> Out of curiosity, how do you type the S̅?  Is it a combining macron or
>>>>> something?
>>>>
>>>> A macron is usually shorter: S̄.  It's a combining overline (U+0305).
>>>>
>>>> I use Emacs as my Usenet client so I use that directly because it can
>>>> auto-complete (and search) Unicode character names.  When I write the
>>>> original, I was not sure what character was the right one (and I did
>>>> indeed try a macron first!) so seeing all the completion options was
>>>> very helpful.
>>>
>>> Like this: ̅S ?
>
>> Yes, except that combining marks go after the glyph they combine with.
>
> Interesting - I did not realise there was a difference.  Putting the
> combining mark first gives ̅S while putting it last gives S̅.  There is a
> noticeable difference in these two glyphs (at least with the fonts I am
> using) - putting the combing mark last sets its height to fit the S
> better.

Oh!  Not what I see.  Here, the first puts the overline on the space,
the second on the S.  I don't think the combining characters work very
well in most fonts and display systems.  I used this one only because I
was referring to a book that used that specific notation and there was a
chance the OP would see what I intended.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#8063

On 26/09/17 12:53, Ben Bacarisse wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
>> On 25/09/17 21:32, Ben Bacarisse wrote:
>>> David Brown <david.brown@hesbynett.no> writes:
>>>
>>>> On 22/09/17 22:18, Ben Bacarisse wrote:
>>>>> David Brown <david.brown@hesbynett.no> writes:
>>>>> <snip>
>>>>>> Out of curiosity, how do you type the S̅?  Is it a combining macron or
>>>>>> something?
>>>>>
>>>>> A macron is usually shorter: S̄.  It's a combining overline (U+0305).
>>>>>
>>>>> I use Emacs as my Usenet client so I use that directly because it can
>>>>> auto-complete (and search) Unicode character names.  When I write the
>>>>> original, I was not sure what character was the right one (and I did
>>>>> indeed try a macron first!) so seeing all the completion options was
>>>>> very helpful.
>>>>
>>>> Like this: ̅S ?
>>
>>> Yes, except that combining marks go after the glyph they combine with.
>>
>> Interesting - I did not realise there was a difference.  Putting the
>> combining mark first gives ̅S while putting it last gives S̅.  There is a
>> noticeable difference in these two glyphs (at least with the fonts I am
>> using) - putting the combing mark last sets its height to fit the S
>> better.
> 
> Oh!  Not what I see.  Here, the first puts the overline on the space,
> the second on the S.  I don't think the combining characters work very
> well in most fonts and display systems.  I used this one only because I
> was referring to a book that used that specific notation and there was a
> chance the OP would see what I intended.
> 

More interesting information.

On my system (an out-of-date Redhat Linux, with an old version of
Thunderbird) I see the first as an overline on top of an S.  When I type
the u0305, I get an overline to the right of the cursor.  I can then
type another character, such as S, which appears at the same spot.  But
clearly the position of the line and its width is not adjusted to give
an S with an overline - it looks more like a stand-alone overline
character with a zero logical width.  Perhaps your newsreader (or
unicode font) does not support zero logical widths like that?

Anyway, now I know that I must put my combining marks after the letter.
 I wouldn't want my posts to look bad for people with old-fashioned
newsreaders :-)

[toc] | [prev] | [next] | [standalone]

#8015

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!

[toc] | [prev] | [next] | [standalone]

#8018

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.

[toc] | [prev] | [next] | [standalone]

#8022

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

I numbered the vertices from 1 to 8 by going from left to right, then
top to bottom.  So the left-most vertice is 1, then to the right of
vertice 1 we have vertices 2, 3, 4 (going from top to bottom) and so on.

>> 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).  If you delete the thick lines of Fig 2.4 (b), you
disconnect the graph, getting two components, the right most component
being composed of 3 vertices --- {5 , 7, 8}.

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

Yes, I was describing the bond in Fig 2.4 (b), not the edge cut in (a).

The edge cut in (a) --- by by vertex labeling --- is 

  (2, 6) (2, 7) (3, 5) (3, 6) (4, 5) (4, 6) (4, 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.
>
> 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.  

I'm gonna comment on this below because the subject converges.

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

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.

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

Definition 2.  An edge cut of G is [S,S̅] where S is a nonempty proper
subset of V and S̅ = V - S.

Theorem.  If C is an edge cut of G, then 

  w(G) < w(G - C).

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.

That's what I think. :-)

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

I think a more general definition of bond was given before this quote.
That definition applies to all graphs.  A bond is a minimal edge cut.

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

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.

Here's an example.

Definition.  We call special the function f:Q-->Z such that 

   f(p/q) = p + q, 

where p/q satisfies gcd(p,q) = 1.

This definition implicitly claims f exists, but it doesn't.  So there's
no such special function.

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.

You did it above.

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.

Thanks very much!

[...]

[toc] | [prev] | [next] | [standalone]

#8024

Daniel Bastos <dbastos@toledo.com> writes:

[...]

> Here's an example.
>
> Definition.  We call special the function f:Q-->Z such that 
>
>    f(p/q) = p + q, 
>
> where p/q satisfies gcd(p,q) = 1.
>
> This definition implicitly claims f exists, but it doesn't.  So there's
> no such special function.

Sorry.  This function does exist.  The one that doesn't is the one
without the requirement gcd(p,q) = 1.

Definition.  We call special the function f:Q-->Z such that 

   f(p/q) = p + q, 

where p,q are integers.

[...]

[toc] | [prev] | [next] | [standalone]

#8026

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.

[toc] | [prev] | [next] | [standalone]

#8038

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.

[...]

[toc] | [prev] | [standalone]

Page 3 of 3 — ← Prev page 1 2 [3]

Back to top | Article view | comp.programming

csiph-web