Bipartite

Mathematical concept in graph theory

About WikiMD: The article, Bipartite, is part of WikiMD.
WikiMD is a free medical encyclopedia and wellnesspedia moderated by medical professionals.

A bipartite graph, also known as a bigraph, is a special kind of graph in the field of graph theory. A graph is bipartite if its set of vertices can be divided into two disjoint sets such that no two graph vertices within the same set are adjacent. In other words, every edge connects a vertex in one set to a vertex in the other set.

Definition

Formally, a graph \( G = (V, E) \) is bipartite if the vertex set \( V \) can be partitioned into two disjoint sets \( U \) and \( W \) such that every edge in \( E \) has one endpoint in \( U \) and the other endpoint in \( W \). This can be written as: \[ U \cup W = V \] \[ U \cap W = \emptyset \] \[ \forall (u, v) \in E, u \in U \text{ and } v \in W \]

Properties

• **Two-colorable**: A bipartite graph is two-colorable, meaning its vertices can be colored using two colors such that no two adjacent vertices share the same color.
• **No odd-length cycles**: A graph is bipartite if and only if it contains no odd-length cycles. This is a direct consequence of the two-colorability property.
• **Complete bipartite graph**: A complete bipartite graph, denoted as \( K_{m,n} \), is a bipartite graph where every vertex in set \( U \) is connected to every vertex in set \( W \).

Applications

Bipartite graphs have numerous applications in various fields:

• **Matching problems**: In combinatorial optimization, bipartite graphs are used to model matching problems, such as the assignment problem and the maximum bipartite matching problem.
• **Network flow**: Bipartite graphs are used in network flow problems, particularly in the Ford-Fulkerson algorithm for computing the maximum flow in a flow network.
• **Social networks**: In social network analysis, bipartite graphs can represent relationships between two different classes of entities, such as people and the events they attend.

Examples

• **Bipartite graph in biology**: In ecology, bipartite graphs can represent interactions between two different types of species, such as plants and their pollinators.
• **Bipartite graph in computer science**: In computer science, bipartite graphs are used in database systems to model relationships between different types of entities, such as customers and products.

Related Concepts

• Graph theory
• Matching (graph theory)
• Network flow
• Two-colorable graph
• Complete bipartite graph

See also

• Graph (discrete mathematics)
• Cycle (graph theory)
• Ford-Fulkerson algorithm
• Social network analysis