Maximum Matching

A maximum matching in a bipartite graph is a matching of maximum size, that is, it contains the largest possible number of edges without sharing vertices. It has applications in resource allocation.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int maxBPMatch(int[][] graph) {
  
  int N = graph.length; 
  int[] pairU = new int[N];
  int[] pairV = new int[N];

  // Initialize pairs to not matched
  Arrays.fill(pairU, -1);
  Arrays.fill(pairV, -1);

  int result = 0;
  for (int u = 0; u < N; u++) {
    if (pairU[u] < 0) {
      result += dfs(graph, pairU, pairV, u); 
    }
  }
  
  return result;
}

int dfs(int[][] graph, int[] pairU, int[] pairV, int u) {
  if (u < 0) return 0;

  for (int v = 0; v < graph.length; v++) {
    if (graph[u][v] == 1 && pairV[v] < 0) {
      pairV[v] = u;
      pairU[u] = v;
      return 1 + dfs(graph, pairU, pairV, pairU[u]);
    }
  }
  return 0;
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
int maxBPMatch(const vector<vector<int>>& graph) {
  
  int N = graph.size();
  vector<int> pairU(N, -1);
  vector<int> pairV(N, -1);

  int result = 0;
  for (int u = 0; u < N; u++) {
    if (pairU[u] < 0) {
      result += dfs(graph, pairU, pairV, u);
    }
  }

  return result;
}

// DFS procedure 

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def max_bp_match(graph):
  
  N = len(graph)
  pair_u = [-1] * N
  pair_v = [-1] * N

  result = 0
  for u in range(N):
    if pair_u[u] < 0:
      result += dfs(graph, pair_u, pair_v, u)

  return result
  
def dfs(graph, pair_u, pair_v, u):
  
  # DFS procedure
  return 0

Maximum matchings have applications in scheduling and resource allocation.

In graph theory, Maximum Matching refers to a set of edges that don’t share any vertex, such that the set is as large as possible. In simpler terms, it’s the largest group of edges you can pick without picking two edges that share a vertex. Maximum matching is commonly used in applications like job allocation, network design, and marriage problems.

Example Code in Java

Here is a simple implementation of the Hopcroft-Karp algorithm for Bipartite Graph:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class MaximumMatching {
    static final int NIL = 0;
    static final int INF = Integer.MAX_VALUE;
    int[] pair;
    int[] dist;
    ArrayList<Integer>[] adj;

    // Returns true if there is an augmenting path
    boolean bfs(int n) {
        Queue<Integer> queue = new LinkedList<>();
        for (int u = 1; u <= n; u++) {
            if (pair[u] == NIL) {
                dist[u] = 0;
                queue.add(u);
            } else {
                dist[u] = INF;
            }
        }
        dist[NIL] = INF;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            if (u != NIL) {
                for (int v : adj[u]) {
                    if (dist[pair[v]] == INF) {
                        dist[pair[v]] = dist[u] + 1;
                        queue.add(pair[v]);
                    }
                }
            }
        }
        return dist[NIL] != INF;
    }

    // Returns true if there is an augmenting path beginning with u
    boolean dfs(int u) {
        if (u == NIL) return true;
        for (int v : adj[u]) {
            if (dist[pair[v]] == dist[u] + 1 && dfs(pair[v])) {
                pair[u] = v;
                pair[v] = u;
                return true;
            }
        }
        dist[u] = INF;
        return false;
    }

    // Returns the size of maximum matching, needs the number of vertices n
    int hopcroftKarp(int n) {
        pair = new int[n + 1];
        dist = new int[n + 1];
        int matching = 0;
        while (bfs(n)) {
            for (int u = 1; u <= n; u++) {
                if (pair[u] == NIL && dfs(u)) {
                    matching++;
                }
            }
        }
        return matching;
    }
}

Example Code in C++

1
// C++ code to be added

Example Code in Python

1
# Python code to be added

You’d implement similar logic in C++ and Python to solve the maximum matching problem using algorithms like Hopcroft-Karp or Ford-Fulkerson.