Question 1
A connected simple graph has eight vertices. Their degrees are
The graph has 14 edges.
Determine the value of .
[2]
State the number of vertices of odd degree.
[1]
Determine the number of additional edges required to make complete.
[2]
0
Question 2
A connected undirected graph has vertices with degrees
Determine whether the graph has an Eulerian trail or an Eulerian circuit.
[2]
new edge is added. Determine whether the new graph has an Eulerian circuit. Justify your answer.
[2]
0
Question 3
The directed graph has vertices in the order and adjacency matrix
Rows represent starting vertices.
Determine the out-degree and in-degree of vertex .
[2]
Write down the vertices adjacent from .
[1]
Determine whether is strongly connected. Justify your answer.
[2]
0
Question 4
An undirected graph has vertices in the order and adjacency matrix
Calculate the number of walks of length from to .
[2]
Calculate the number of walks from to having length at most but at least .
[2]
Explain why the identity matrix is not included in the calculation in part (b).
[1]
0
Question 5
A delivery vehicle moves between depots , and . Its transition matrix is
where rows represent the current depot. Initially, the vehicle is at depot .
Write down the initial state vector .
[1]
Determine the probability distribution after two transitions.
[3]
Write down the probability that the vehicle is at depot after two transitions.
[1]
0
Question 6
A connected undirected graph has vertex set and edge set
Classify the walk as a walk, trail or path, using the most specific applicable term. Justify your answer.
[2]
Determine the endpoints of an Eulerian trail in the graph and give one such trail.
[2]
Explain why the graph cannot have a Hamiltonian cycle.
[1]
0
Question 7
A road inspector must start and finish at the same junction while travelling along every road at least once. The road network has edges with lengths, in kilometres,
Determine the minimum length of the inspector's route.
[4]
0
Question 8
The distances between five cities are represented by the complete weighted graph below.
Apply the nearest neighbour algorithm starting at . Write down the resulting tour.
[3]
Determine the upper bound for the travelling salesman problem obtained from this tour.
[2]
0
Question 9
For a travelling salesman problem, a feasible Hamiltonian cycle of weight has been found. Applying the deleted vertex algorithm at vertices gives lower bounds , respectively.
State the strongest lower bound and the vertex that produces it.
[1]
Deduce the weight of an optimal Hamiltonian cycle. Justify your answer.
[3]
0
Question 10
A communication network has vertices and edges
The network is connected.
Show that the network is a tree.
[2]
Write down the unique path from to and state its length.
[2]
new edge is added. Write down the cycle that is created.
[1]
0
Question 11
A company wishes to connect six sites . The possible links and their costs, in thousands of dollars, are
Using Kruskal's algorithm, write down the first three edges selected.
[2]
Determine a minimum spanning tree and its total cost.
[3]
0
Question 12
The weighted adjacency table for a network is shown below. A dash indicates that there is no direct edge.
Use Prim's algorithm, starting at , to write down the edges in the order in which they are selected.
[3]
Calculate the total weight of the minimum spanning tree.
[2]
0
Question 13
A complete weighted graph has the following edge weights:
Delete vertex and determine the weight of a minimum spanning tree on the remaining vertices.
[2]
Use the deleted vertex algorithm to determine a lower bound for the travelling salesman problem.
[2]
Explain why the value found in part (b) is a lower bound.
[1]
0
Question 14
Four clinics are connected through an intermediate junction . The undirected road lengths, in kilometres, are
A route in the completed graph may represent a multi-edge shortest route in the original network.
Determine the least distances from to and from to .
[2]
Complete the least-distance model as required and apply the nearest neighbour algorithm starting at . Determine the resulting tour and its total length.
[3]
0
Question 15
A simplified page-ranking model contains webpages . The hyperlinks are
A user chooses with equal probability between all links leaving the current page. The webpages are ordered .
Construct the transition matrix , using rows as source webpages.
[2]
Initially, the user is equally likely to be on any webpage. Determine the probability distribution after two transitions.
[3]
Using the distribution after two transitions, identify the webpages with the joint highest rank.
[1]
0
Question 16
A maintenance vehicle must traverse every edge of a network and return to its starting point. The network has vertices and weighted edges
Identify the odd-degree vertices.
[1]
Determine the least total weight of the edges that must be duplicated.
[3]
Hence determine the minimum total weight of a closed route traversing every edge.
[2]
0
Question 17
A connected simple graph represents communication links between eight research stations. The degrees of seven of the vertices are
The graph has edges. The two vertices of degree are labelled and .
I.
Determine the degree of the eighth vertex.
[2]
II.
Determine how many more edges would be required to make complete.
[2]
new edge is added. Determine whether the resulting graph has an Eulerian circuit. Justify your answer.
[4]
0
Question 18
A company plans fibre links between seven facilities. The possible links and installation costs, in thousands of dollars, are
I.
Using Kruskal's algorithm, write down the links in the order in which they are selected.
[2]
II.
Calculate the total cost of the minimum spanning tree.
[2]
Apply Prim's algorithm starting at . State the order in which the links are selected and explain why the total agrees with part (a).
[4]
0
Question 19
A connected simple graph models communication links between ten mountain observatories . The degrees of the first eight vertices are
The graph has edges, and .
I.
Determine and .
[3]
II.
State the number of odd-degree vertices.
[1]
I.
Explain why the original graph has neither an Eulerian circuit nor an Eulerian trail.
[2]
II.
It is known that the four odd-degree vertices can be paired using two edges that are not already in the graph. Determine the minimum number of edges that must be added to obtain an Eulerian circuit. Justify your answer.
[2]
0
Question 20
A directed data network has vertices in the order and adjacency matrix
Rows represent starting vertices.
I.
Determine the in-degree and out-degree of vertex .
[2]
II.
Explain why the directed graph is strongly connected.
[2]
I.
Calculate the number of walks of length from to .
[2]
II.
Calculate the number of walks from to having length at least and at most .
[2]
0
Question 21
A simplified page-ranking model has webpages . The directed hyperlinks are
A user chooses with equal probability from the hyperlinks leaving the current webpage. Rows represent the current webpage.
I.
Construct the transition matrix , using the vertex order .
[2]
II.
The user starts at webpage . Determine the probability distribution after two transitions.
[2]
I.
Determine the probability distribution after four transitions.
[2]
II.
Find the stationary distribution and hence identify the webpage with the highest long-term rank.
[2]
0
Question 22
An undirected walking network has vertices and edges
The vertices are ordered .
I.
Write down the degree of each vertex.
[2]
II.
Construct the adjacency matrix of the network.
[2]
I.
Calculate the number of walks of length from to .
[2]
II.
Calculate the number of walks from to having positive length at most .
[2]
0
Question 23
A weighted graph has vertices and edges
I.
Use Kruskal's algorithm to find one minimum spanning tree.
[2]
II.
Calculate the weight of the minimum spanning tree.
[2]
Determine whether the minimum spanning tree is unique. Justify your answer by giving two different minimum spanning trees.
[4]
0
Question 24
An ecological network is represented by a connected simple graph with nine vertices and eight edges. The vertex degrees are
I.
Determine the value of .
[2]
II.
Show that is a tree.
[2]
One new edge is added between two previously non-adjacent vertices. Explain why exactly one cycle is created, and determine how many further edges would be required to make the resulting graph complete.
[4]
0
Question 25
A directed graph models the permitted movement of data packets between five servers . Its directed edges are
Rows of an adjacency matrix represent starting vertices.
I.
Construct the adjacency matrix using the vertex order .
[2]
II.
Determine the in-degree and out-degree of server .
[2]
I.
Calculate the number of directed walks of length from to .
[2]
II.
Hence calculate the number of walks from to having positive length at most .
[2]
0
Question 26
Visitors move randomly between three exhibition rooms . From , a visitor chooses equally between and . From , the visitor chooses equally between and . From , the visitor always moves to . Rows represent the current room.
I.
Construct the transition matrix using the order .
[2]
II.
visitor starts in room . Determine the probability distribution after two transitions.
[2]
I.
Find the stationary distribution of the visitor.
[3]
II.
Interpret the first component of this stationary distribution in context.
[1]
0
Question 27
A research institute is installing fibre between laboratories . The possible links and their costs, in thousands of euros, are given by the edge list below; this edge list defines the network:
I.
Use Kruskal's algorithm to determine a minimum spanning tree.
[3]
II.
Calculate the total cost of the minimum spanning tree.
[1]
The institute wants to add exactly one available link so that failure of any one link leaves all laboratories connected.
[4]
0
Question 28
A courier must visit six distribution centres. Travel times, in minutes, form a complete weighted graph with edges
A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
A | — | 2 | 7 | 8 | 6 | 3 |
B | 2 | — | 3 | 7 | 8 | 6 |
C | 7 | 3 | — | 2 | 6 | 8 |
D | 8 | 7 | 2 | — | 3 | 7 |
E | 6 | 8 | 6 | 3 | — | 2 |
F | 3 | 6 | 8 | 7 | 2 | — |
I.
Apply the nearest-neighbour algorithm starting at .
[2]
II.
Calculate the resulting upper bound.
[1]
Use the deleted vertex algorithm with deleted to prove that the tour in part (a) is optimal.
[5]
0
Question 29
A festival walkway graph is a simple undirected graph with vertices and edges
Thus, two triangular walkway loops share only the vertex .
I.
Determine whether the graph has an Eulerian circuit. Justify your answer.
[2]
II.
Explain why the graph has no Hamiltonian cycle.
[2]
For the new graph, determine whether an Eulerian trail exists and whether a Hamiltonian cycle exists. Justify each answer.
[4]
0
Question 30
A street-cleaning vehicle must traverse every street in a connected network and return to its starting point. The street lengths, in kilometres, are
I.
Identify the odd-degree vertices.
[2]
II.
Calculate the total length of all the streets.
[1]
Compare all possible pairings of the odd-degree vertices and determine the least additional distance required.
[3]
Hence determine the minimum length of a closed route and give one possible route.
[2]
0
Question 31
A maintenance worker must inspect every corridor of a campus network and return to the starting point. Corridor lengths, in hundreds of metres, are
I.
Identify the odd-degree vertices and find the shortest route between them.
[2]
II.
Determine the minimum total length of the inspection route.
[2]
new corridor of weight is constructed. Determine the new minimum total length of an inspection route and explain why it is shorter than the route in part (a).
[4]
0
Question 32
The table gives travel times, in minutes, between six locations in a complete network.
Location | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
A | 4 | 8 | 7 | 6 | 3 | |
B | 4 | 5 | 9 | 7 | 6 | |
C | 8 | 5 | 4 | 3 | 7 | |
D | 7 | 9 | 4 | 5 | 8 | |
E | 6 | 7 | 3 | 5 | 4 | |
F | 3 | 6 | 7 | 8 | 4 |
I.
Apply the nearest-neighbour algorithm starting at . State the resulting tour.
[2]
II.
Determine the resulting upper bound.
[2]
Delete vertex and use the deleted vertex algorithm to find a lower bound. Hence state the largest possible difference between the upper bound in part (a) and the optimal tour.
[4]
0
Question 33
A travelling salesperson must visit five warehouses. The complete weighted graph has edge weights
I.
Apply the nearest-neighbour algorithm starting at .
[2]
II.
State what the value found represents for the optimal travelling-salesperson tour.
[2]
Delete vertex and use the deleted vertex algorithm. Hence prove that the tour found in part (a) is optimal.
[4]
0
Question 34
A water-taxi network has terminals . The available direct routes have lengths, in kilometres,
For the travelling-salesperson model, a completed edge represents a shortest route in the original network.
I.
Determine the least distances from to , from to , and from to .
[2]
II.
Determine the least distances from to and from to .
[2]
Apply the nearest-neighbour algorithm to the completed graph, starting at . Determine the tour and its total length.
[4]
0
Question 35
A bicycle moves randomly between docking stations . The directed routes are
At each station, the bicycle is equally likely to take any outgoing route.
I.
Construct the transition matrix in the order , using rows as source stations.
[2]
II.
Initially, the bicycle is equally likely to be at any station. Determine the probability distribution after three transitions.
[2]
Find the stationary distribution and identify all stations with the highest long-term probability.
[4]
0
Question 36
A directed graph has vertices in the order and adjacency matrix
I.
Calculate the number of walks from to having positive length at most .
[2]
II.
Calculate the number of walks of length from to .
[2]
Determine the smallest integer such that every vertex can reach every other distinct vertex using at most directed edges. Justify your answer using matrix powers.
[4]
0
Question 37
A festival site is represented by a connected graph with vertices and edges
Thus, two triangular regions are joined by the edge .
I.
Determine whether the graph has an Eulerian trail or an Eulerian circuit.
[2]
II.
Give one Eulerian trail.
[2]
Explain why the original graph has no Hamiltonian cycle. A new edge is then added. Give a Hamiltonian cycle in the new graph.
[4]
0
Question 38
A renewable-energy company can install cables along the following links. The weights are cable lengths in kilometres.
I.
Use Prim's algorithm starting at to determine the order in which the links are selected.
[2]
II.
Calculate the total length of the minimum spanning tree.
[2]
The link becomes unavailable. Use Prim's algorithm starting at to determine a new minimum spanning tree and its total length.
[4]
0
Question 39
A wheel network , where , consists of a cycle of outer vertices and one central vertex. The central vertex is adjacent to every outer vertex. The accompanying diagram is a separate schematic example and does not define the edge set of ; use the written definition.
I.
Write down the degree of the central vertex and the degree of each outer vertex.
[2]
II.
Hence determine the number of edges in .
[2]
Show that for every vertex , and hence determine in terms of and .
[4]
0
Question 40
A power network has vertices . The upper vertex in the diagram is denoted by . The available links have weights
where .
I.
For , use Kruskal's algorithm to determine a minimum spanning tree.
[2]
II.
Calculate its total weight.
[1]
I.
Find the values of for which the link occurs in a minimum spanning tree.
[3]
II.
Hence write down the minimum spanning tree weight as a piecewise function of .
[2]
0
Question 41
A road inspector must traverse every road in a connected network and return to the starting junction. The road lengths, in kilometres, are
I.
Identify the odd-degree vertices.
[2]
II.
Calculate the total length of all roads.
[1]
Apply the Chinese postman algorithm to determine the minimum length of the inspector's closed route.
[5]
0
Question 42
A snowplough must traverse every road and return to its starting junction. The network has weighted edges, with lengths in kilometres:
A new road of length kilometres is proposed. If constructed, the new road must also be cleared.
I.
Identify the odd-degree vertices in the original network and find the length of a shortest path between them.
[2]
II.
Determine the minimum length of a closed route in the original network.
[2]
I.
Show that after the new road is constructed, the network has an Eulerian circuit.
[2]
II.
Find the values of for which constructing the new road decreases the minimum closed-route length.
[2]
0
Question 43
A ferry company serves ports . The available two-way routes, with lengths in kilometres, are
For a travelling-salesperson model, an edge in the completed graph represents a shortest route through the original network.
I.
Determine the least distances from to , from to , and from to .
[3]
II.
Write down the least distance from to .
[1]
I.
Apply the nearest-neighbour algorithm to the completed graph, starting at .
[2]
II.
Calculate the tour length and explain how the final completed edge is travelled in the original network.
[2]
0
Question 44
A simplified page-ranking model has webpages . The hyperlinks are
A user chooses equally between all outgoing hyperlinks. Rows represent the current webpage.
I.
Construct the transition matrix in the order .
[2]
II.
user starts on webpage . Determine the probability distribution after three transitions.
[2]
Find the stationary distribution and identify the webpage with the greatest long-term rank.
[4]
0
Question 45
A monitoring network is arranged as a rooted -ary tree of depth . The root is at level . Every non-leaf vertex has exactly children, and all leaves are at level .
I.
For and , determine the number of vertices and the number of leaves.
[2]
II.
Determine the number of edges in this network.
[2]
For general and , show that the number of edges is
[4]
0
Question 46
The vertices , where , represent checkpoints positioned at coordinates on a straight line. The complete graph has edge weight
I.
For , apply the nearest-neighbour algorithm starting at .
[2]
II.
Calculate the weight of this tour.
[1]
For the graph defined above, prove that the nearest-neighbour algorithm starting at produces an optimal Hamiltonian cycle for general .
[5]
0
Question 47
A communication graph is the complete bipartite graph . Its vertices are divided into sets and , where and . Every vertex in is adjacent to every vertex in , and there are no edges joining two vertices in the same set.
I.
Write down the degree of a vertex in and the degree of a vertex in .
[2]
II.
Determine the number of edges in .
[1]
Fix a vertex in , and let be the adjacency matrix of the graph. Determine and , and hence deduce formulae for and for positive integers .
[5]
0
Question 48
Five observatories are arranged around a circular reserve. The complete weighted graph has weight on each perimeter edge
and weight on each of the five remaining edges, where .
Edge | Type | Weight |
|---|---|---|
A-B | Perimeter | p |
B-C | Perimeter | p |
C-D | Perimeter | p |
D-E | Perimeter | p |
E-A | Perimeter | p |
A-C | Diagonal | q |
A-D | Diagonal | q |
B-D | Diagonal | q |
B-E | Diagonal | q |
C-E | Diagonal | q |
I.
For , apply the nearest-neighbour algorithm starting at and give one possible tour.
[2]
II.
Write down the resulting upper bound.
[1]
Use the deleted vertex algorithm, deleting , to prove that a perimeter tour is optimal for every .
[5]
0
The Fast Track To Your
Best IB Coursework & College Essays
All content on this website has been developed independently from and is not endorsed by the International Baccalaureate Organization. International Baccalaureate and IB are registered trademarks owned by the International Baccalaureate Organization.