Results 1 to 5 of 5

Math Help - More Graph Questions

  1. #1
    Junior Member
    Joined
    Feb 2008
    Posts
    51

    More Graph Questions

    Thanks in advance!
    Attached Thumbnails Attached Thumbnails More Graph Questions-1.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    You do know, I hope, that these definitions are not unique or standard.
    So if we mean by a walk a sequence of alternating vertices and edges, beginning with a vertex and ending with a vertex, not necessarily the same.
    A path is a walk in which all edges are distinct.
    (Again these may not agree with your definitions)

    So is a star-like graph with n+1 vertices, 0 to n, both 010 and 102 are walks but only 102 is a path.

    Thus the number of walks of length two is {\binom {n} {2}} + n. WHY?
    But the number of paths of length two is {\binom {n} {2}}. WHY?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2008
    Posts
    51
    Quote Originally Posted by Plato View Post
    You do know, I hope, that these definitions are not unique or standard.
    So if we mean by a walk a sequence of alternating vertices and edges, beginning with a vertex and ending with a vertex, not necessarily the same.
    A path is a walk in which all edges are distinct.
    (Again these may not agree with your definitions)

    So is a star-like graph with n+1 vertices, 0 to n, both 010 and 102 are walks but only 102 is a path.

    Thus the number of walks of length two is {\binom {n} {2}} + n. WHY?
    But the number of paths of length two is {\binom {n} {2}}. WHY?
    Your interpretation is correct.

    The number of walks of length two is {\binom {n} {2}} + n because you either just choose two edges from n (all the paths) or you can walk from 0 to any vertex and back and there are n ways to do this.

    and the number of paths of length two is {\binom {n} {2}} because you just choose two edges from n and because they are all adjacent through 0 you have your path.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    Please do not use PM's to ask for more help!

    If n=4 then Adj = \left( {\begin{array}{*{20}c}   0 & 1 & 1 & 1 & 1  \\<br />
   1 & 0 & 1 & 1 & 1  \\   1 & 1 & 0 & 1 & 1  \\   1 & 1 & 1 & 0 & 1  \\<br />
   1 & 1 & 1 & 1 & 0  \\\end{array}} \right)

    \left( {Adj} \right)^2  = \left( {\begin{array}{*{20}c}<br />
   4 & 3 & 3 & 3 & 4  \\   3 & 4 & 3 & 3 & 4  \\   3 & 3 & 4 & 3 & 4  \\<br />
   3 & 3 & 3 & 4 & 4  \\   4 & 4 & 4 & 4 & 5  \\\end{array}} \right)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2008
    Posts
    51
    Quote Originally Posted by Plato View Post
    Please do not use PM's to ask for more help!

    If n=4 then Adj = \left( {\begin{array}{*{20}c} 0 & 1 & 1 & 1 & 1 \\<br />
1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 \\<br />
1 & 1 & 1 & 1 & 0 \\\end{array}} \right)

    \left( {Adj} \right)^2 = \left( {\begin{array}{*{20}c}<br />
4 & 3 & 3 & 3 & 4 \\ 3 & 4 & 3 & 3 & 4 \\ 3 & 3 & 4 & 3 & 4 \\<br />
3 & 3 & 3 & 4 & 4 \\ 4 & 4 & 4 & 4 & 5 \\\end{array}} \right)
    Thank you good sir, sorry about the PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with graph questions please
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 11th 2010, 07:46 PM
  2. Quick graph questions
    Posted in the Algebra Forum
    Replies: 9
    Last Post: August 13th 2009, 05:03 PM
  3. Graph theory questions
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 11th 2008, 12:37 PM
  4. Graph Theory Questions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 28th 2008, 03:46 PM
  5. Questions on Graph transformations
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 21st 2008, 08:21 PM

Search Tags


/mathhelpforum @mathhelpforum