9.04 Bipartite networks

What do these networks have in common?

For each network, we have split the vertices into two groups, blue and orange. Notice that the orange vertices are only connected to blue vertices, and the blue vertices are only connected to orange vertices - there are no edges between blue vertices, and no edges between orange ones either.

Whenever we can divide the vertices up like this, we call the network a bipartite network.

We are going to study these kinds of networks, with one group of vertices representing tasks, and the other representing agents - people, companies, countries, and so on. These are called allocation problems (sometimes assignment problems).

Let's consider the following situation:

Paula, Rohan and Erin are working together on a group project over the weekend. There are a number of tasks that need to get done, but each student is better at some things and worse at others. This table shows how many hours it would take for them to do each part of the project:

Once every task is completed, they get to go home. Who should do what part to make sure they can go home the earliest?

There are two ways we can represent this same information - one is by using a matrix:

\begin{pmatrix} 10 & 5 & 8\\ 6 & 7 & 12 \\ 9 & 8 & 5 \end{pmatrix}

The matrix is just a more condensed version of the table. A more interesting way is to represent the information using a bipartite network:

We use a bipartite network since every person is connected to every task, but a person isn’t connected to a person, or a task to a task.

We want to pick out three edges so that each person and task has exactly one edge coming out of it, forming an allocation. Here are two ways we could do it:

In the first allocation, the group has to stay for 12 hours, since Rohan takes 12 hours to do the speech while Paula and Erin wait around. The second allocation is a little better since the group stays for 8 hours and, in this allocation, it’s Rohan who does the waiting. What is the best allocation possible?

With some further investigation, we would find that this is the best allocation possible:

This allocation has the group only taking 6 hours to complete the project, half the time of the first allocation we tried. It is the optimum allocation.

We may have spotted this allocation straight away just by looking at the table. It allocates everyone the task that they’re best at. But this isn’t always the case, so be sure to check thoroughly.

Examples

Example 1

Consider the following bipartite graph.

Which of the following allocations agree with the bipartite graph?

A

B

C

D

Worked Solution

Create a strategy

Choose the options where the corresponding connected vertices match the given graph.

Apply the idea

Option A shows C and 2 are connected which is not true in the graph.

Option C shows B and 5 are connected which is not true in the graph.

Option D shows B and 3 are connected which is not true in the graph.

Option B has connections that are included in the graph. The answer is option B.

Watch question walkthrough

Example 2

Which of the following bipartite graphs represent the given reduced table?

	A	B	C	D
M	0	4	0	3
N	8	9	1	0
O	5	0	3	7
P	0	4	0	0

A

B

C

D

Worked Solution

Create a strategy

Choose the options where the edges in the bipartite graph are represented by the zero entries in the reduced table.

Apply the idea

In the table, entries with the 0 indicates when two vertices are joined by an edge.

So the 0 in row M and A, indicates that A and M are joined by an edge. Likewise with C and M, D and N, B and O, P and A, C and P, and finally D and P.

The option that matches the correct graph is option C. The answer is option C.

Watch question walkthrough

Now we can investigate a procedure that guarantees the best allocation possible. We will learn to find the optimal allocation using the Hungarian Algorithm with its network version.

Here’s a summary of the Hungarian algorithm (network version):

1. Subtract the lowest weight of edges coming out of each vertex on the left from the others.

2. Subtract the lowest weight of edges coming out of each vertex on the right from the others.

3. Identify if there are any paths of three 0-edges. If so, mark the middle edge of those paths. Subtract the lowest nonzero weight from all other nonzero weightings in the network, but add this weight to the marked 0-edge(s).

Examples

Example 3

Harvey, Kiara, and Dao are on the medical support team for a company that runs events. There are events at three major cities this weekend, and the cost for each of them to travel to each city is given in the table below:

	Sydney	Melbourne	Perth
\text{Harvey}	\$200	\$250	\$320
\text{Kiara}	\$280	\$300	\$250
\text{Dao}	\$300	\$470	\$510

Which allocation costs the least money overall?

Worked Solution

Create a strategy

Draw a graph for the table and subtract the lowest weight of edges coming out of each vertex on the left and right.

Apply the idea

We can draw the information in the table in the following graph:

The first step of the algorithm is to subtract the lowest weight of edges coming out of each vertex on the left from the others.

The lowest weight from the Harvey vertex is 200, so we subtract this from all the other edges coming out of the Harvey vertex.

The lowest weight from the Kiara vertex is 250, so we subtract this from all the other edges coming out of the Kiara vertex.

The lowest weight from the Dao vertex is 300, so we subtract this from all the other edges coming out of the Dao vertex.

Each person now has a 0-edge, but these edges do not all point to different destinations - both Harvey and Dao have a 0-edge to Sydney, and nobody has a 0-edge to Melbourne.

The second step of the algorithm is to subtract the lowest weight of edges coming out of each vertex on the right from the others.

The lowest weight coming out of the Sydney vertex is 0, and since subtracting 0, doesn’t change the network we do nothing. This is the same for Perth.

The cheapest trip to Melbourne is \$50, so we subtract \$50 from all Melbourne trips:

Now there are 0-edges both to and from each person and task. We are ready to do the allocation. There’s only one 0-edge from Perth, and only one from Dao, so we highlight those:

This leaves Harvey to be connected to Melbourne:

This is the optimum allocation. If we recover the original edge weights, we can calculate the cost:

The total, cheapest cost is \$250+\$300+\$250=\$800.

Reflect and check

Interestingly, this involves paying the most to send someone to Sydney. This procedure finds what’s best for the group, not always the individual.

There is a second way to find the optimum allocation from within the table itself, without ever drawing a bipartite network. This can be very useful when there would be a lot of vertices and edges, since the network can get very crowded.

Here’s a summary of the Hungarian algorithm (matrix version):

1. Subtract the lowest number in each row from every number in that row.

2. Subtract the lowest number in each column from every number in that column.

3. Cover the 0’s with the minimum number of lines. If the number of lines required is less than the total number of rows (or columns), subtract the smallest nonzero value in the matrix from all other nonzero values, and add this value to any number covered by two lines. Then read off the optimum allocation.

The matrix version saves space, is easier to enter into a computer, and makes the tricky cases a lot easier to spot and deal with. But the network version inspired this one, and is easiest for smaller allocations. Use the one you like the best.

Examples

Example 4

A limousine company has to dispatch 3 cars to 3 different locations. The following table displays the traveling cost (in dollars) of each limousine to each area.

\text{Locations and Cars}	A_1	A_2	A_3
L_1	29	37	22
L_2	32	27	26
L_3	33	34	25

a

Use the Hungarian algorithm to find the allocation which uses the minimum cost.

Worked Solution

Apply the idea

Start by writing the numbers in a matrix.

\begin{pmatrix} 29 & 37 & 22\\ 32 & 27 & 26 \\ 33 & 34 & 25\\ \end{pmatrix}

Subtract the lowest number in each row from the numbers in that row.

\begin{pmatrix} 29-22 & 37-22 & 22-22\\ 32-26 & 27-26 & 26-26 \\ 33-25 & 34-25 & 25-25\\ \end{pmatrix} = \begin{pmatrix} 7 & 15 & 0\\ 6 & 1 & 0 \\ 8 & 9 & 0\\ \end{pmatrix}

Subtract the lowest number in each column from the numbers in that column.

\begin{pmatrix} 7-6 & 15-1 & 0\\ 6-6 & 1-1 & 0 \\ 8-6 & 9-1 & 0\\ \end{pmatrix} = \begin{pmatrix} 1 & 14 & 0\\ 0 & 0 & 0\\ 2 & 8 & 0\\ \end{pmatrix}

Draw lines through the row and column with all zeros.

The lowest remaining number is 1 so we subtract this from all the remaining numbers and add it to the number that has two lines through it to get:

\begin{pmatrix} 1-1 & 14-1 & 0\\ 0 & 0 & 0+1\\ 2-1 & 8-1& 0\\ \end{pmatrix} = \begin{pmatrix} 0 & 13 & 0\\ 0 & 0 & 1\\ 1 & 7& 0\\ \end{pmatrix} \\

We can cover all the zeros using 3 horizontal lines, one through each row. Since 3 is equal to the total number or rows, we are done. Here is the final matrix with the locations and cars: \quad \begin{matrix} A_1 & A_2 & A_3 \end{matrix} \\ \begin{matrix} L_1\\ L_2 \\ L_3 \\ \end{matrix} \begin{pmatrix} 0 & 13 & 0\\ 0 & 0 & 1\\ 1 & 7& 0\\ \end{pmatrix}

The only 0 in the row for L_3 is in column A_3, so L_3 should be allocated to A_3.

L_1 has zeros in the A_1 and A_3 columns, but A_3 is already taken, so L_1 must be allocated to A_1.

L_2 has zeros in the A_1 and A_2 columns, but A_1 is already taken, so L_2 must be allocated to A_2.

The allocation that uses the minimum cost is: L_1 \to A_1\\ L_2 \to A_2\\ L_3 \to A_3\\

Watch question walkthrough

b

What is the minimum cost of travel?

Worked Solution

Create a strategy

Add the numbers that correspond to the the optimum allocation found in part (a).

Apply the idea

\text{Locations and Cars}	A_1	A_2	A_3
L_1	29	37	22
L_2	32	27	26
L_3	33	34	25

From the table we can see that the optimal allocation has the following costs: L_1 \to A_1 =29\\ L_2 \to A_2 =27\\ L_3 \to A_3 =25\\

\displaystyle \text{Minimum cost}	\displaystyle =	\displaystyle 29+27+25	Add the costs
	\displaystyle =	\displaystyle \$ 81	Evaluate

Watch question walkthrough