FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Recreational
Bipartition
Post new topic   Reply to topic Page 1 of 1 [5 Posts] View previous topic :: View next topic
Author Message
Brendan O'Sullivan
science forum beginner


Joined: 18 Jun 2005
Posts: 48

PostPosted: Sun Jun 19, 2005 3:16 pm    Post subject: Bipartition Reply with quote

I think I have a good grasp on vertices and edges now.

Let K_2,3 have bipartition B U W where B = {a,b}, W = {x_1, x_2, x_3}.

(a) Explain why, in a spanning tree of K_2,3, there must be precisely one of
the vertices x_i joined to both a and b.

(b) How many spanning trees does K_2,3 have?

(c) How many spanning trees does K_2,100 have?
Back to top
Brendan O'Sullivan
science forum beginner


Joined: 18 Jun 2005
Posts: 48

PostPosted: Sun Jun 19, 2005 8:37 pm    Post subject: Re: Bipartition Reply with quote

Quote:
Let K_2,3 have bipartition B U W where B = {a,b}, W = {x_1, x_2, x_3}.

(a) Explain why, in a spanning tree of K_2,3, there must be precisely one
of
the vertices x_i joined to both a and b.

Since you have a bipartition, no edges go from B to B, or form W to
W. If each vertex in W is connected ONLY to a OR to b, that allows you
to partition W into "those connected to a" and "those connected to
b". So, did you have a spanning tree then?
A typical spanning tree would be:

a x_1 b x_2 , there must be precisely one of
the vertices x_i joined to both a and b, as it is not possible for the tree
to be completed otherwise.



Quote:
(b) How many spanning trees does K_2,3 have?

Surely you can figure this one out explicitly. The idea, of course, is
to try to see a pattern in your counting, so that you can generalize
for the next question:
a x_1 b x_2

a x_2 b x_3
a x_1 b x_3
I get three for it, which corresponds to 3C2 = 3
Quote:
(c) How many spanning trees does K_2,100 have?

I would say the pattern would be 100 C2 = 4950

Thanks very much for your help, you are a wizard with the topic.
Back to top
Arturo Magidin
science forum Guru


Joined: 25 Mar 2005
Posts: 1838

PostPosted: Sun Jun 19, 2005 8:40 pm    Post subject: Re: Bipartition Reply with quote

In article <d949cm$f8f$1@reader01.news.esat.net>,
Brendan O'Sullivan <bos4@esatclear.ie> wrote:
Quote:
I think I have a good grasp on vertices and edges now.

Good. So these questions you are writing now, they are just
rhetorical, right? It's not like you are asking for help, since you
did not in fact ask for help. You just posted questions copied from
somewhere.

Quote:
Let K_2,3 have bipartition B U W where B = {a,b}, W = {x_1, x_2, x_3}.

(a) Explain why, in a spanning tree of K_2,3, there must be precisely one of
the vertices x_i joined to both a and b.

Since you have a bipartition, no edges go from B to B, or form W to
W. If each vertex in W is connected ONLY to a OR to b, that allows you
to partition W into "those connected to a" and "those connected to
b". So, did you have a spanning tree then?


Quote:
(b) How many spanning trees does K_2,3 have?

Surely you can figure this one out explicitly. The idea, of course, is
to try to see a pattern in your counting, so that you can generalize
for the next question:

Quote:
(c) How many spanning trees does K_2,100 have?

So... What have you done so far?

--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================

Arturo Magidin
magidin@math.berkeley.edu
Back to top
Brendan O'Sullivan
science forum beginner


Joined: 18 Jun 2005
Posts: 48

PostPosted: Mon Jun 20, 2005 3:14 pm    Post subject: Re: Bipartition Reply with quote

"Arturo Magidin" <magidin@math.berkeley.edu> wrote in message
news:d96t77$dm3$1@agate.berkeley.edu...
Quote:
In article <d94s6l$l1c$1@reader01.news.esat.net>,
Brendan O'Sullivan <bos4@esatclear.ie> wrote:


Let K_2,3 have bipartition B U W where B = {a,b}, W = {x_1, x_2, x_3}.

(a) Explain why, in a spanning tree of K_2,3, there must be precisely
one
of
the vertices x_i joined to both a and b.

Since you have a bipartition, no edges go from B to B, or form W to
W. If each vertex in W is connected ONLY to a OR to b, that allows you
to partition W into "those connected to a" and "those connected to
b". So, did you have a spanning tree then?

A typical spanning tree would be:
a x_1 b x_2 , there must be precisely one of
the vertices x_i joined to both a and b, as it is not possible for the
tree
to be completed otherwise.

Just asserting something is seldom a proof. Just repeating what you
are asked to prove with conviction is seldom convincing,
either. Saying something is "typical" doesn't prove anything. What if
there are "atypical" answers? What if your answer is not truly
"typical"? What proof do you have that every spanning tree will "look
like" what you have written down?

Without a satisfactory answer to all those questions, what you have is
not a proof, just bluster.

Why not complete what I wrote, or come up with some full proof of your
own?

Suppose you have a connected bipartite graph G, with two parts B and
W; |B|=2 and |W|=3. We want to prove that in a spanning tree for G,
there must be at least one vertex in W which is adjacent to both
vertices in B.

Given a spanning tree for W, we can divide W into three distinct sets:

W_a = { w in W : w is only adjacent to a in the tree}
W_b = { w in W : w is only adjacent to b in the tree}
W_{ab} = {w in W: w is adjacent to both a and b in the tree}

(since it is a spanning tree, you cannot have a w in W which is
adjacent to neither a nor b, because then it would be an isolated
point).

Since T is connected, there must be a path from a to b. From a you can
only go to a w in W_a or a w in W_{ab}. From a w in W_a you can only
go to a. So a path from a to b must start at a, go to a vertex in
W_{ab}, and then go to b; hence W_{ab} must be nonempty, as was to be
shown.


(b) How many spanning trees does K_2,3 have?

Surely you can figure this one out explicitly. The idea, of course, is
to try to see a pattern in your counting, so that you can generalize
for the next question:
a x_1 b x_2
a x_2 b x_3
a x_1 b x_3
I get three for it, which corresponds to 3C2 = 3

I'm not even sure what "a x_1 b x_2" is supposed to be. Not a spanning
tree, at any rate (where is x_3?)

There are plenty more than 3. You can have x_1 adjacent to
both a and b, and both x_2 and x_3 adjacent to b; or both adjacent to
a; or x_2 to a and x_3 to b; or x_2 to b and x_3 to a. That gives me
FOUR spanning trees already, and I haven't considered what happens if
the vertex adjacent to both a and b is x_2 instead of x_1.

Also: just because 3 happens to be equal to (3 choose 2) does not
necessarily mean that the correct answer will always be (n choose 2)
for K_{2,n}. How do you make trees correspond to ways of choosing two
out of 3? 3 is also equal to (3 choose 1), so why not (n choose 1) as
the general case?


Let's go back to the partition above. We have shown that W_{ab} must
have at least one element. I claim that it has at MOST one element.
For, supposw that w,w' are elements of W_{ab}. Then there is a path
from a to w, from w to b, from b to w', and from w' to a, giving a
cycle. This is impossible in a spanning tree, so W_{ab} must have at
most 1 element.

So, to construct a spanning tree, first we must choose the 1 element
in W_{ab}. The number of ways to make that choice is (3 choose 1).

Having chosen the one and only one vertex of W which will be adjacent
to both a and b, each of the remaining 2 vertices will be adjacent
to either a or b. They can be adjacent to either, and the choice is
completely free. So we have two possibilities for each of the 2
vertices, giving 2^{2} = 4 possibilities.

Thus, there are 4 spanning trees for EACH choice of which vertex in W
will be adjacent to both a and b, and there are 3 choices of which
vertex that will be. That gives me (3 choose 1)*2^2 = 12 spanning
trees.


(c) How many spanning trees does K_2,100 have?

I would say the pattern would be 100 C2 = 4950

You'd say wrong.

Again, as above, we can choose any ONE vertex in W (which this time
has 100 elements) to be adjacent to both a and b. After that choice,
the remaining 99 vertices can each be made adjacent to either a or b
(but not both). So, how many spanning trees does K_{2,100} have, then?

Thanks Arturo,
I think that will keep me busy for a while!
Brendan
Back to top
Arturo Magidin
science forum Guru


Joined: 25 Mar 2005
Posts: 1838

PostPosted: Mon Jun 20, 2005 5:08 pm    Post subject: Re: Bipartition Reply with quote

In article <d94s6l$l1c$1@reader01.news.esat.net>,
Brendan O'Sullivan <bos4@esatclear.ie> wrote:
Quote:


Let K_2,3 have bipartition B U W where B = {a,b}, W = {x_1, x_2, x_3}.

(a) Explain why, in a spanning tree of K_2,3, there must be precisely one
of
the vertices x_i joined to both a and b.

Since you have a bipartition, no edges go from B to B, or form W to
W. If each vertex in W is connected ONLY to a OR to b, that allows you
to partition W into "those connected to a" and "those connected to
b". So, did you have a spanning tree then?

A typical spanning tree would be:
a x_1 b x_2 , there must be precisely one of
the vertices x_i joined to both a and b, as it is not possible for the tree
to be completed otherwise.

Just asserting something is seldom a proof. Just repeating what you
are asked to prove with conviction is seldom convincing,
either. Saying something is "typical" doesn't prove anything. What if
there are "atypical" answers? What if your answer is not truly
"typical"? What proof do you have that every spanning tree will "look
like" what you have written down?

Without a satisfactory answer to all those questions, what you have is
not a proof, just bluster.

Why not complete what I wrote, or come up with some full proof of your
own?

Suppose you have a connected bipartite graph G, with two parts B and
W; |B|=2 and |W|=3. We want to prove that in a spanning tree for G,
there must be at least one vertex in W which is adjacent to both
vertices in B.

Given a spanning tree for W, we can divide W into three distinct sets:

W_a = { w in W : w is only adjacent to a in the tree}
W_b = { w in W : w is only adjacent to b in the tree}
W_{ab} = {w in W: w is adjacent to both a and b in the tree}

(since it is a spanning tree, you cannot have a w in W which is
adjacent to neither a nor b, because then it would be an isolated
point).

Since T is connected, there must be a path from a to b. From a you can
only go to a w in W_a or a w in W_{ab}. From a w in W_a you can only
go to a. So a path from a to b must start at a, go to a vertex in
W_{ab}, and then go to b; hence W_{ab} must be nonempty, as was to be
shown.


Quote:
(b) How many spanning trees does K_2,3 have?

Surely you can figure this one out explicitly. The idea, of course, is
to try to see a pattern in your counting, so that you can generalize
for the next question:
a x_1 b x_2
a x_2 b x_3
a x_1 b x_3
I get three for it, which corresponds to 3C2 = 3

I'm not even sure what "a x_1 b x_2" is supposed to be. Not a spanning
tree, at any rate (where is x_3?)

There are plenty more than 3. You can have x_1 adjacent to
both a and b, and both x_2 and x_3 adjacent to b; or both adjacent to
a; or x_2 to a and x_3 to b; or x_2 to b and x_3 to a. That gives me
FOUR spanning trees already, and I haven't considered what happens if
the vertex adjacent to both a and b is x_2 instead of x_1.

Also: just because 3 happens to be equal to (3 choose 2) does not
necessarily mean that the correct answer will always be (n choose 2)
for K_{2,n}. How do you make trees correspond to ways of choosing two
out of 3? 3 is also equal to (3 choose 1), so why not (n choose 1) as
the general case?


Let's go back to the partition above. We have shown that W_{ab} must
have at least one element. I claim that it has at MOST one element.
For, supposw that w,w' are elements of W_{ab}. Then there is a path
from a to w, from w to b, from b to w', and from w' to a, giving a
cycle. This is impossible in a spanning tree, so W_{ab} must have at
most 1 element.

So, to construct a spanning tree, first we must choose the 1 element
in W_{ab}. The number of ways to make that choice is (3 choose 1).

Having chosen the one and only one vertex of W which will be adjacent
to both a and b, each of the remaining 2 vertices will be adjacent
to either a or b. They can be adjacent to either, and the choice is
completely free. So we have two possibilities for each of the 2
vertices, giving 2^{2} = 4 possibilities.

Thus, there are 4 spanning trees for EACH choice of which vertex in W
will be adjacent to both a and b, and there are 3 choices of which
vertex that will be. That gives me (3 choose 1)*2^2 = 12 spanning
trees.


Quote:
(c) How many spanning trees does K_2,100 have?

I would say the pattern would be 100 C2 = 4950

You'd say wrong.

Again, as above, we can choose any ONE vertex in W (which this time
has 100 elements) to be adjacent to both a and b. After that choice,
the remaining 99 vertices can each be made adjacent to either a or b
(but not both). So, how many spanning trees does K_{2,100} have, then?



--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================

Arturo Magidin
magidin@math.berkeley.edu
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [5 Posts] View previous topic :: View next topic
The time now is Fri Nov 24, 2017 9:15 am | All times are GMT
Forum index » Science and Technology » Math » Recreational
Jump to:  


Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0925s ][ Queries: 11 (0.0607s) ][ GZIP on - Debug on ]