Graphs & networks

Graph G is shown below

Show that graph G is not bipartite.

Use Kuratowski’s Theorem to show that graph G is not planar.

Determine whether graph G is simply connected.

Write down the indegree and outdegree of node L.

Determine whether digraph H is simply connected.

At the end of each year the workers at an office take part in a gift exchange. Each worker randomly chooses the name of one other worker and buys a small gift for that person.

Each worker’s name is chosen by exactly one of the others. A worker cannot choose their own name.

In the first year there were four workers, A, B, C and D. There are 9 ways in which A, B, C and D can choose the names for the gift exchange. One of these is already given in the table in the Printed Answer Booklet.

Complete the table in the Printed Answer Booklet to show the remaining 8 ways in which the

names can be chosen.

During the second year, worker D left and was replaced with worker E. The organiser of the gift exchange wants to know whether it is possible for the event to happen for another 3 years (starting with the second year) with none of the workers choosing a name they have chosen before, assuming that there are no further changes in the workers.

Classify the organiser’s problem as an existence, construction, enumeration or optimisation

problem.

After the second year, the organiser drew a graph showing who each worker chose in the first two years of the gift exchange. None of the workers chose the same name in the first and second years.

The vertices of the graph represented the workers, A, B, C, D and E, and the arcs showed who had been chosen by each worker.

Explain why the graph must be a digraph.

State the number of arcs in the digraph that shows the choices for the first two years.

Assuming that the digraph created in part (d) is planar, use Euler’s formula to calculate how

many regions it has.

Write down a way in which the nearest neighbour method can fail to solve the problem of

finding a least weight cycle through all the vertices of a network.

Explain why, when trying to find a least weight cycle through all the vertices of a network, an

ad hoc method may be preferable to an algorithmic approach.

The distance matrix below represents a network connecting six viewpoints A, B, C, D, E and F. The distance matrix shows the direct distances between each pair of viewpoints where a direct route exists. The distances are measured in km. A blank shows that there is no direct route between the two viewpoints.

Draw the network on the vertices given in the Printed Answer Booklet.

Apply the nearest neighbour method, starting from A.

A hiker wants to travel between the six viewpoints, starting and finishing at A. The hiker must visit every viewpoint at least once, but may visit a viewpoint more than once.

Show that the hiker does not need to travel as far as 50 km.

Use an appropriate algorithm to find the shortest distance from F to each of the other

viewpoints.

Complete the table in the Printed Answer Book to show the shortest distance between each

pair of viewpoints.

Use your answer to part (g) to find a lower bound for the distance the hiker must travel by

initially deleting vertex A.

A graph is shown below.

Write down a cycle through all six vertices.

Write down a continuous route that uses every arc exactly once.

Use Kuratowski’s theorem to show that the graph is not planar.

Show that the graph has thickness 2.

Four children, A, B, C and D, discuss how many of the 23 birthday parties held by their classmates they had gone to. Each party was attended by at least one of the four children.

The results are shown in the Venn diagram below.

Construct a complete graph K₄, with vertices representing the four children and arcs

weighted to show the number of parties each pair of children went to.

State a piece of information about the number of parties the children went to that is shown in

the Venn diagram but is not shown in the graph.

A fifth child, E, also went to some of the 23 parties shown in the Venn diagram. Every party that E went to was also attended by at least one of A, B, C and D.

• A was at 8 of these parties, B at 7, C at 5 and D at 8.

• These include 5 parties attended by both A and B, 2 by both A and C, 3 by both A and D, 3 by both B and D and 4 by both C and D.

• These include 1 party attended by A, B and D and 1 party attended by A, C and D.

Use the inclusion‑exclusion principle to determine the number of parties that E went to.

A connected graph is shown below.

Write down a path through exactly 7 of the vertices.

Write down a cycle through exactly 6 of the vertices.

Explain why Ore’s theorem cannot be used to decide whether or not this graph is

Hamiltonian.

Prove that the graph is not Hamiltonian.

The following colouring algorithm can be used to determine whether a connected graph is bipartite or not. The algorithm colours each vertex of a graph in one of two colours, and .

STEP 1 Choose a vertex and assign it colour . STEP 2 If any vertex is adjacent to another vertex of the same colour, stop. Otherwise assign colour to each vertex that is adjacent to a vertex with colour . STEP 3 If any vertex is adjacent to another vertex of the same colour, stop. Otherwise assign colour to each vertex that is adjacent to a vertex with colour . STEP 4 Repeat STEP 2 and STEP 3 until all vertices are coloured. STEP 5 If there are no adjacent vertices of the same colour then the graph is bipartite, output the word “bipartite”. Otherwise the graph is not bipartite, output the words “not bipartite”.

Use this algorithm, starting at vertex A, to determine whether the graph is bipartite, or not.

Explain what Kuratowski’s theorem tells you about the graph.

Show that the graph has thickness 2.

A building has 7 CCTV cameras, A to G, at the junctions of some of the corridors.

The cameras at the junctions and the lengths of the 11 corridors between them, in metres, are shown in the table below.

Model this information as a network.

Use an appropriate algorithm to calculate the minimum distance from A to each of the other

vertices.

The run‑time of an algorithm for finding this minimum distance is proportional to the total number of comparisons used. For a network with n vertices, the worst case is when the algorithm is applied to a network based on the complete graph K_n.

In each pass

• A vertex is made permanent and the temporary label at all adjacent vertices that are not yet permanent are updated. This uses 1 comparison for every such vertex (adjacent to the permanent label) that previously already had a temporary label.

• The best temporary labels at all vertices that do not yet have permanent labels are then compared to determine the next vertex to become permanent. If there are k such vertices this involves k - 1 comparisons.

By considering the number of comparisons of each type in each iteration, show that the algorithm uses a total of 6 comparisons when it is applied to a network based on the complete

graph K₄.

You are given that the total number of comparisons used when the algorithm is applied to a network based on K_n is (n - 1)(n - 2).

A computer takes 0.03 seconds to apply this algorithm on a network based on K₇.

Calculate, to 1 decimal place, how many seconds it will take the computer to apply the

algorithm to a network based on K₇₀.

The manager wants to construct a tour (a closed route) that passes each camera.

Find a lower bound for the length of this tour by initially deleting D.

Find an upper bound for the length of this tour by using the nearest neighbour algorithm

starting from D.

Deduce the length of the shortest possible tour. Briefly explain your reasoning.

A simply connected semi-Eulerian graph G has 6 vertices and 8 arcs. Two of the vertex degrees are 3 and 4.

Determine the minimum possible vertex degree.

Determine the maximum possible vertex degree.

Write down the two possible degree sequences (ordered lists of vertex degrees).

The adjacency matrix for a digraph H is given below.

Write down the indegree and the outdegree of each vertex of H.

Use the indegrees and outdegrees to determine whether graph H is Eulerian.

Use the adjacency matrix to determine whether graph H is simply connected.

Explain carefully how you know that the graph K₅ has thickness 2.

The following colouring algorithm can be used to determine whether a connected graph is bipartite or not. The algorithm colours each vertex of a graph in one of two colours, α and β.

STEP 1 Choose a vertex and assign it colour α.

STEP 2 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour β to each vertex that is adjacent to a vertex with colour α.

STEP 3 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour α to each vertex that is adjacent to a vertex with colour β.

STEP 4 Repeat STEP 2 and STEP 3 until all vertices are coloured.

STEP 5 If there are no adjacent vertices of the same colour then the graph is bipartite. Otherwise the graph is not bipartite.

STEP 6 Stop.

Apply this algorithm to graph A, starting with the vertex in the top left corner, to determine

whether graph A is bipartite or not.

The worst case is when the graph is a path that starts at one vertex and ends at another, having passed through each of the other vertices once.

What can you deduce about the efficiency of the colouring algorithm in this worst case?

The colouring algorithm is used on two graphs, X and Y. It takes 10 seconds to run for graph X and 60 seconds to run for graph Y. Graph X has 1000 vertices.

Estimate the number of vertices in graph Y.

A different algorithm has efficiency O(2ⁿ). This algorithm takes 10 seconds to run for graph X.

Explain why you would expect this algorithm to take longer than 60 seconds to run for graph Y.

This question is about the planar graph shown below.

Apply Kuratowski’s theorem to verify that the graph is planar.

Use Euler’s formula to calculate the number of regions in a planar representation of the

graph.

Write down a Hamiltonian cycle for the graph.

By finding a suitable pair of vertices, show that Ore’s theorem cannot be used to prove

that the graph, as shown above, is Hamiltonian.

Draw the graph formed by using the contractions AB and CF.

Use Ore’s theorem to show that this contracted graph is Hamiltonian.