Graph Theory (DP IB Maths: AI HL)

Exam Questions

3 hours26 questions
1a
Sme Calculator
3 marks

Let G be an unweighted graph with 5 vertices. The adjacency matrix of G is shown below.

 

A

B

C

D

E

A

0

1

0

0

1

B

1

0

2

0

2

C

0

2

0

1

1

D

0

0

1

2

1

E

1

2

1

1

0

Draw the graph of G.

1b
Sme Calculator
4 marks
(i)
Define an Eulerian trail.

(ii)
From which vertices in graph G must an Eulerian trail start and finish.  Give a reason for your answer.

(iii)
Write down an Eulerian trail in G.

Did this page help you?

2a
Sme Calculator
1 mark

The graph G shown below is a strongly connected, unweighted, directed graph with 5 vertices.

q2

Explain why the graph is considered to be strongly connected.

2b
Sme Calculator
3 marks

Write down the adjacency matrix bold italic M for the graph G.

2c
Sme Calculator
2 marks

Find the total number of walks of length 5 that both start and finish at vertex straight A.

2d
Sme Calculator
1 mark

Write down a possible walk of length 5 that starts and finishes at vertex straight A.

Did this page help you?

3a
Sme Calculator
2 marks

Consider the weighted graph G below.

q3

(i)
Define a Hamiltonian cycle.

(ii)
Write down a Hamiltonian cycle starting from vertex straight A.
3b
Sme Calculator
3 marks

Use Kruskal’s algorithm to find the minimum spanning tree. Show each step of the algorithm clearly.

3c
Sme Calculator
1 mark

State the total weight of the minimum spanning tree.

Did this page help you?

4a
Sme Calculator
5 marks

Celeste is building a model city incorporating 6 main buildings that need to be connected to an electrical supply.

Each vertex listed in the table below represents a building and the weighting of each edge is the cost in USD of creating a link to the electrical supply between the given vertices.

 

A

B

C

D

E

F

A

-

4

9

8

11

3

B

4

-

13

2

5

12

C

9

13

-

7

1

4

D

8

2

7

-

10

3

E

11

5

1

10

-

15

F

3

12

4

3

15

-

 

Celeste wants to find the lowest cost solution that links all 6 buildings up to the electricity supply.

Starting from vertex straight A, use Prim’s algorithm on the table to find and draw the minimum spanning tree. Show each step of the process clearly.
4b
Sme Calculator
1 mark
State the lowest cost of connecting all of the buildings to the electricity supply.

Did this page help you?

5a
Sme Calculator
3 marks

5 scientists each have their own laboratory, and each laboratory is connected to other laboratories by a series of doors.  Some of the doors can only be opened from one side.  The table below lists which other laboratories can be accessed from the laboratory in the heading.

Anne’s lab

Bilal’s lab

Cariad’s lab

Diego’s lab

Ebele’s lab

Cariad

Anne

Anne

Anne

Anne

 

Cariad

 

Bilal

Cariad

 

Diego

 

Ebele

Diego

 

Ebele

 

 

 

Show the information from the table in a directed graph.

5b
Sme Calculator
2 marks

Show that it is possible to move through the laboratories visiting each laboratory exactly once, and write down a viable path.

5c
Sme Calculator
2 marks

Comment on any restrictions that determine the start and finish points of a path that visits each laboratory exactly once.

Did this page help you?

6a
Sme Calculator
3 marks

Let G be the graph below.

q5

Construct the transition matrix for a random walk around G.

6b
Sme Calculator
2 marks

Determine the probability that a random walk of length 3 starting at straight A will finish at straight C.

6c
Sme Calculator
2 marks
(i)
Find the steady state probabilities for the graph.

(ii)
Hence rank the vertices in terms of importance from highest to lowest.

Did this page help you?

7a
Sme Calculator
2 marks

The graph G below shows 7 towns and the train tracks that connect them, with the vertices representing the towns and the weighting of each edge indicating the time taken in minutes to walk along the section of track.

q7

State the degree of each vertex.

7b
Sme Calculator
1 mark

Explain why G does not contain an Eulerian circuit.

7c
Sme Calculator
4 marks

The railway company in charge of maintaining the track wishes to inspect all sections of the track for defects after a storm event.

Find the minimum time it would take for a railway worker who was walking to inspect all of the track.

Did this page help you?

8a
Sme Calculator
1 mark

The graph below contains 6 vertices representing villages and their connecting bus routes. The weighting indicates the cost of each bus route in AUD.

q8

Explain why G is not a complete graph.

8b
Sme Calculator
4 marks

Complete the table of least weights below.

 

A

B

C

D

E

F

A

-

 

 

 

 

 

B

4

-

 

 

 

 

C

6

8

-

 

 

 

D

 

9

9

-

 

 

E

 

 

10

15

-

 

F

2

5

7

9

4

-

 

8c
Sme Calculator
5 marks

Starting at town straight A, use the nearest neighbour algorithm to find an upper bound for the cost of a journey that will visit each vertex and return to straight A. Be sure to include the precise route of the upper bound journey.

Did this page help you?

9a
Sme Calculator
3 marks

The table of least weight for a graph G of 5 vertices is shown below.  Each vertex listed in the table represents a room in an art gallery and the weighting of the graph denotes the distance in metres between the rooms.

 

A

B

C

D

E

A

-

15

22

18

25

B

15

-

13

17

24

C

22

13

-

30

12

D

18

17

30

-

21

E

25

24

12

21

-

Draw the graph G.

9b
Sme Calculator
4 marks

By deleting vertex straight E and using Prim’s algorithm, find a lower bound for the distance walked to visit every room in the art gallery. Show each step of the process clearly.

9c2 marks

Show that by deleting a different vertex a lower bound can be found that is higher than the one found in part (b).

Did this page help you?

1a
Sme Calculator
1 mark

Let G be a graph with 5 vertices. The adjacency matrix of G is shown below. 

 

A

B

C

D

E

A

0

1

1

1

0

B

1

0

1

0

0

C

0

1

0

1

0

D

1

0

0

0

1

E

1

0

0

0

1

Explain what the fact that the adjacency matrix is not symmetrical about the leading diagonal means with respect to the associated graph.

1b
Sme Calculator
3 marks

Draw the graph of G.

1c
Sme Calculator
2 marks

Determine whether G  is Eulerian, semi-Eulerian or neither.  Justify your answer.

Did this page help you?

2a
Sme Calculator
3 marks

Consider the graph G shown below.

mi_q2a_3-10_graph-theory_hard_ib_ai_hl_maths_dig

Write down the adjacency matrix for the graph G.

2b
Sme Calculator
2 marks

Find the total number of walks of length 7 that start at vertex A and finish at vertex D.

2c
Sme Calculator
2 marks

Find the total number of walks of length 7 that start at vertex D and finish at vertex A. Explain any difference found between this result and the value found in part (b).

Did this page help you?

3a
Sme Calculator
1 mark

Let G be the graph shown below.  In the graph the vertices represent different clinics in a hospital and the edges represent the possible locations for pipelines to supply oxygen to the clinics. The weighting of the edges represents the cost, in hundreds of US dollars, of installing each pipe.

mi_q3a_3-10_graph-theory_hard_ib_ai_hl_maths_dig

Show that G is a Hamiltonian graph.

3b
Sme Calculator
4 marks

Using Kruskal’s algorithm, find the minimum cost of a network that will connect each clinic to the oxygen supply.

 

Did this page help you?

4a
Sme Calculator
5 marks

The musical elves who live in the magical land of Fooditooti want to build a network of rainbow bridges to connect the different cities in the land, and they wish to do so in such a way as to minimise the total length of the bridges that they need to build.

The graph G below shows  a schematic map of Fooditooti, along with its 6 cities: Pineapple Skies, Strawberry Fields, Marshmallow World, Sugar Mountain, Blueberry Hill and Mango Tree. The weighting of the edges between the cities represents the length in kilometres of the rainbow bridge that would be required to connect the two cities.

mi_q4a_3-10_graph-theory_hard_ib_ai_hl_maths_dig

Starting from Pineapple Skies and using Prim’s algorithm, find a network of bridges of minimum total length that will span the whole land.

4b
Sme Calculator
2 marks

Given that rainbow bricks are sold in bundles, with each bundle costing $15 and containing enough bricks to build 42 centimetres of rainbow bridge, find the total cost of constructing the network from part (a).

Did this page help you?

5a
Sme Calculator
3 marks

On Monday Dinesh has 5 lessons to attend: English, Biology, French, Maths and Art.  His lessons all take place in the different departments in his school, which are connected by a number of corridors.  Some of the corridors are narrow so students are only allowed to walk in one direction along them. 

From the Biology department, there are corridors that lead to the English, French and Maths departments. 

The Maths department is also connected to the Art department and the French department, but students are not allowed to access the Maths department from the French department. 

The English department has corridors connecting it to the French department and the Art department, although students cannot walk back through the corridor from the Art department to the English department. 

Construct a graph showing how the classrooms are connected.

5b
Sme Calculator
1 mark

Write down a possible path starting from and finishing at the Maths department that Dinesh could take to visit each of the departments without using the same corridor more than once.

5c
Sme Calculator
2 marks

Given that the timetable requires Dinesh to go to his lessons in the order initially stated, write down the route that he should take to minimise the number of corridors that he must walk down more than once.

Did this page help you?

6a
Sme Calculator
1 mark

Consider the graph G below.

mi_q6a_3-10_graph-theory_hard_ib_ai_hl_maths_dig

For a random walk through graph G, explain why the long-term probabilities will be dependent on the starting position.

6b
Sme Calculator
6 marks

Find the probability of a random walk finishing at vertex C given that the starting position is at vertex F.

Did this page help you?

7a
Sme Calculator
1 mark

The graph P, shown below, represents the layout of a sculpture park with each vertex representing the position of a sculpture and the edges representing the pathways between the sculptures. The weighting of each edge indicates the length of the corresponding pathway in metres.

mi_q7a_3-10_graph-theory_hard_ib_ai_hl_maths_dig

A treasure hunt has been set up for visitors with different tokens to collect hidden along the pathways.

State with a reason whether P  contains an Eulerian circuit.

 

7b
Sme Calculator
7 marks

Given that a visitor must start and finish at the same sculpture, find the minimum distance that a visitor must travel in order to walk along each edge at least once in order to find all the tokens. State clearly which edges must be repeated.

 

Did this page help you?

8a
Sme Calculator
2 marks

In the graph below each vertex represents a place of interest in a museum, with the weighted edges representing the pathways connecting the places of interest and their lengths in metres. Vertices A and E represent the entrance hall and the souvenir shop, respectively.

mi_q8a_3-10_graph-theory_hard_ib_ai_hl_maths_dig

Other than possibly starting and finishing at the same location, Elijah wishes to visit each place of interest once and only once during his visit.   

Using the graph above, write down a possible route for Elijah

(i)
starting at the entrance hall and finishing at the souvenir shop
(ii)
starting and finishing at the souvenir shop.

 

8b
Sme Calculator
1 mark

Explain why there must be fewer than 24 possible routes meeting Elijah’s criteria that start and finish from the same vertex in the graph.

8c
Sme Calculator
4 marks

By inspection, find the shortest distance that Elijah will need to travel given that he must start and finish at the entrance hall. State the route that he should take.

Did this page help you?

9a
Sme Calculator
2 marks

In order to distribute food for the animals in the wildlife park that she runs, Jessamy needs to visit each of the enclosures A comma space B comma space C comma space D and E .  She starts at enclosure  as this is where the feed is stored, then visits each enclosure once and returns to  to put back the feeding equipment.  As this is a task that must be repeated twice a day, Jessamy wishes to minimise the time that it takes to visit all of the different enclosures. 

The weighted graph G, with weights representing the time in minutes taken to move between the five enclosures, can be represented by the following table:

 

 

A

B

C

D

E

A

-

7

5

8

8

B

7

-

11

12

14

C

5

11

-

3

12

D

8

12

3

-

9

E

8

14

12

9

-

 

Draw the weighted graph G.

 

9b
Sme Calculator
5 marks

Let T be the shortest possible time for Jessamy’s journey between the different enclosures.

Starting at enclosure C, use the nearest neighbour algorithm to find an upper bound for T. Indicate clearly the order in which the edges are selected.

9c
Sme Calculator
4 marks

By first removing vertex E, use the deleted vertex algorithm to find a lower bound for T.

9d
Sme Calculator
1 mark

Hence write down an inequality that is satisfied by T.

Did this page help you?

1a
Sme Calculator
2 marks

The diagram below shows the plan of a school building.

uex41hst_mi_q1a_3-10_graph-theory_very_hard_ib_ai_hl_maths_10

Construct a graph to represent this information, using vertices to represent rooms and edges to represent the connecting doors.

 

1b
Sme Calculator
3 marks

For a prank, a student releases a monkey into the English classroom at 8:30 pm on Thursday.

Given that the monkey wanders through the rooms at random, find the probability that the 7th room it wanders into (after leaving the English classroom) is the Geography classroom.

1c
Sme Calculator
2 marks

The monkey continues to wander at random through the school building all night until the cleaner arrives at 6 am on Friday morning 

By inspecting the steady state probabilities, write down the room in which the cleaner is most likely to discover the monkey.

1d
Sme Calculator
3 marks

Stating clearly any assumptions you have made, find an approximation for the total length of time the monkey is likely to have spent in the Maths classroom before the cleaner arrives.

 

Did this page help you?

2a
Sme Calculator
2 marks

Consider the weighted graph G below. Vertex A represents a water source and the remaining vertices represent water features in a park. The edges represent pipes that could be installed to connect the features to the water source, with the weightings being their lengths in metres. 

mi_q2a_3-10_graph-theory_very_hard_ib_ai_hl_maths_dig

Explain, with a reason, which of the two relevant algorithms would be most efficient for finding the minimum length of pipe needed to connect all of the features to the water supply.

 

2b
Sme Calculator
4 marks

Find the minimum length of pipe required to connect all of the water features to the water source using the algorithm stated in part (a). Show each step of the algorithm clearly.

2c
Sme Calculator
6 marks

After the minimum-length system from part (b) has been installed, a fault with the feature at vertex G is discovered such that the feature and all pipes directly connected to it must be disconnected from the water system. Any features that had been connected to the system via vertex G must now be re-connected, using new pipes, by the shortest possible route that does not go through vertex G.

Given that the cost of the piping is £3.80 per metre, find the amount of money that would have been saved if the system was initially designed without the feature at vertex G.

Did this page help you?

3a
Sme Calculator
4 marks

Min Son is installing 8 lamps in her garden and wishes to connect them together so that she will ultimately only need to connect one of the lamps directly to the electrical supply. Each lamp is set in a hole and the electrical cables run underground from the base of each lamp.

Each vertex listed in the table below represents a lamp and the weighting of each edge is the horizontal distance in metres between each pair of lamps.

 

 

A

B

C

D

E

F

G

H

A

-

7

10.2

10.5

15.4

13.1

9.3

6.5

B

7

-

6.5

9.3

13.1

15.4

10.5

10.2

C

10.2

6.5

-

3.8

6.7

11.3

6.8

8.9

D

10.5

9.3

3.8

-

4.9

7.5

3.5

6.7

E

15.4

13.1

6.7

4.9

-

9.2

7.5

11.3

F

13.1

15.4

11.3

7.5

9.2

-

4.9

6.7

G

9.3

10.5

6.8

3.5

7.5

4.9

-

3.8

H

6.5

10.2

8.9

6.7

11.3

6.7

3.8

-

 

Find the minimum length of electrical cable required to connect all of the lamps together.

 

3b
Sme Calculator
2 marks

State two assumptions that have been made.

 

Did this page help you?

4
Sme Calculator
5 marks

In a town there are 8 local attractions and each attraction has its own website that it maintains. Some of the websites contain links to the other websites as shown in the adjacency table below. 

  A B C D E F G H
A 0 1 0 1 0 0 0 1
B 0 0 0 0 0 0 1 0
C 0 0 0 1 0 1 0 0
D 0 0 1 0 0 0 0 0
E 0 1 0 1 0 1 0 0
F 0 0 1 0 1 0 0 0
G 1 1 0 0 1 1 0 1
H 1 0 0 0 0 0 0 0

On its results page, the search engine Beegle ranks the websites in the following order from highest to lowest: C, E, H, F, D, G, A, B.

Beegle states that it ranks websites based on the relative number of clicks each one receives, with those pages that are clicked on more often ranking higher in the search results.

An experiment is conducted to test Beegle’s claim, whereby a volunteer randomly clicks on the links between the different websites 1000 times.

By investigating the probabilities of clicking on the different websites, determine whether Beegle’s statement is likely to be true.  State any assumptions you make in reaching your conclusion.

 

Did this page help you?

5a
Sme Calculator
3 marks

Consider the graph R below.

mi_q5a_3-10_graph-theory_very_hard_ib_ai_hl_maths_dig

Find the number of walks of length 4 or less that start at vertex D and finish at vertex G.

5b
Sme Calculator
3 marks
Determine the starting position of the random walk of length 7 that is least likely to finish at G.
5c
Sme Calculator
1 mark

Without doing any further calculations, write down the steady state probabilities for the graph. Be sure to justify your answer.

5d
Sme Calculator
3 marks

The directional arrow on the edge AG is removed, so that edge AG is now traversable in both directions. 
For a random walk with a very large number of steps, determine the order, from most to least likely, of the vertices upon which the walk is likely to finish.

 

Did this page help you?

6a
Sme Calculator
1 mark

The table below shows the length of track, in kilometres, between 8 local train stations.

 

A

B

C

D

E

F

G

H

A

-

 

 

 

 

 

 

 

B

9

-

 

 

 

 

 

 

C

7

-

-

 

 

 

 

 

D

-

2

16

-

 

 

 

 

E

-

-

5

-

-

 

 

 

F

-

-

8

-

6

-

 

 

G

18

-

-

-

19

-

-

 

H

6

-

15

-

-

21

-

-

 

A railway engineer must walk all the lengths of track between the stations, in either direction, in order to inspect them.  Whilst inspecting track it takes the engineer an average of 1.8 minutes to walk a distance of 100 metres, but if she is walking back over track she has already inspected she walks at a rate of 4 km/h.

Explain why the inspector cannot return to the same station she starts at without walking along some lengths of track more than once.
6b
Sme Calculator
5 marks

Find the least amount of time that the inspector requires to inspect all of the lengths of track if she starts and finishes at station A.

6c
Sme Calculator
1 mark

Given the context of the question, explain why the solution in (b) is not optimal.

 

Did this page help you?

7a
Sme Calculator
4 marks

The table of least weights for a complete graph of 5 vertices is shown below.  Each vertex in the table represents a house that Angelina must visit to make a delivery. The weightings represent the time taken, in minutes, to travel between the houses. Angelina wants to find the quickest route she can take that visits all of the houses exactly once. 

 

A

B

C

D

E

A

-

11

16

11

7

B

11

-

6

12

5

C

16

6

-

9

11

D

11

12

9

-

8

E

7

5

11

8

-

By deleting each vertex in turn, find a best lower bound for the shortest route Angelina can take.

7b
Sme Calculator
4 marks

Starting at vertex A and using the nearest neighbour algorithm, find an upper bound for the shortest route Angelina can take.

7c
Sme Calculator
1 mark

Hence determine the total time of the shortest route that Angelina can take. Give a reason for your answer.

7d
Sme Calculator
1 mark

Write down a possible route of shortest length, given that Angelina starts and finishes at house A.

Did this page help you?

8a
Sme Calculator
5 marks

The graph below shows 6 treasures (vertices) hidden in a maze and the tunnels (edges) that connect them.  The weights on the edges indicate the lengths of the tunnels in metres. Some of the tunnels can only be travelled along in one direction as indicated on the graph.

 mi_q8a_3-10_graph-theory_very_hard_ib_ai_hl_maths_dig

Construct a table showing the shortest distance between each pair of treasures.

8b
Sme Calculator
8 marks

Ankunda wants to find the shortest distance he will have to travel to collect each of the treasures, starting and finishing at the same location.

Find a best upper bound for the shortest route Ankunda can take, given that

i)
he must start and finish at the location of treasure C
ii)
he can start and finish at the location of any treasure.

Did this page help you?