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.
