Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - Spanning Trees

  1. #1
    Member
    Joined
    Mar 2008
    Posts
    88

    Spanning Trees

    This proof was done in class and will be on the test on Friday but I just don't understand it. Can someone save me please. Thank you.

    1) Prove that if T1, T2 and T3 are spanning trees of a simple connected graph G then:
    d(T1, T3) <= d(T1, T2) + d(T2, T3):
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2008
    Posts
    88
    Im sorry but the : is not suppose to be there at the end
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by uniquereason81 View Post
    This proof was done in class and will be on the test on Friday but I just don't understand it. Can someone save me please. Thank you.

    1) Prove that if T1, T2 and T3 are spanning trees of a simple connected graph G then:
    d(T1, T3) <= d(T1, T2) + d(T2, T3):
    What do you mean by d(T_1, T_2)?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2008
    Posts
    88
    it is the distance between Tree 1 and Tree 2
    The formula for distance between two spanning trees is |E(T1)| + |E(T2)| -2|E(T1) [intersect] E(T2)|
    T1 ,T2 ,T3 are spanning trees of graph G
    Last edited by uniquereason81; November 5th 2010 at 04:36 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by uniquereason81 View Post
    it is the distance between Tree 1 and Tree 2
    The formula for distance between two spanning trees is |E(T1)| + |E(T2)| -2|E(T1) [intersect] E(T2)|
    T1 ,T2 ,T3 are spanning trees of graph G
    Well, plugging in the formula, this basically comes down to showing that for all sets S_1, S_2, S_3, we have

    |S_2| \geq |S_1 \cap S_2| + |S_2 \cap S_3| - |S_1 \cap S_3|

    Now, draw a Venn diagram to see what is happening, and complete...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Mar 2008
    Posts
    88
    Im sorry Swlabr I just don't follow how you derived that formula for that how is it showing the d(T1,T2)+d(T2,T3) is greater than or equal to d(T1,T3).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by uniquereason81 View Post
    Im sorry Swlabr I just don't follow how you derived that formula for that how is it showing the d(T1,T2)+d(T2,T3) is greater than or equal to d(T1,T3).
    Just take the formula for d(T_i, T_j), the formula you told me, and plug it into d(T_1,T_2)+d(T_2,T_3) \geq d(T_1,T_3). Cancel terms that are equal, and write S_i for E(T_i). That will then give you the formula I wrote.

    Then, just use Venn diagrams.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Mar 2008
    Posts
    88
    why and how would you use a venn diagram. i am sorry for being a pain but or teacher should us a different way
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by uniquereason81 View Post
    why and how would you use a venn diagram. i am sorry for being a pain but or teacher should us a different way
    Well, what way did your teacher teach you?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Mar 2008
    Posts
    88
    He did it without using the venn diagram. It was with words (if that makes any sense).

    But for the venn diagram which I think I'm understanding is it two shaded circles but the middle is not.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by uniquereason81 View Post
    He did it without using the venn diagram. It was with words (if that makes any sense).

    But for the venn diagram which I think I'm understanding is it two shaded circles but the middle is not.
    You end up with two disjoint subsets of S2 = E(T2) shaded, and so their cardinality will be less than or equal to that of S2.

    If you type up what your lecturer wrote, then I can have a look at it if you want?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Mar 2008
    Posts
    88
    His way is CRAAAAAAAAAAZY it took up a front of a page and half of the back.
    I rather learn your way which I can actually understand.

    So let me give this a shot
    The S_1,S_2,S_3 are basically the T_1,T_2,T_3.
    Then we get the formula you got.
    Next we plug that into a venn diagram
    Is this venn diagram containing three circles one for each S_i.
    Therefore the middle of S_1 S_2 will be shaded plus S_2 S_3
    This shows that S_2 must be greater than the other two.
    Is that the logic.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by uniquereason81 View Post
    His way is CRAAAAAAAAAAZY it took up a front of a page and half of the back.
    I rather learn your way which I can actually understand.

    So let me give this a shot
    The S_1,S_2,S_3 are basically the T_1,T_2,T_3.
    Then we get the formula you got.
    Next we plug that into a venn diagram
    Is this venn diagram containing three circles one for each S_i.
    Therefore the middle of S_1 S_2 will be shaded plus S_2 S_3
    This shows that S_2 must be greater than the other two.
    Is that the logic.
    Pretty much, although you have to note that you are taking away |S_1 \cap S_3|. This is important because with |S_1 \cap S_2|+|S_2 \cap S_3| you are essentially `shading' S_1 \cap S_2 \cap S_3 twice. However, the -|S_1 \cap S_3| gets rid of one of these shadings for you. Does that make sense?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Mar 2008
    Posts
    88
    Yes because the plus can means intersect.
    I think if my professor would have shown us that formula it would have been easier.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by uniquereason81 View Post
    Yes because the plus can means intersect.
    No...the plus `means' union...
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Spanning trees
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 26th 2011, 11:33 AM
  2. Spanning Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 9th 2011, 01:10 PM
  3. Spanning Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 27th 2010, 05:07 PM
  4. Spanning trees
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 27th 2010, 08:06 PM
  5. Spanning Trees
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 2nd 2009, 11:17 PM

Search Tags


/mathhelpforum @mathhelpforum