Bipartite graphs

What is a bipartite graph

bipartite graph is actually really simple graph that I shall explain in just a few minutes below

A bipartite graph is such a graph where you can split the nodes into two sets that have no intersection (disjoint sets), where no two nodes in the same set have an edge between them. So this means that an edge will only connect two nodes from different sets.

An example:

you will have to forgive my terrible digital drawing skills, but i think this simple diagram gets the point across. We have 5 nodes here and there are two different sets: N1, N2, N3 are a part of one set, and N4, N5, N6 are part of the other set. There are also no edges within the red nodes, or within the green nodes.

attributes

• Two disjoint set of vertices
• A node can only have as many edges as there are nodes in the smaller set
• Every edge will connect an edge in one set to an edge in another set
• There are no odd-length cycles. This is because to have an odd length cycle there must be an edge between nodes in the same set, and this goes against the definition of a bipartite graph

Uses

One use that will be something that we all have interacted with is web search engines, as queries can be one set while web pages is another set.
Another use of bipartite graphs is in neural networks which are very useful in machine learning.
One last use is in matching problems. These are very important problems in graph theory, and one way to solve these is to use the Hungarian algorithm which is what i shall write an article on soon.

Well that is the basics of bipartite graphs and i hope that you found this insightful. Until next time.