Practice Maths

Topic Review — Graphs and Networks

← Graphs and Networks

This review covers graph theory definitions, Euler trails and Hamiltonian paths, shortest path (Dijkstra’s algorithm), and minimum spanning trees.

Review Questions

  1. A graph has vertices A, B, C, D, E with edges AB, AC, BC, BD, CE, DE. Find the degree of each vertex and verify the Handshaking Lemma.
  2. For the graph in Question 1, does an Euler trail exist? An Euler circuit? A Hamiltonian path?
  3. A complete graph K5 has 5 vertices, each connected to every other. How many edges does it have? What is the degree of each vertex? Does an Euler circuit exist?
  4. Explain the difference between an Euler trail and a Hamiltonian path. Can a graph have one but not the other?
  5. A graph has 8 vertices with degrees: 2, 2, 2, 2, 3, 3, 4, 4. Does an Euler circuit exist? Does an Euler trail exist?
  6. Use Dijkstra’s algorithm to find the shortest path from A to E in the graph with edges: AB=5, AC=3, BC=4, BD=7, CD=2, DE=6, CE=10.
  7. A network of roads has edges: PQ=8, PR=4, QR=3, QS=9, RS=5, ST=7. Find the shortest path from P to T.
  8. What is a spanning tree? How many edges does a spanning tree of a graph with 9 vertices have?
  9. Use Kruskal’s algorithm to find the MST of: AB=6, AC=2, BD=4, BC=5, CD=3, DE=8, CE=7.
  10. Use Prim’s algorithm starting at vertex 1 to find the MST: 1–2=10, 1–3=6, 2–3=5, 2–4=15, 3–4=4, 4–5=8, 3–5=12.
  11. State the Euler conditions for a connected graph. A graph has 6 vertices with all degrees equal to 4. What type of Euler path exists?
  12. Explain the difference between a minimum spanning tree and a shortest path tree. When would you use each?
  13. A postman must deliver to every street in a neighbourhood. The streets form a graph where all vertices have even degree. Explain why the postman can plan a route that starts and ends at the same location without repeating any street.
  14. Find the shortest path from A to F and the minimum spanning tree for the graph: AB=3, AC=8, BC=2, BD=5, CD=4, CE=6, DF=7, EF=3. Comment on any difference between the two routes.
  15. A water pipe network connects 5 houses. The pipes already laid are: AE=20 m, BC=15 m, CD=10 m, DE=25 m. One more pipe must be laid to make the network connected. The remaining possible pipes and their costs are AB=18 m, AC=30 m, BD=22 m. Which pipe should be chosen to minimise total pipe length?
See Answers ➔
See Answers ➔