MAST20018代写、代写python/c++程序设计

日期：2022-08-11 10:20

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.