3.10 Graph Theory

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

Explain why the graph is considered to be strongly connected.

Write down the adjacency matrix for the graph .

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

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

Consider the weighted graph below.

(ii)

Write down a Hamiltonian cycle starting from vertex .

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

State the total weight of the minimum spanning tree.

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.

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

Starting from vertex , use Prim’s algorithm on the table to find and draw the minimum spanning tree. Show each step of the process clearly.

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.

Show the information from the table in a directed graph.

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

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

Let  be the graph below.

Construct the transition matrix for a random walk around .

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

The graph 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.

State the degree of each vertex.

Explain why  does not contain an Eulerian circuit.

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.

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

Explain why G is not a complete graph.

Complete the table of least weights below.

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

The table of least weight for a graph  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.

Draw the graph .

By deleting vertex 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.

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

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