## Lecture 21. Bipartite Graph
- Bipartite Graph
- Maximum Matching
Note:
https://www.geeksforgeeks.org/bipartite-graph/
---
### Bipartite Graph
- A **bipartite** graph (or bigraph) is a graph whose vertices can be **divided into two disjoint** sets $U$ and $V$, that is, every edge connects a vertex in $U$ to one in $V$.
<img src="https://cdn.ucode.vn/uploads/1/upload/GWqOzEIV.png" class="element-left content-img" width="70%"/>
---
#### Bipartite Graph
- Equivalently, a bipartite graph is a graph that does **not contain** any **odd-length cycles**.
<img src="https://cdn.ucode.vn/uploads/1/upload/GWqOzEIV.png" class="element-left content-img" width="70%"/>
<img src="https://cdn.ucode.vn/uploads/1/upload/ZahgEwzl.png" class="element-left content-img" />
---
#### Bipartite Graph
- The two sets $U$ and $V$ may be thought of as a coloring of the graph with **two colors**: if one colors all nodes in $U$ blue, and all nodes in $V$ red, each edge has endpoints of **differing colors**.
<img src="https://cdn.ucode.vn/uploads/1/upload/QMGUSfxa.png" class="element-left content-img" width="60%"/>
Note:
this is a complete bipartite graph
---
#### Bipartite Graph
- Denote a bipartite graph: $G=(U,V,E)$
- If $|U|=|V|$: **balanced** bipartite graph.
- If all vertices on the same side of the bipartition have the same degree, then G is called **biregular**.
---
#### Bipartite Graph Characterization
- An undirected graph is bipartite if and only if it does not contain an odd cycle.
- A graph is bipartite if and only if it is **2-colorable** (its chromatic number $\le 2$).
---
#### Bipartite Graph Check
1. Assign **RED** color to the source vertex (putting into set U).
2. Color all the **neighbors** (using BFS) with **BLUE** color (putting into set V).
3. Color all neighbor’s neighbor with **RED** color (putting into set U).
4. If we find a neighbor which is colored with same color as current vertex: graph is not Bipartite
---
#### Bipartite Graph Check
```cpp=
int n;
vector<vector<int>> adj;
vector<int> side(n, -1);
bool is_bipartite = true;
queue<int> q;
for (int st = 0; st < n; ++st) {
if (side[st] == -1) {
q.push(st);
side[st] = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
for (int u : adj[v]) {
if (side[u] == -1) {
side[u] = side[v] ^ 1;
q.push(u);
} else {
is_bipartite &= side[u] != side[v];
}
}
}
}
}
cout << (is_bipartite ? "YES" : "NO") << endl;
```
---
### Matching
- A **matching** or independent edge set in an undirected graph is a set of **edges without common vertices**.
<img src="https://cdn.ucode.vn/uploads/1/upload/oTcPEnaM.png" class="element-left content-img" />
---
#### Matching prolems
- Maximum (cardinality) matching: find a matching containing **as many edges as possible**.
- Maximum weight matching: find a matching in which the sum of **weights is maximized**.
<img src="https://cdn.ucode.vn/uploads/1/upload/mXMUzYKX.png" class="element-left content-img" width="60%"/>
---
### Maximum matching
- Maximum (cardinality) matching: find a matching containing **as many edges as possible**.
<img src="https://cdn.ucode.vn/uploads/1/upload/DVvZUiww.png" class="element-left content-img" />
---
#### Maximum matching
<img src="https://cdn.ucode.vn/uploads/1/upload/lVTzxROo.png" class="element-left content-img" />
---
#### Maximum matching
- Adding two new nodes to the graph: a source and a sink $\rightarrow$ the maximum flow problem by
<img src="https://cdn.ucode.vn/uploads/1/upload/TsgWXXjQ.png" class="element-left content-img" />
---
#### Maximum matching
- After this, the size of a maximum flow in the graph equals the size of a maximum matching in the original graph.
<img src="https://cdn.ucode.vn/uploads/1/upload/EAnrMeAq.png" class="element-left content-img" />
---
#### Maximum matching: Application
- There are $M$ job applicants and $N$ jobs. Each applicant has a subset of jobs that he/she is interested in. Each job opening can only accept one applicant and a job applicant can be appointed for only one job. Find an assignment of jobs to applicants in such that as many applicants as possible get jobs.
<img src="https://cdn.ucode.vn/uploads/1/upload/laLOkPnb.png" class="element-left content-img" />
---
#### Maximum matching
- Maximum Bipartite Matching (MBP) problem can be solved by converting it into a **flow network**.
- Step 1 - **Build a Flow Network**: add a source and add edges from source to all applicants. Similarly, add edges from all jobs to sink. The capacity of every edge is marked as $1$ unit.
<img src="https://cdn.ucode.vn/uploads/1/upload/uFeMtxWa.png" class="element-left content-img" width="60%" />
---
#### Maximum matching
- Step 2 - **Find the maximum flow**: We use Ford-Fulkerson algorithm to find the maximum flow in the flow network built in step 1. The maximum flow is actually the MBP we are looking for.
<img src="https://cdn.ucode.vn/uploads/1/upload/XNIyCnWI.png" class="element-left content-img" width="60%"/>
---
#### Maximum matching: represenation
- Input is in the form of **Edmonds matrix** which is a 2D array `bpGraph[M][N]` with $M$ rows (for $M$ job applicants) and $N$ columns (for $N$ jobs). The value `bpGraph[i][j]` is $1$ if $i$’th applicant is interested in $j$’th job, otherwise $0$.
- Output is number **maximum number of people** that can get jobs.
---
#### Maximum matching: implementation
- A simple way: create adjacency matrix representation of a directed graph with $M+N+2$ vertices, and use `fordFulkerson()` fucntion for the matrix.
- This implementation requires $O((M+N)^2)$ extra space.
---
#### Maximum matching: implementation
- Can be simplified, based on the fact that:
- The graph is **bipartite**
- Capacity of every edge is either $0$ or $1$
- Use DFS traversal to find a job for an applicant (similar to augmenting path in Ford-Fulkerson)
---
#### Maximum matching: implementation
- In `dfs()`, we try all jobs that an applicant `u` is interested in until we find a job, or all jobs are tried without luck. For **every job** we try, we do following:
- If a job is not assigned to anybody, we simply assign it to the applicant and return `True`.
- If a job is assigned to somebody else say `x`, then we recursively check whether `x` can be assigned some other job.
- If `dfs()` returns true, then it means that there is an augmenting path in flow network and 1 unit of flow is added to the result in `maxBPM()`.
---
#### Maximum matching
```python=
class BPM:
def __init__(self, graph):
# residual graph
self.graph = graph
self.applicants = len(graph)
self.jobs = len(graph[0])
def dfs(self, u, matchR, seen):
for v in range(self.jobs):
# If applicant u is interested in job v and v is not seen
if self.graph[u][v] and not seen[v]:
seen[v] = True
'''If job 'v' is not assigned toan applicant OR previously assigned applicant for job v
(which is matchR[v]) has an alternate job available. Since v is marked as visited in the
above line, matchR[v] in the following recursive call will not get job 'v' again'''
if matchR[v] == -1 or self.dfs(matchR[v], matchR, seen):
matchR[v] = u
return True
return False
# Returns maximum number of matching
def maxBPM(self):
# matchR[i] is the applicant number assigned to job i, the value -1 indicates nobody is assigned.
matchR = [-1] * self.jobs
# Count of jobs assigned to applicants
result = 0
for u in range(self.applicants):
# Mark all jobs as not seen for next applicant.
seen = [False] * self.jobs
# Find if the applicant 'u' can get a job
if self.dfs(u, matchR, seen):
result += 1
return result
```
---
#### Maximum matchings
```python=
bpGraph = [[0, 1, 1, 0, 0, 0],
[1, 0, 0, 1, 0, 0],
[0, 0, 1, 0, 0, 0],
[0, 0, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1]]
g = BPM(bpGraph)
print("Maximum number of applicants that can get job is %d " % g.maxBPM())
# Maximum number of applicants that can get job is 5
```
---
#### Maximum matchings
- Ford Fulkerson based approach
- Time complexity: $O(V \times E)$
- Where $V = M + N$
---
#### Maximum matchings: Hopcroft–Karp
- Hopcroft–Karp Algorithm: improvement that runs in $O(\sqrt{V} \times E)$
- https://brilliant.org/wiki/hopcroft-karp/
---
### More Advanced Topics
- Maximum weight matching
- Maximum matching with minimal weight
- Maximum matching in general graph
---
## THE END
{"metaMigratedAt":"2023-06-17T19:46:17.352Z","metaMigratedFrom":"YAML","breaks":true,"description":"View the slide with \"Slide Mode\".","slideOptions":"{\"theme\":\"white\"}","title":"Thuc Nguyen's ADSA Course - Lecture 21. Bipartite Graph","contributors":"[{\"id\":\"476f9158-9a39-4a2d-bb09-ce08dd7eb978\",\"add\":9837,\"del\":561}]"}