|
Be the first user to complete this post
|
Add to List |
401. Introduction to Bipartite Graphs OR Bigraphs
Bipartite Graphs OR Bigraphs is a graph whose vertices can be divided into two independent groups or sets, U and V such that each edge in the graph has one end in set U and another end in set V or in other words each edge is either (u, v) which connects edge a vertex from set U to vertex from set V or (v, u) which connects edge a vertex from set V to vertex from set U. No edge will connect to the vertices that belong to the same set.
If two sets U and V are considered as two sets of colors (Let's say colors are Red and Black) and color the graph with these so that all the vertices in set U are in red color and all the vertices in set V are in black color. Now we can conclude that in Bipartite Graphs OR Bigraphs all the edges have one vertex color red and another one black.
Example:
If both sets have equal cardinality (means both sets have an equal number of vertices), then it is called balanced bipartite graph and if each vertex in set U has an edge to all the vertices in another set V and vice versa then that bipartite graph is called complete bipartite graph.
Bipartite Graph cannot have cycles with odd length - Bipartite graphs can have cycles but with of even lengths not with odd lengths since in cycle with even length its possible to have alternate vertex with two different colors but with odd length cycle its not possible to have alternate vertex with two different colors, see the example below
Matching: Matching in the graph is a subset of its edges. None of these edges share any vertices or in other words, for each edge will connect two unique vertices. This algorithm solves many matching problems including maximum bipartite matching.
Problems on Bipartite Graphs
- Check if the Graph is Bipartite - Adjacency Matrix
- Check if Graph is Bipartite - Adjacency List BFS
- Check if Graph is Bipartite using DFS
- Maximum number of edges in Bipartite Graph- Coming Soon
- Find Maximum Edges that can be added to a tree to stay as Bipartite Graph- Coming Soon
- Maximum Bipartite Matching
Source- wiki