Bipartite Graph

A bipartite graph is used to represent a relationship between two distinct sets of variables.

Essential Further Mathematics 4ed 2012 (Figure 24.7)

Hungarian Algorithm

The Hungarian Algorithm is a method of finding the optimal allocation for activities. It is the process of assigning the members to tasks in an optimal way that would either minimize the total cost or total time taken.

A bipartite graph can be used to help find that optimal allocation.

The matrix given to construct the bipartite graph MUST be a square matrix (i.e. a matrix that has the same number of rows and columns).

There are a few steps involved in a Hungarian Algorithm and they are:

1. Reduce each row of the matrix/table by the smallest number in that row. (Row Reduction)
2. Reduce each column by the smallest number in that column. (Column Reduction)
3. Cover all ZEROS using the MINIMUM number of horizontal and vertical lines.

ENSURE that you are not tempted to use lines to try and cover all the zeros. There are times when you can use for example 3 lines to cover all the zeros instead of 4 lines.

4. Determine if the number of lines used = the number of tasks there are. If yes, then you can draw a bipartite graph and use the zeros to match the tasks.

If no, then find the SMALLEST number that is NOT COVERED by a line and reduce all the uncovered number by that number. Use lines to cover the zeros and see if the number of lines = number of tasks present. Repeat if necessary.

The following question has been obtained from VCAA Further Mathematics Exam 2 2012 (Question 3). The numbers represents the time taken for each worker to perform each task in minutes.

Step 1: Perform a row reduction.

• Smallest number in row W was 21 therefore, you take away 21 from every value in that row.

Step 2: Perform a column reduction

Step 3: Cover all zeros with the MINIMUM number of lines.

Step 4: Does the number of lines = the number of tasks. In this case NO. So we must find the smallest number that is uncovered and use it to subtract from the other uncovered numbers. That number is 3. We take 3 away from the other uncovered numbers on the table to get the table shown below.

The number of lines is now EQUAL to the number of tasks.

Step 5: Construct a bipartite graph, using the zeros on the table/matrix to allocate the tasks.

Looking at the bipartite graph Julia can only perform task W and so must be allocated to that task, because there is no other task that she can do.

Max can do both task W and Y, however, Julia has already been allocated to task W and so he must be allocated to task Y.

Lana can do tasks W, X and Y. Tasks W and Y have already been allocated, which means that she must be allocated to task Y.

This leaves Ken who must be allocated to task Z.

Therefore the final allocation is:

In some cases, you may have to go back to the original table given in the question, which may represent the times that each worker can perform each task in order to perform the allocation, if there are two people that can do a particular task and there is no way of looking at the bipartite graph to perform the allocation.

For example, if Julia and Max can both perform task W. Julia takes 26 minutes to complete task W and Max takes 25 minutes to complete task W. Then Max would be chosen to complete task W, because he takes the least amount of time.

However, we only use this method if the other method cannot help us to determine the optimal allocation i.e. if Julia can only complete task W, then regardless of how much time she takes to complete it she MUST be allocated to task W.

Remember we are looking for the optimal allocation: minimising the total time taken to complete tasks.