D2 - Unit 1

Question 0

What is a maximal matching?

Answer 0

A matching with the most possible matches

Question 1

What is a bipartite graph?

Answer 1

A graph with one set of nodes on one side and one set on another

Question 2

What is a complete matching?

Answer 2

A matching where everything on one side is connected to something on another.

Question 3

How to use the Hungarian algorithm to solve allocation problems.

Answer 3

1. Reduce each row by the lowest number and write this at the side.
2. Reduce each column by the lowest number and write this at the top.
3. Cover all zeros with the minimum number of lines. If the minimum number is the same size of the array (the number of rows) go to step 5.
4. Reduce all uncovered numbers by the minimum uncovered number, and increase the numbers covered twice by the minimum uncovered number. Return to step 2.
5. There is now a maximal matching using only 0s.

Question 4

How to apply the Hungarian algorithm when the array is not a square?

Answer 4

Create a dummy row/column where the values are the same as or higher the highest value in that column/row.

Question 5

How to use the Hungarian algorithm when the higher the number the better (to maximise)?

Answer 5

Find the highest number on the array. Create a new table where the numbers are the difference between the highest number and the original number.

Question 6

How to improve a matching

Answer 6

Start at an unconnected node and go down an unconnected arc.
Go back along a connected arc.
Then go along an unconnected arc etc.
Carry on until you arrive at a node with no other arcs, or no connected arcs if it is time to go down a connected one.
List the path as well as the new pairings.