Original Model and Related Concepts of Bipartite Graphs

A bipartite graph, also known as a bigraph, is a special model in graph theory.

Let G = (V, E) be an undirected graph.

If the vertex set V can be partitioned into two disjoint subsets (A and B), and every edge (i, j) in the graph connects vertices i and j from different subsets, then G is called a bipartite graph. Typically, the upper vertex set is referred to as the X set, and the lower vertex set as the Y set. For example, the following diagram illustrates a bipartite graph:

Given a bipartite graph G (undirected), a subgraph M of G is called a matching if no two edges in M share a common vertex.

The problem of selecting the largest possible set of such edges is known as the maximum matching problem.

If in a matching, every vertex in the graph is incident to an edge in the matching, it is called a perfect matching or complete matching.

Augmenting Path (Alternating Path): A path where both endpoints are unmatched vertices, and the edges along the path alternate between unmatched and matched edges. Upon finding such a path, since there is one more unmatched edge than matched edges, we can modify the matching by removing the matched edges from the path and adding the unmatched edges, there by increasing the matching size by one.

Solving the Maximum Matching Problem in Bipartite Graphs

Hungarian Algorithm

The Hungarian algorithm is based on the sufficiency proof of Hall's theorem and is the most common algorithm for bipartite graph matching. Its core idea is to search for augmenting paths, using them to find the maximum matching in a bipartite graph.

---

To simplify, imagine you are a matchmaker with N single men and M single women. Each person may have mutual interest in multiple members of the opposite sex. If a man and a woman have mutual interest, you can pair them. Ignoring all unrequited interests, you have a relationship graph where each connection indicates mutual interest.

Aiming to pair as many couples as possible (i.e., find the maximum matching in the bipartite graph), the Hungarian algorithm operates as follows:

1. Try to find a partner for man 1. The first woman connected to him, woman 1, is unmatched, so pair them.

2. Next, for man 2, woman 2 is unmatched, so pair them.

3. For man 3, woman 1 is already matched. Attempt to reassign woman 1's current partner (man 1) to another woman.

(Yellow edges indicate temporary removal.)

The second woman connected to man 1 is woman 2, but she is also matched. Try to reassign woman 2's current partner (man 2) to another woman (this is a recursive process).

Man 2 can be paired with woman 3, resolving the issue. Backtrack:

• Man 2 pairs with woman 3.

• Man 1 pairs with woman 2.

• Man 3 pairs with woman 1.

Final result after step 3:

4. For man 4, following the same process, no woman can be reassigned to accommodate him, so no match is possible.

This illustrates the Hungarian algorithm's flow, where finding a partner is a recursive process, with the key concept being "making room" by reassigning matches.

The principle can be summarized as: Seize opportunities when available, and create them when necessary.

Code Implementation

Here is a sample implementation of the Hungarian algorithm in C++:

bool findMatch(int manIndex, int numWomen, bool** interestMatrix, bool* visited, int* womanPartner) {
    for (int womanIndex = 0; womanIndex < numWomen; womanIndex++) {
        if (interestMatrix[manIndex][womanIndex] && !visited[womanIndex]) {
            // visited array indicates if the woman has been considered in this augmenting path search
            visited[womanIndex] = true;
            if (womanPartner[womanIndex] == -1 || findMatch(womanPartner[womanIndex], numWomen, interestMatrix, visited, womanPartner)) {
                // womanPartner array stores the man matched to each woman; -1 indicates unmatched
                womanPartner[womanIndex] = manIndex;
                return true;
            }
        }
    }
    return false;
}

In the main function, iterate through each man to find matches:

int hungarianAlgorithm(int numMen, int numWomen, bool** interestMatrix) {
    int* womanPartner = new int[numWomen];
    bool* visited = new bool[numWomen];
    int matchCount = 0;

    for (int i = 0; i < numWomen; i++) {
        womanPartner[i] = -1; // Initialize all women as unmatched
    }

    for (int manIndex = 0; manIndex < numMen; manIndex++) {
        for (int i = 0; i < numWomen; i++) {
            visited[i] = false; // Reset visited array for each man
        }
        if (findMatch(manIndex, numWomen, interestMatrix, visited, womanPartner)) {
            matchCount++;
        }
    }

    delete[] womanPartner;
    delete[] visited;
    return matchCount;
}