Results 1 to 4 of 4

Math Help - Network Problem

  1. #1
    Newbie
    Joined
    Dec 2008
    Posts
    9

    Network Problem

    Have to do this question fairly soon in an exam. This is pretty much the exact same question that will be on it.

    What sort of maths is this and how the hell do I do it??!? I don't have any notes on it.
    -----------
    The following network (Figure 1 below) represents the road system in the town A-Town, with streets being edges and street junctions being vertices. The number on each street represents the length of the street in metres. Traffic can travel in either direction along any street: there are no one-way streets in the town.



    1. Use an appropriate algorithm to find, for each vertex, the shortest path (and its length) from vertex 1 to that vertex. Include workings with your solution.
    Draw the resulting shortest path spanning tree rooted at vertex 1.
    Which are the vertices in the shortest path between vertices 1 and 13?
    Discuss other examples of where a model/problem like this could arise.

    2. The Post Office is located at the junction marked 1 in Figure 1. Postman Pat is starting on his round. He wants to start from the Post Office, deliver the post along each street, and return to the Post Office at the end of the round. What tour should Pat take, and what is its length? Use an appropriate graph algorithm to find your answer. [Hint: your work in Question 1 will be useful here.]

    3. The A-Town town council wish to resurface certain streets in the town, so that it will be possible to get from any junction to any other junction using only the newly-resurfaced streets. Using an appropriate graph algorithm, find which streets should be resurfaced so as to minimise the total length of street resurfaced.
    --------------------------
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Dec 2008
    Posts
    9
    Just found some network mathematics notes online but they don't really help with the question above

    Anyone out there able to give me any hints or do a part of the question so I can better understand the question?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2008
    Posts
    9
    Are

    1) Dijkstra's

    2) Doing an Euler Tour

    3) Minimal spanning tree (a.k.a) Kruskal's or Prim's algorithm

    the 3 things I need to be able to do this question?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2008
    Posts
    394
    Quote Originally Posted by CheeseyChips View Post
    Are

    1) Dijkstra's

    2) Doing an Euler Tour

    3) Minimal spanning tree (a.k.a) Kruskal's or Prim's algorithm

    the 3 things I need to be able to do this question?

    Thanks.
    The standard method for the shortest path is

    Single-source shortest path: Greedy Algorithm (Dijkstra's ..)
    All-pairs shortest path: Dynamic Programming (Floyd-Warshall algorithm..)

    Hope this information is helpful.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Network Simplex Problem
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: December 12th 2011, 01:46 PM
  2. RC network
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 31st 2010, 04:03 AM
  3. bayesian network?
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: October 17th 2009, 10:57 AM
  4. RC Network
    Posted in the Discrete Math Forum
    Replies: 22
    Last Post: September 23rd 2006, 05:35 PM

Search Tags


/mathhelpforum @mathhelpforum