MAST20018 – Discrete Mathematics and Operations Research Assignment 1
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MAST20018 – Discrete Mathematics and Operations Research
Assignment 1
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
d 
t
(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 edge
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 s 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.
(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. Provide citations if you use any known theorems from the literature.
2022-11-07