MATH1005/MATH6005 Discrete Mathematical Models

Final Exam, Semester 1, 2022

“You are a rainbow lorikeet; the problems on this exam are seeds.” AP.

Problem #1 #2 #3 #4 #5 Total

Score

Out of 10 10 10 10 10 50

1
 Throughout this exam, and as we did throughout the course, we write N for the set of positive integers.
Problem 1 (10 marks) (a) Use a truth table to prove or disprove the following logical equivalence:
((p ∧ q) → r) ≡ (p → (q → r))

(b) Let X denote the set of all finite graphs. Consider the following statement:
For all finite graphs G, if G is planar and has no loops, then the chromatic number of
G is at most 4.
Write down the structural part of a proof that proceeds via the contrapositive.

Please note, some of the terms in this statement were not introduced in our course. You do not
need to know what they mean in order to complete the question.

(c) Let U = {x, y, z} and S = {(a, W ) ∈ U × P(U ) | a ̸∈ W }. Use set-roster notation to describe S.

2
(d) Consider the following statement:
For any universal set U and for any A, B, C ∈ P(U ), we have (A \ B) \ C = A \ (B ∪ C).
Either: provide a counterexample to disprove the statement; or use an element proof, the definition
of set operations and relations, and any of the logical equivalences below you may need to prove
the statement.

Given any statement variables p, q, and r, a tautology t and a contradiction c, the following
logical equivalences hold.
1. Commutative laws: p∧q ≡q∧p p∨q ≡q∨p
2. Associative laws: (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
3. Distributive laws: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
4. Identity laws: p∧t≡p p∨c≡p
5. Negation laws: p ∨ ¬p ≡ t p ∧ ¬p ≡ c
6. Double negative law: ¬(¬p) ≡ p
7. Idempotent laws: p∧p≡p p∨p≡p
8. Universal bound laws: p ∨ t ≡ t p∧c≡c
9. De Morgan’s laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q
10. Absorption laws: p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p
11. Negations of t and c: ¬t ≡ c ¬c ≡ t

3
(e) Consider the following statement:
For any universal set U and for any A, B ∈ P(U ), we have P(A ∪ B) ⊆ P(A) ∪ P(B).
Either: provide a counterexample to disprove the statement; or use an element proof, the definition
of set operations and relations, and any of the logical equivalences below you may need to prove
the statement.

Given any statement variables p, q, and r, a tautology t and a contradiction c, the following
logical equivalences hold.
1. Commutative laws: p∧q ≡q∧p p∨q ≡q∨p
2. Associative laws: (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
3. Distributive laws: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
4. Identity laws: p∧t≡p p∨c≡p
5. Negation laws: p ∨ ¬p ≡ t p ∧ ¬p ≡ c
6. Double negative law: ¬(¬p) ≡ p
7. Idempotent laws: p∧p≡p p∨p≡p
8. Universal bound laws: p ∨ t ≡ t p∧c≡c
9. De Morgan’s laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q
10. Absorption laws: p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p
11. Negations of t and c: ¬t ≡ c ¬c ≡ t

4
Problem 2 (10 marks) (a) Use induction to prove the following:
For all n ∈ N, n is a non-negative integer power of 2 or n can be written as a sum of
distinct non-negative integer powers of 2.

Note: By completing the problem above, you have proved that every positive integer can be repre-
sented by a bit string using binary positional notation.

5
(b) A certain bank has 31,700 customers. Each customer at the bank has chosen a 4-digit PIN to
identify themselves at the ATM. Examples of PINs are 0678, 2189, 9834. Prove that there is at
least one PIN shared by four or more customers.

(c) A FAW is a four letter ‘word’ whose letters are in alphabetical order. Letters are drawn from
the standard lower case English 26-letter alphabet, and are allowed to repeat. A ‘word’ does not
have to appear in any dictionary. Examples of FAWs are abcd, ccyz, aooy and yyyy. A FAW is
said to contain a repeated letter if there is at least one letter which appears more than once in
the word.

If a FAW is chosen at random, what is the probability that it contains a repeated letter? You
may give you answer in the form of a mathematical expression (you do not have to compute a
final number)

6
(d) A four-sided die is a tetrahedron with faces marked 1, 2, 3 and 4. When a four-sided die is
thrown, one face is not visible—the number on the face that is not visible is said to be the
‘number thrown.’ Consider a probability experiment in which we toss a red four-sided die and a
blue four-sided die simultaneously.
(i) Describe how we may represent outcomes so that outcomes are equally likely, and then use
set-roster notation to describe the sample space of the experiment.

(ii) Let T be the random variable on S which assigns to each outcome the absolute value of the
difference between the numbers thrown on the two dice. Let E1 = {s ∈ S | T (s) > 1} and let
E2 be the event that a 2 is thrown on the red die. Are the events E1 and E2 independent?

7
Problem 3 (10 marks) Enumerative Combinatorics and Graph Theory
(a) Let G be the graph shown below.

A e1 B

e5 E e2 e3

e4
D C
(i) How many different walks in G start at A and end at D? If possible, list them all.

(ii) How many different walks in G are paths which start at A and end at D? If possible, list
them all.

(iii) How many different walks in G are circuits (including the trivial circuits)? If possible, list
them all.

(b) Hypercubes were introduced in the course as a family of graphs which may represent a good
solution to which problem?

8
(c) (i) If G and H are graphs, what is an isomorphism between G and H?

(ii) Let m, n ∈ N be such that m ̸= n, and let G be a graph that is isomorphic to the complete
bipartite graph Km,n . How many different isomorphisms are there between G and Km,n ?
Justify your answer.

9
(d) Let W be the graph shown below.

G F

B C

Prove or disprove the following: W has a Hamilton circuit.

10
Problem 4 (10 marks) (a) Describe the input and output to the Nearest Neighbour algorithm.

(b) Let G be a connected graph. State a condition on G that is both necessary and sufficient for
Fleury’s algorithm to be successful at identifying an Euler path in G.

(c) Let G be the weighted graph

A 7 B 1 F
1 4 5 2 3
C 2 D 6 E
.

Use one of the algorithms discussed in the course to find a minimal spanning tree for G. Write
the name of the algorithm, and draw the minimal spanning tree it produces, in the space below.

11
(d) Let H be the weighted graph

1 15

A 13 B 1 F

2 5 3 3

C 1 D 9 E
.

Use Dijkstra’s algorithm to find the shortest path in H from A to E (pseudocode for the Dijkstra’s
algorithm is given at the end of the exam paper). To show that you applied the algorithm correctly,
you should complete the table below

The vertices are ‘locked in’

in the following order

The shortest path found is

12
(e) A matching problem has been turned into a maximum flow problem for a transport network
using the method described in the course. The resulting directed graph is shown below. Use the
vertex labelling algorithm described in the course to solve the matching problem (pseudocode for
the vertex-labeling algorithm is given at the end of the exam paper). The first incremental flow
is shown on the diagram below and recorded in the first table below. Record each subsequent
incremental flow in the first table below (use only as many rows as you need), and record the
final matching in the second table.

F0 with f1 A W

B X
S T
C Y

D Z

incremental path of incremental flow

flow label

f1 SAW T

vertex The vertex, if any, with which it is matched

13
Problem 5 (10 marks) (a) A freelance computer network consultant, let’s call her Yvonne, is employed
in weekly contracts. Each week she is either: employed (E), unemployed (U) or training in new
technology (T). Yvonne’s records support the following assumptions:
• If she’s employed this week, then next week she’ll be employed with probability 0.80, and
training in new technology with probability 0.05.
• If she’s unemployed this week, then next week she’ll be employed with probability 0.60 and
training in new technology with probability 0.20.
• If she is training in new technology this week, then next week she’ll be employed with proba-
bility 0.70.
• She never trains in new technology for two consecutive weeks.
We can model Yvonne’s situation by a Markov process. Make a transition diagram to model
Yvonne’s situation.

(b) A corporation, BIG CORP INDUSTRIES, seeks to understand which employees perform tasks
that are the most important to the corporation’s operation. Every employee has submitted a
response to the following survey question: “List the names of colleagues whose work is important
to yours.”

A ‘PageRank-like approach’ will be used to rank the importance of employees from this data.
(i) Describe a directed graph (What is the set of vertices? When is there an edge from one
vertex to another?) related to the survey data that may play the role of a ‘webgraph’ in a
PageRank-like approach to ranking the importance of employees.

(ii) State at least two hypotheses concerning the data and the importance of employees that, if
assumed true, would justify the claim that a PageRank-like approach will be an effective way
to rank the importance of employees.

14
(c) Let G be the webgraph with the adjacency matrix A shown below, and suppose that we are using
the page rank algorithm with a damping factor of 80% (0.80) to rank the pages in G.
 
0 1 1 0
 1 0 0 1 
A=  0 1 0 0 

0 0 0 0

(i) Draw a picture of G.

(ii) Write down the basic transition matrix T associated to G.

 3 27 27 3 
60 60 60 60
 
 27 3 3 27 

 60 60 60 60 

(iii) The modified transition matrix M associated to G is M =  .
 
3 51 3 3

 60 60 60 60 

 
 19 19 19 3 
60 60 60 60

 3 
10
 
 5 
 10 
Your friend says the following: “The page rank vector associated to G is v =  .”
 
 1 
 10 
 
1
10

In no more than three sentences, explain how you could determine whether or not your friend
is correct.

15
 THERE ARE NO MORE PROBLEMS. PSEUDOCODE FOR TWO ALGORITHMS IS ALL THAT
FOLLOWS.

Dijkstra’s Algorithm
Input:
1. Connected simple graph G. Vertices A, Z from G.
2. Distance function dist : E(G) → Q+ .
Output:
1. Tree T containing A and Z as vertices.
T is a subgraph of G.
The unique path A→Z in T has minimal total distance of all paths A→Z in G.
2. ‘Labelling’ L : V (T ) → Q+ ; L(v) = min.dist(A → v).
Method:
1. Initialize the tree T : Set V (T ) = {A}, E(T ) = ∅.
2. Initialize a ‘Marking’ function M : V (G) → V (G) ∪ {blank}:
Set M (v) = blank for all v ∈ G.
3. Set L(A) = 0. Set ‘current vertex’ c to A.
While c ̸= Z:
4. For each vertex v adjacent to c but not in T :
If v is unmarked (i.e. M (v) = blank)
or if L(v) > L(c)+ dist({c, v})
set M (v) = c, L(v) = L(c)+ dist({c, v}).
5. From all marked v ∈ G\T (i.e. M (v) ̸= blank and v ̸∈ T )
(such v are said to be ‘on the fringe’)
select one, say w, with minimal L(v).
6. Insert vertex w and edge {M (w), w} into the tree T .
(I call this “locking in” w and its lead-in edge.)
7. Update c to w. (i.e. make w the new current vertex.)
End of While Loop

End of Method

16
Vertex labelling algorithm for finding a maximum flow function for a transport network
Input: Transport network D with capacity function C.
Output: A maximum flow function Fmax for the network.
Method: Initialise F to the zero flow F0 . Initialize i to 1.
For i = 1, 2, . . . carry out stage i below to attempt to build an incremental flow fi .
If stage i succeeds, define Fi = Fi−1 + fi and proceed to stage i+1.
If stage i fails, define Fmax = Fi−1 and stop.
Stage i:
1. If i > 1, mark up the amended edge flows for Fi−1 .
2. Mark up the levels for Fi−1 , as explained below.
3. If t is assigned a level, stage i will succeed, so continue.

If not, then stage i fails, so return above to define Fmax and terminate.
4. Mark up labels for Fi−1 as follows until t is labelled:
(a) Label each level 1 vertex v with skv , where kv = S((s,v)). (see below for definition of S)
(b) If t has level 2 or more now work through the level 2 vertices in alphabetical order, labelling each vertex v with uku , where
• u is the alphabetically earliest level 1 vertex with (u,v) ∈ E(D) and S((u,v)) > 0,
• kv is the minimum of S((u,v)) and the value part of u’s label.
(c) If t has level 3 or more now work through the level 3 vertices in a similar manner and so on.
5. Let pi be the path u0 u1 . . . un where un = t and for 0 < j ≤ n
uj has label uj−1 kj .

Define fi to be the incremental flow on pi with flow value kn .

End of Method
Levels and labels: At each stage of the vertex labelling algorithm levels and labels are associated afresh with the vertices of the
network.

The level of a vertex is determined iteratively as follows:

• The source vertex s always has level 0.
• If e = (s, x) and S(e) > 0 then x has level 1.
• If x has level n and S((x, y)) > 0 then y has level n + 1 provided it has not already been assigned a lower level.

The label on a vertex v of level n ≥ 1 has the form uk, where u is a vertex of level n − 1 and (u, v) ∈ E(D) is an edge on the path for
a potential incremental flow through v with flow value k.

The algorithm assigns labels in ascending order of levels, and in alphabetical order within levels.

The spare capacity function S

For vertices u,v of D, where D has capacity and flow functions C, F :

C((u,v))−F ((u,v))
 if (u,v) ∈ E(D)
S((u,v)) = F ((v,u)) if (v,u) ∈ E(D)

0 otherwise.


When (v,u) ∈ E(D), S((u, v)) is called a virtual capacity.

17