Alternative Coursework
COMP3940 Graph Algorithms and Complexity Theory
Summer 2020
In the undirected graph below a matching is indicated by bold edges. Execute Edmonds’
algorithm on this graph starting from the given matching. In each round of the algorithm
show the following.
• Grow alternating trees until you find an augmenting path or a blossom.
• If blossoms were found construct the shrink graph.
• If an augmenting path was found give the augmented matching.
n
1 1
e
1 1
s
1 1
w
1 1
n
1 2
e
1 2
s
1 2
w
1 2
n
1 3
e
1 3
s
1 3
w
1 3
n
2 1
e
2 1
s
2 1
w
2 1
n
2 2
e
2 2
s
2 2
w
2 2
n
2 3
e
2 3
s
2 3
w
2 3
n
3 1
e
3 1
s
3 1
w
3 1
n
3 2
e
3 2
s
3 2
w
3 2
n
3 3
e
3 3
s
3 3
w
3 3
n
4 1
e
4 1
s
4 1
w
4 1
n
4 2
e
4 2
s
4 2
w
4 2
n
4 3
e
4 3
s
4 3
w
4 3
n
5 1
e
5 1
s
5 1
w
5 1
n
5 2
e
5 2
s
5 2
w
5 2
n
5 3
e
5 3
s
5 3
w
5 3
Submission: Send your work in portable document format (PDF) to the module leader by
email. Therefore
either work out your solution on paper and scan it,
or use LATEX or any other text processing system to create the PDF file via pdflatex
or a suitable PDF converter.
Deadline: Tuesday 4 August 2020, 10am.