Bipartite graph

From Wikipedia, the free encyclopedia

Example of bipartite graph

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets Failed to parse (Missing texvc executable; please see math/README to configure.): V_1

and Failed to parse (Missing texvc executable; please see math/README to configure.): V_2
such that every edge connects a vertex in Failed to parse (Missing texvc executable; please see math/README to configure.): V_1
and one in Failed to parse (Missing texvc executable; please see math/README to configure.): V_2

that is, there is no edge between two vertices in the same set.

1 Intuitive definition
2 Mathematical definition
3 Applications
4 Examples
5 Properties
6 See also
7 External links

Intuitive definition

It is possible to color the nodes of a bipartite graph red and blue such that no edge exists between like colors. For example, this is impossible in the case of a fully connected graph with 3 vertices (a triangle): after one node is colored red and another blue, the remaining one is connected to both but must have the same color as either.

Mathematical definition

A simple undirected graph Failed to parse (Missing texvc executable; please see math/README to configure.): G\ = (V,\ E)

is called bipartite if there exists a partition Failed to parse (Missing texvc executable; please see math/README to configure.): V = V_1 \cup V_2
of the vertex set so that every edge in E is of the form v₁v₂ for some v₁ in V₁ and v₂ in V₂.  One often writes Failed to parse (Missing texvc executable; please see math/README to configure.): G\ = (V_1 + V_2,\ E)
to denote a bipartite graph whose partition has the parts Failed to parse (Missing texvc executable; please see math/README to configure.): V_1
and Failed to parse (Missing texvc executable; please see math/README to configure.): V_2

. If Failed to parse (Missing texvc executable; please see math/README to configure.): |V_1| = |V_2| , that is, if the number of elements in Failed to parse (Missing texvc executable; please see math/README to configure.): V_1

is equal to the number of elements in Failed to parse (Missing texvc executable; please see math/README to configure.): V_2

, then Failed to parse (Missing texvc executable; please see math/README to configure.): G

is called a balanced bipartite graph.

If the graph is connected, its bipartition can be defined by the parity of the distances from any arbitrarily chosen vertex v: one subset consists of the vertices at even distance to v and the other subset consists of the vertices at odd distance to v.

Applications

Bipartite graphs are useful for modelling matching problems. An example of bipartite graph is a job matching problem. Suppose we have a set P of people and a set J of jobs, with not all people suitable for all jobs. We can model this as a graph with P + J the set of vertices. If a person Failed to parse (Missing texvc executable; please see math/README to configure.): p_i

is suitable for a certain job Failed to parse (Missing texvc executable; please see math/README to configure.): j_i
there is an edge between Failed to parse (Missing texvc executable; please see math/README to configure.): p_i
and Failed to parse (Missing texvc executable; please see math/README to configure.): j_i
in the graph. The marriage theorem provides a characterization of bipartite graphs which allow perfect matchings.

Bipartite graphs are extensively used in modern Coding theory, especially to decode codewords received from the channel. Factor graphs and Tanner graphs are examples of this.

In computer science, a Petri net is a mathematical modelling tool used in analysis and simulations of concurrent systems. A system is modelled as a bipartite directed graph with two sets of nodes: A set of "place" nodes that contain resources, and a set of "event" nodes which generate and/or consume resources. There are additional constraints on the nodes and edges that constrain the behavior of the system. Petri nets utilize the properties of bipartite directed graphs and other properties to allow mathematical proofs of the behavior of systems while also allowing easy implementation of simulations of the system.

Examples

Every tree is bipartite.
Cycle graphs with an even number of vertices are bipartite.

Properties

Image:RecursiveEvenBipartite.svg

Constructing a bipartition on a graph without odd cycles

A graph is bipartite if and only if it does not contain an odd cycle. Therefore, a bipartite graph cannot contain a clique of size 3 or more.
A graph is bipartite if and only if it is 2-colorable, (i.e. its chromatic number is less than or equal to 2).
The size of minimum vertex cover is equal to the size of the maximum matching (König's theorem).
The size of the maximum independent set plus the size of the maximum matching is equal to the number of vertices.
For a connected bipartite graph the size of the minimum edge cover is equal to the size of the maximum independent set.
For a connected bipartite graph the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices.
Every bipartite graph is a perfect graph.