Menu
Sign up Sign in

AI HL · AHL 1

Graph Theory

0 of 43 skills done

0
AHL 1.13

Exam practice: the whole unit

AHL 1.13

Exam practice: the whole unit

Target: I can decide whether an Euler trail exists by counting vertices of odd degree, and give the reason. (+4 more)

By the end of this section

Key points

The parts of a long question

  • Euler trail: count the vertices of odd degree. Exactly 2 means a trail between two different vertices exists. More than 2 means it does not. Always give the number as your reason.
  • Table of shortest distances: check every pair. Use the table for nearest neighbour.
  • Nearest neighbour: go to the nearest unvisited vertex each time, then return to the start. The total is an upper bound.
  • Minimum spanning tree: Kruskal or Prim. List the edges and the total weight.

Lower bounds

  • Deleted vertex lower bound: MST of the rest plus the two shortest edges at the deleted vertex.
  • To improve a lower bound, delete a different vertex. The largest lower bound is best.
  • If each edge length is rounded to the nearest unit, each edge in the optimal route could be 0.5 shorter. Lower bound = route length − 0.5 × number of edges in the route.

Getting the marks

  • Method marks are for the algorithm: show the edges you add, the legs of the tour and each sum.
  • Write the final answer with its unit. Each part of a long question usually uses the part before it: use your own earlier answer if you are unsure.
  • Check: a lower bound must not be larger than an upper bound.

Worked examples

Problems like the ones in class. Pick one, try it, then open the working.
Can every road be used once?

The graph shows the roads, with lengths in km, between seven towns. Is it possible to make a journey that starts and finishes at different towns and uses each road exactly once? Give a reason.

52109381381310ABCDEFG
Working
  1. Degree of each town

    A 2, B 3, C 4, D 3, E 3, F 3, G 2

    The degree is the number of roads at the town.

  2. Count the odd ones

    Odd: B, D, E, F. That is 4.

    Count the towns with an odd degree.

  3. Decide

    No, it is not possible. There are 4 vertices of odd degree (B, D, E, F); a trail between two different towns needs exactly 2.

    A trail using every edge once between two different vertices exists only when exactly 2 vertices have odd degree. Always give the number as your reason.

Video walkthrough coming
Filling in the shortest distances

Use the graph to complete the table of shortest distances. Find the shortest distance between B and G.

52109381381310ABCDEFG
Working
  1. Pairs that need a route

    AD = 5 (route A-C-D); AE = 13 (route A-C-D-E); AF = 12 (route A-C-F); AG = 21 (route A-C-D-E-G); BC = 7 (route B-A-C); BE = 17 (route B-D-E); BF = 17 (route B-A-C-F); BG = 25 (route B-D-E-G); CE = 11 (route C-D-E); CG = 19 (route C-D-E-G); DF = 13 (route D-C-F); DG = 16 (route D-E-G)

    Try every route. The shortest one gives the table entry. A direct road that is longer than a detour does not count.

  2. Every other entry

    The table entry is the weight of the road.

    Check that no detour is shorter before you copy it.

  3. ABCDEFGA-525131221B5-79171725C27-3111019D593-81316E1317118-138F1217101313-13G21251916813-
    The table

    BG = 25

    The whole table is a complete graph on the seven towns.

Video walkthrough coming
Nearest neighbour upper bound

The table of shortest distances for the seven towns is shown. Use the nearest neighbour algorithm, starting at G, to find an upper bound for the travelling salesman problem.

ABCDEFGA-525131221B5-79171725C27-3111019D593-81316E1317118-138F1217101313-13G21251916813-
Working
  1. Go to the nearest unvisited town each time

    GE (8); ED (8); DC (3); CA (2); AB (5); BF (17)

    Start at G. From each town read the smallest entry in its row, ignoring towns already visited.

  2. Return to the start

    FG (13)

    The last town goes back to G. The table gives this distance.

  3. Add

    UB = 8 + 8 + 3 + 2 + 5 + 17 + 13 = 56

    Show the route and the sum for the method marks.

Video walkthrough coming
Spanning tree and lower bound

For the graph of the seven towns, sketch a minimum spanning tree for the subgraph with vertices A, B, C, D, E, F and write down its weight. Hence find a lower bound for the travelling salesman problem.

52109381381310ABCDEFG
Working
  1. Kruskal on the subgraph

    AC (2), CD (3), AB (5), DE (8), BD (9) skipped, BC (10) skipped, CF (10)

    Leave out G and its roads. Add the shortest edge each time and skip any that makes a cycle.

  2. 52109381310ABCDEF
    Sketch and weight

    Tree: AC (2), CD (3), AB (5), DE (8), CF (10). Weight = 2 + 3 + 5 + 8 + 10 = 28

    Draw the tree. Show every edge.

  3. Add the two shortest roads at the deleted town

    GE (8), GF (13)

    Town G has only these two roads.

  4. Lower bound

    LB = 28 + 8 + 13 = 49

    The shortest tour cannot be shorter.

Video walkthrough coming
A better bound, and rounded roads

(a) Explain one way in which a better lower bound could be found. (b) The optimum solution starting at G is G-F-C-A-B-D-E-G, of length 55 km. Each road length is given to the nearest km. Find the lower bound for the total distance in the optimal solution.

52109381381310ABCDEFG
Working
  1. A better lower bound

    Delete a different vertex and repeat; take the largest bound.

    Each vertex gives a lower bound. The best one is the largest. This is how you answer (a).

  2. Count the roads

    G-F-C-A-B-D-E-G uses 7 roads

    Count the roads in the route, not the towns.

  3. Allow for rounding

    Each road is at least 0.5 km less than its stated length: 55 − 7 × 0.5

    A road shown as 8 km could be as short as 7.5 km.

  4. Answer

    Lower bound = 51.5 km

    Show the multiplication for the method mark.

Video walkthrough coming