MAST20018 – Discrete Mathematics and Operations Research
Assignment 1
Due 5pm on Wednesday 17th August 2022. Submit via Canvas. Show all working and explain all
reasoning.
1. Every Activity on Node network has an associated adjacency matrix Q, where a “max-plus”
operation on Q is defined in order to calculate the length of the longest path in the network
(and hence the minimum completion time of the project). Please answer the following questions
rigorously.
(a) Let Qp be the matrix that results by taking the max-plus operation p times on Q. What
can you conclude if Qp = Qp+1?
(b) Given that Qp = Qp+1, what does the entry of Qp in the row of α and the column of β
represent?
(c) More generally, given that Qp = Qp+1, what do the numbers in the row of α represent?
(d) Suppose that you wanted to design a matrix method for calculating the latest finishing
times of all activities in an AON network. How would you specify an adjacency matrix
and a corresponding matrix operation in order to achieve this?
2. Consider the network below:
s a
f
t
d
b c e
(a) Write down the adjacency matrix for the given network using the formula
A = [aij], aij =
??? 1, if nodes i and j are connected by an edge0, otherwise.
Index your rows and columns in the order s, a, b, c, d, e, f, t.
(b) Without doing any matrix multiplication, write down the top row of A2, and explain your
reasoning.
(c) Draw a tree, with root s, indicating the shortest path from a to all the other nodes. Use
the BFS method from class.
(d) Using the data in your tree, employ the recursive algorithm from class to compute the
number of shortest paths from s to t.
1
MAST20018 – Discrete Mathematics and Operations Research
(e) Without doing any matrix multiplication, state and explain the entry in the row of node
s and the column of node t in A3.
3. The vertex chromatic number of a graph is the minimum number of colours needed to colour
the vertices of the graph so that no pair of adjacent vertices share the same colour.
(a) For the graph of Q2, find upper and lower bounds on the vertex chromatic number.
Explain your reasoning and name any theorems used.
(b) Find a minimum colouring for the graph of Q2.
4. A graph G is called planar if there exists an embedding of G in the plane so that no pair of
edges intersect, except possibly at shared endpoints. A plane embedding of a planar graph
results in a subdivision of the plane, where each maximally connected region is bounded by
vertices and edges of the graph. Each such maximally connected region is called a face.
Prove that the complete graph on five nodes is not planar.