1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Network maths problem

  1. Mar 8, 2009 #1
    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.
  2. jcsd
  3. Mar 8, 2009 #2
    use graph theory.
  4. Mar 8, 2009 #3
    Ok, thanks.

    Anywhere online to get notes about graph theory....don't have any whatsoever!!
  5. Mar 8, 2009 #4
  6. Mar 10, 2009 #5
    Dijkstra's, a Euler Tour and a Minimal spanning tree (a.k.a) Kruskal's or Prim's algorithm.

    After a bit of research are these the 3 things I need for the 3 questions?
  7. Mar 10, 2009 #6
    try them. If they work, you chose right. Have confidence in your ability to solve this stuff.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Network maths problem
  1. A Math Problem (Replies: 14)

  2. Curvature math problem (Replies: 2)

  3. Financial math problem (Replies: 3)