Bipartite Graph

Definition - What does Bipartite Graph mean?

A bipartite graph is a graph in which a set of graph vertices can be divided into two independent sets, and no two graph vertices within the same set are adjacent. In other words, bipartite graphs can be considered as equal to two colorable graphs. Bipartite graphs are mostly used in modeling relationships, especially between two entire separate classes of object.

A bipartite graph is also known as a bigraph.

Techopedia explains Bipartite Graph

A bipartite graph has two sets of vertices, for example A and B, with the possibility that when an edge is drawn, the connection should be able to connect between any vertex in A to any vertex in B. If the graph does not contain any odd cycle (the number of vertices in the graph is odd), then its spectrum is symmetrical. The chromatic number, which is the minimum number of colors required to color the vertices with no adjacent vertices sharing the same colors, needs to be less than or equal to two in the case of a bipartite graph. All types of acyclic graphs (graphs which have no graph cycles), are examples of bipartite graphs. A cyclic graph is considered bipartite if all the cycles involved are of even length. According to Koning’s line coloring theorem, all bipartite graphs are class 1 graphs.

Bipartite graphs are widely used in modern coding theory apart from being used in modeling relationships.

Share this:

Techopedia Deals

Connect with us

Techopedia on Linkedin
Techopedia on Linkedin
Tweat cdn.techopedia.com
"Techopedia" on Twitter


'@Techopedia'
Sign up for Techopedia's Free Newsletter!

Email Newsletter

Join thousands of others with our weekly newsletter

Resources
The 4th Era of IT Infrastructure: Superconverged Systems
The 4th Era of IT Infrastructure: Superconverged Systems:
Learn the benefits and limitations of the 3 generations of IT infrastructure – siloed, converged and hyperconverged – and discover how the 4th...
Approaches and Benefits of Network Virtualization
Approaches and Benefits of Network Virtualization:
Businesses today aspire to achieve a software-defined datacenter (SDDC) to enhance business agility and reduce operational complexity. However, the...
Free E-Book: Public Cloud Guide
Free E-Book: Public Cloud Guide:
This white paper is for leaders of Operations, Engineering, or Infrastructure teams who are creating or executing an IT roadmap.
Free Tool: Virtual Health Monitor
Free Tool: Virtual Health Monitor:
Virtual Health Monitor is a free virtualization monitoring and reporting tool for VMware, Hyper-V, RHEV, and XenServer environments.
Free 30 Day Trial – Turbonomic
Free 30 Day Trial – Turbonomic:
Turbonomic delivers an autonomic platform where virtual and cloud environments self-manage in real-time to assure application performance.