Graph Theory (DP IB Maths: AI HL)

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

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

Draw the graph of G.

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

Consider the graph G shown below.

Write down the adjacency matrix for the graph G.

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

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).

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.

Show that G is a Hamiltonian graph.

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

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.

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

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).

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.

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.

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.

Consider the graph G below.

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

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

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.

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.

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.

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.

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

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.

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.

In order to distribute food for the animals in the wildlife park that she runs, Jessamy needs to visit each of the enclosures and .  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:

Draw the weighted graph G.

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.

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

Hence write down an inequality that is satisfied by T.

The diagram below shows the plan of a school building.

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

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 7^th room it wanders into (after leaving the English classroom) is the Geography classroom.

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.

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.

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. 

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.

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.

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.

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.

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

State two assumptions that have been made.

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. 

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.

Consider the graph  below.

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

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

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.

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

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.

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.

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

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. 

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

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

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

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

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.

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

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