Bipartite graph
Encyclopedia
In the mathematical
field of graph theory
, a bipartite graph (or bigraph) is a graph
whose vertices
can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent set
s. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles
.
The two sets U and V may be thought of as a coloring
of the graph with two colors: if we color all nodes in U blue, and all nodes in V green, each edge has endpoints of differing colors, as is required in the graph coloring problem. In contrast, such a coloring is impossible in the case of a nonbipartite graph, such as a triangle
: after one node is colored blue and another green, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color.
One often writes G = (U, V, E) to denote a bipartite graph whose partition has the parts U and V. If |U| =|V|, that is, if the two subsets have equal cardinality, then G is called a balanced bipartite graph.
If a bipartite 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.
Thus, one may efficiently test whether a graph is bipartite by using this parity technique to assign vertices to the two subsets U and V, separately within each connected component
of the graph, and then examine each edge to verify that it has endpoints assigned to different subsets.
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 graph
s and Tanner graph
s 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.
In projective geometry
, Levi graph
s are a form of bipartite graph used to model the incidences between points and lines in a configuration
.
. Given a multigraph M, take U as the vertex set of M and take V as the edge set of M. Then join an element of V to precisely the two elements of U which are the ends of that edge in M. Thus every multigraph is described entirely by a bipartite graph which is one-sided regular of degree 2, and vice versa.
Similarly, every directed hypergraph
can be represented as a bipartite digraph. Take U as the vertex set in the hypergraph, and V as set of edges. For each
and 
, connect u to v if the hypergraph edge v contains u as an input, and connect v to u if v contains u as an output.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
field of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a bipartite graph (or bigraph) is a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
whose vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent set
Independent set (graph theory)
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
s. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
.
The two sets U and V may be thought of as a coloring
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
of the graph with two colors: if we color all nodes in U blue, and all nodes in V green, each edge has endpoints of differing colors, as is required in the graph coloring problem. In contrast, such a coloring is impossible in the case of a nonbipartite graph, such as a triangle
Gallery of named graphs
Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer. A famous example is the Petersen graph, a concrete graph on 10 vertices that appears as a minimal example or counterexample in many different...
: after one node is colored blue and another green, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color.
One often writes G = (U, V, E) to denote a bipartite graph whose partition has the parts U and V. If |U| =|V|, that is, if the two subsets have equal cardinality, then G is called a balanced bipartite graph.
Examples
- Any graph with no odd cycles is bipartite. As a consequence of this:
- Every treeTree (graph theory)In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
is bipartite. - Cycle graphCycle graphIn graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
s with an even number of vertices are bipartite. - Any planar graphPlanar graphIn graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
where all the faces in its planar representation consist of an even number of edges is bipartite. Special cases of this are grid graphs and squaregraphSquaregraphIn graph theory, a branch of mathematics, a squaregraph is a type of undirected graph that can be drawn in the plane in such a way that every bounded face is a quadrilateral and every vertex with three or fewer neighbors is incident to an unbounded face....
s, in which every inner face consists of 4 edges.
- Every tree
Testing bipartiteness
Connectivity (graph theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It is closely related to the theory of network flow problems...
, 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.
Thus, one may efficiently test whether a graph is bipartite by using this parity technique to assign vertices to the two subsets U and V, separately within each connected component
Connected component (graph theory)
In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three connected components...
of the graph, and then examine each edge to verify that it has endpoints assigned to different subsets.
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 bipartite graph (P, J, E). If a person px is suitable for a certain job jy there is an edge between px and jy in the graph. The marriage theoremMarriage theorem
In mathematics, Hall's marriage theorem is a combinatorial result that gives the condition allowing the selection of a distinct element from each of a collection of finite sets...
provides a characterization of bipartite graphs which allow perfect matchings.
Bipartite graphs are extensively used in modern Coding theory
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...
, especially to decode codewords received from the channel. Factor graph
Factor graph
In probability theory and its applications, a factor graph is a particular type of graphical model, with applications in Bayesian inference, that enables efficient computation of marginal distributions through the sum-product algorithm...
s and Tanner graph
Tanner graph
A Tanner graph is a bipartite graph used to state constraints or equations which specify error correcting codes. In coding theory, Tanner graphs are used to construct longer codes from smaller ones...
s are examples of this.
In computer science, a Petri net
Petri net
A Petri net is one of several mathematical modeling languages for the description of distributed systems. A Petri net is a directed bipartite graph, in which the nodes represent transitions and places...
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.
In projective geometry
Projective geometry
In mathematics, projective geometry is the study of geometric properties that are invariant under projective transformations. This means that, compared to elementary geometry, projective geometry has a different setting, projective space, and a selective set of basic geometric concepts...
, Levi graph
Levi graph
In combinatorial mathematics, a Levi graph or incidence graph is a bipartite graph associated with an incidence structure. From a collection of points and lines in an incidence geometry or a projective configuration, we form a graph with one vertex per point, one vertex per line, and an edge for...
s are a form of bipartite graph used to model the incidences between points and lines in a configuration
Configuration (geometry)
In mathematics, specifically projective geometry, a configuration in the plane consists of a finite set of points, and a finite arrangement of lines, such that each point is incident to the same number of lines and each line is incident to the same number of points.Although certain specific...
.
Modelling multigraphs and hypergraphs
Bipartite graphs can model the more general multigraphMultigraph
In mathematics, a multigraph or pseudograph is a graph which is permitted to have multiple edges, , that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge....
. Given a multigraph M, take U as the vertex set of M and take V as the edge set of M. Then join an element of V to precisely the two elements of U which are the ends of that edge in M. Thus every multigraph is described entirely by a bipartite graph which is one-sided regular of degree 2, and vice versa.
Similarly, every directed hypergraph
Hypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...
can be represented as a bipartite digraph. Take U as the vertex set in the hypergraph, and V as set of edges. For each
and , connect u to v if the hypergraph edge v contains u as an input, and connect v to u if v contains u as an output.Properties
- A graph is bipartite if and only ifIf and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
it does not contain an odd cycle. Therefore, a bipartite graph cannot contain a cliqueClique (graph theory)In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
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 theoremKönig's theorem (graph theory)In the mathematical area of graph theory, König's theorem, proved by Dénes Kőnig in 1931, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs...
). - 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 graphPerfect graphIn graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....
. - The spectrumSpectral graph theoryIn mathematics, spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated to the graph, such as its adjacency matrix or Laplacian matrix....
of a graph is symmetric if and only if it's a bipartite graph.
See also
- Complete bipartite graphComplete bipartite graphIn the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
- Dulmage–Mendelsohn decomposition
- Adjacency matrix of a bipartite graph
- Record linkageRecord linkageRecord linkage refers to the task of finding records in a data set that refer to the same entity across different data sources...