UNIVERSITY OF STIRLING MATPMD2
Computing Science & Mathematics November 2023
MATPMD2 : NETWORKS AND GRAPH THEORY
GRAPH THEORY ASSIGNMENT : AUTUMN SEMESTER 2023
Paper available: 9am Tuesday 21st November 2023
Due: 12pm (noon) Monday 27th November 2023
This assignment is worth a total of 50 marks. This is a two-hour paper which means that you
should take no longer than two hours to complete this assignment.
Full and appropriate working should be shown. The marks for each part of a question are shown
in brackets.
You should assume all graphs are simple undirected graphs with no loops or multiple edges
unless clearly indicated otherwise.
At the end of the assignment are additional copies of the graphs used in questions 3 and 6 which
you might find useful.
THIS IS AN OPEN-BOOK ASSIGNMENT AND YOU MAY CONSULT YOUR COURSE
NOTES, BUT YOU MAY NOT USE ANY OTHER RESOURCES.
YOU SHOULD COMPLETE THE ASSIGNMENT UNDER EXAM CONDITIONS. YOU
SHOULD COMMUNICATE WITH NO ONE AND SHOULD WORK ALONE.
COMPLETE YOUR SOLUTIONS WITH THE FOLLOWING DECLARATION:
“I DECLARE THAT THIS IS MY OWN WORK”
DO NOT SIGN THE DECLARATION.
1
UNIVERSITY OF STIRLING MATPMD2
Computing Science & Mathematics November 2023
1. (i) An n-vertex tree is a connected graph on n vertices which contains no cycles.
(a) Draw a tree on 7 vertices and state the number of edges in this tree.
Draw another tree on 9 vertices, again stating the number of edges in this tree.
(b) Deduce (without proof) the number of edges in an n-vertex tree.
[2]
(ii) (a) Draw three non-isomorphic, connected graphs, each with n = 9 vertices, and
each containing exactly two cycles.
[You do not need to prove that these graphs are non-isomorphic.]
(b) Explain why the number of edges is always one more than the number of vertices
in such graphs. [5]
Total marks [7]
2. Let G be the following graph with adjacency matrix A(G).
(i) Write out in full the adjacency matrix of G, the complement of G. [3]
(ii) Working only from the structure of the graph G,
(a) write down the diagonal entries of A2 ,
(b) write down the trace of A3 ,
(c) write down the diagonal entries of A3 ,
(d) find the diagonal entry of A4 corresponding to vertex 2.
[11]
(iii) Comment on the idea of using the diagonal entries of A4 to determine the number of
4−cycles contained in a graph. [3]
Total marks [17]
Question 3 overleaf............
2
UNIVERSITY OF STIRLING MATPMD2
Computing Science & Mathematics November 2023
3. Let G be the following graph.
(i) Partition the edge set of G into cycles.
(ii) Hence find an Eulerian trail in G.
[6]
Total marks [6]
4. Write down the weighted distance matrix for the following graph.
[4]
Total marks [4]
Question 5 overleaf............
3
UNIVERSITY OF STIRLING MATPMD2
Computing Science & Mathematics November 2023
5. The following graph has multiple, weighted, directed edges.
(i) Give an example of a real-life scenario that this might represent and suggest a research
question that this might help to answer. [3]
(ii) Explain how you might simplify this graph by combining edges so that there are no
multiple edges. What might this mean in the context of your real-life example? [2]
Total marks [5]
6. Consider the following graph.
(i) Identify the two vertices of highest degree in this graph. [1]
(ii) Calculate the clustering coefficient for each of these vertices. [5]
(iii) Which of these two vertices do you think is the most important, and why? [2]
(iv) Identify a vertex with normalized degree centrality 0.4 and explain what this is
measuring. [3]
Total marks [11]
End of assignment.
4
UNIVERSITY OF STIRLING MATPMD2
Computing Science & Mathematics Graph in question 3 November 2023
5
UNIVERSITY OF STIRLING MATPMD2
Computing Science & Mathematics Graph in question 6 November 2023
