This is Assignment 10 for MATH1005 students in a Friday workshop. It is due at 6 pm
on the Thursday after Workshop 10 (6 days after was released).
There are four problems. The numbering of the problems is strange because the numbering
is taken from a much larger document that has many problems from which I can select.
As long as you can see four different problems, then you have the complete assignment.
You should write your best solutions to the problems here, and then upload your solutions
before the due time. Here are three ways you may complete the assignment:
1. Print the assignment sheet. Write your solutions in pen or pencil on the print out.
Scan your completed assignment, turn the file into a single .pdf file, then upload
your solution file to Wattle.
2. Write your solutions in pen or pencil on blank paper. You should clearly label your
solutions and you should write them in the order in which the problems appear in
your assignment. Scan your completed assignment, turn the file into a single .pdf
file, then upload your solution file to Wattle.
3. Download the assignment sheet to a tablet. Annotate the file using your favourite
annotation software. Flatten the file–this makes your annotations a permanent
part of the file, and if you do not do this then we see only a blank assignment in
our grading software. Upload your flattened solution file to Wattle.
In all cases, the file you upload must be a .pdf file.
Please remember to plan your time carefully so you are not trying to submit your
assignment at the last minute. No late work is accepted.
Please enjoy,
AP
MATH1005/6005 Assignment 10 for Friday Workshop Groups Page 2 of 5
Question 1# The diagram at right shows
the capacities and directions of all links in a network
with source s, target t and intermediate nodes a, b, c, d.
Use the labelling algorithm to find the maximum flow
through the network and how it can be achieved. Prove
that your flow is maximum by finding a cut of equal value.
s a b
c d t
14
12
16
8 94
9 17
Here are some blank diagrams to fill in with levels, labels and flows. Use an outliner
pen to mark the incremental flow dictated by the target’s label. The first diagram is
filled in as an example. You will need all diagrams. Draw a min cut on the last diagram.
s a
1
s14
b
2
a14
c
1
s12
d
2
c9
t
3
b9
14,0
12,0
16,0
8,0 9,04,0
9,0 17,0
Flow
F0
s a b
c d t
14,
12,
16,
8, 9,4,
9, 17,
Flow
F1
s a b
c d t
14,
12,
16,
8, 9,4,
9, 17,
Flow
F2
s a b
c d t
14,
12,
16,
8, 9,4,
9, 17,
Flow
F3
s a b
c d t
14,
12,
16,
8, 9,4,
9, 17,
Flow
F4
Draw a minimum cut on this diagram.
Min Cut Capacity
= Max Flow Value
=
MATH1005/6005 Assignment 10 for Friday Workshop Groups Page 3 of 5
Question 2+ The matrix at right shows the capacities
for a network with source at vertex A and target at vertex H.
(a) Find a minimum cut. Specify the partition of the vertices,
the edges making up the cut, and the value of the cut.

0 5 0 0 8 0 0 0
0 0 6 0 0 3 0 0
0 0 0 4 0 0 4 0
0 0 0 0 0 0 0 6
0 0 0 0 0 9 0 0
0 0 0 0 0 0 7 0
0 0 0 0 0 0 0 9
0 0 0 0 0 0 0 0

A B C D
E F G H
(b) Use the minimum cut to find a maximum flow, using only integer flows.
There is no need to use the labelling algorithm.
Draw a diagram showing capacity and flow value for every directed edge.
A B C D
E F G H
MATH1005/6005 Assignment 10 for Friday Workshop Groups Page 4 of 5
Question 3† Circle the correct answers.
For this question, working is not required and will not be marked.
Brothers Alan, Brian, Carl and Dan agree that they each
need a dog to encourage them to get outside more. They
visit the Pound and as luck would have it, exactly four dogs
are available, Joey, Katie, Lucky and Molly. The diagram
at right indicates which of the dogs each of the boys said
they would be happy to re-home.
(a) How many of the 4! = 24 possible allocations of dogs to
brothers would satisfy all the boys preferences?
2 / 3 / 4 / more than 4
A
B
C
D
J
K
L
M
On a separate piece of paper, not to be submitted, use the matching algorithm (the one
derived from the labelling algorithm for Max flow) to find a satisfactory matching. This
question is mostly about the use of the algorithm, so be sure to stick strictly to the rules
about levels and alphabetical order.
(b) The first brother to be (tentatively) allocated a dog by the algorithm is
ALAN / BRIAN / CARL / DAN
(c) At the completion of the allocation Molly would go home with
ALAN / BRIAN / CARL / DAN
Not to be out done, the brothers’ partners, Jane, Kate, Lucy
and Mary, also visit the Pound, but they are after a cat each.
Available are Princess, Queenie, Rusty and Simba, and the
girls preferences are indicated in the diagram at right.
(d) How many of the 4! = 24 possible allocations of cats to
the girls would satisfy all their preferences?
2 / 3 / 4 / more than 4
J
K
L
M
P
Q
R
S
On another piece of paper, again not to be submitted, use the same matching algorithm
to find a satisfactory matching of girls to cats. Remember that this question is mostly
about the use of the algorithm, so be sure to apply it strictly according to the rules.
(e) The first partner to be allocated a cat by the algorithm is
JANE / KATE / LUCY / MARY
(f) At the completion of the allocation Kate would go home with
PRINCESS / QUEENIE / RUSTY / SIMBA
MATH1005/6005 Assignment 10 for Friday Workshop Groups Page 5 of 5
Question 5? For the webgraph shown at right, find
the PageRanks of each page, assuming no damping.
You will need to use the computer.
A
B C
D E F