Results 1 to 3 of 3

Math Help - discrete math: graph theory

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    29

    discrete math: graph theory

    can plz help me with this question?
    Attached Thumbnails Attached Thumbnails discrete math: graph theory-3.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Dec 2008
    Posts
    105
    The answer is 4, the path followed is A-B-E-D.

    If it is the algorithm you do not understand then Iíll give you the steps (Steps applied to your diagram are in brackets).

    Step 1: Label the start vertex as 0 (so label A as 0).

    Step 2: Box this number (Box the 0, this is a permanent box).

    Step 3: Label each vertex that is connected to the start vertex with its distance (these may get crossed out as you find shorter routes so it is a temporary label) So B is 2 and F is 3 and D is 10.

    Step 4: Box the smallest number (The 2 connecting A and B should get boxed).

    Step 5: From this vertex, consider the distance to each connected vertex. (The path A-B- C overall is 8 so put an 8 above the C; however the distance from A-B-E is 3).

    Step 6: If this distance is less than a distance already at this vertex, cross out this distance and write in the new distance. If there was no distance at the vertex write down the new distance).

    Step 7: Repeat from step 4 until the destination vertex is boxed. (E-D is the shortest distance so the final path is ABED).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2008
    Posts
    29
    thanks for the help
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Discrete set theory.
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 24th 2011, 04:53 PM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  3. discrete math probability theory
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 25th 2010, 01:14 PM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. discrete math.proof.set theory.
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: January 13th 2010, 12:53 AM

Search Tags


/mathhelpforum @mathhelpforum