
In the
mathematical
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
field of
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, a bipartite graph (or bigraph) is a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discret ...
whose
vertices can be divided into two
disjoint and
independent sets and
, that is, every
edge
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* Edge device, an entry point to a computer network
* Adobe Edge, a graphical development application
* Microsoft Edge, a web browser developed by ...
connects a
vertex in
to one in
. Vertex sets
and
are usually called the ''parts'' of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length
cycles.
The two sets
and
may be thought of as a
coloring of the graph with two colors: if one colors all nodes in
blue, and all nodes in
red, 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 non-bipartite graph, such as a
triangle
A triangle is a polygon with three corners and three sides, one of the basic shapes in geometry. The corners, also called ''vertices'', are zero-dimensional points while the sides connecting them, also called ''edges'', are one-dimension ...
: after one node is colored blue and another red, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color.
One often writes
to denote a bipartite graph whose partition has the parts
and
, with
denoting the edges of the graph. If a bipartite graph is not
connected, it may have more than one bipartition; in this case, the
notation is helpful in specifying one particular bipartition that may be of importance in an application. If
, that is, if the two subsets have equal
cardinality
The thumb is the first digit of the hand, next to the index finger. When a person is standing in the medical anatomical position (where the palm is facing to the front), the thumb is the outermost digit. The Medical Latin English noun for thum ...
, then
is called a ''balanced'' bipartite graph.
[, p. 7.] If all vertices on the same side of the bipartition have the same
degree, then
is called
biregular.
Examples
When modelling
relations between two different classes of objects, bipartite graphs very often arise naturally. For instance, a graph of football players and clubs, with an edge between a player and a club if the player has played for that club, is a natural example of an ''affiliation network'', a type of bipartite graph used in
social network analysis
Social network analysis (SNA) is the process of investigating social structures through the use of networks and graph theory. It characterizes networked structures in terms of ''nodes'' (individual actors, people, or things within the network) ...
.
Another example where bipartite graphs appear naturally is in the (
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
) railway optimization problem, in which the input is a schedule of trains and their stops, and the goal is to find a set of train stations as small as possible such that every train visits at least one of the chosen stations. This problem can be modeled as a
dominating set
In graph theory, a dominating set for a Graph (discrete mathematics), graph is a subset of its vertices, such that any vertex of is in , or has a neighbor in . The domination number is the number of vertices in a smallest dominating set for ...
problem in a bipartite graph that has a vertex for each train and each station and an edge for each pair of a station and a train that stops at that station.
A third example is in the academic field of numismatics. Ancient coins are made using two positive impressions of the design (the obverse and reverse). The charts numismatists produce to represent the production of coins are bipartite graphs.
More abstract examples include the following:
* Every
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...
is bipartite.
*
Cycle graph
In 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 (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...
s with an even number of vertices are bipartite.
* Every
planar graph
In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
whose
faces all have even length is bipartite. Special cases of this are
grid graph
In graph theory, a lattice graph, mesh graph, or grid graph is a Graph (discrete mathematics), graph whose graph drawing, drawing, Embedding, embedded in some Euclidean space , forms a regular tiling. This implies that the group (mathematics), g ...
s and
squaregraphs, in which every inner face consists of 4 edges and every inner vertex has four or more neighbors.
* The
complete bipartite graph
In 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..Electronic edition page 17.
Graph theory ...
on ''m'' and ''n'' vertices, denoted by ''K
n,m'' is the bipartite graph
, where ''U'' and ''V'' are disjoint sets of size ''m'' and ''n'', respectively, and ''E'' connects every vertex in ''U'' with all vertices in ''V''. It follows that ''K
m,n'' has ''mn'' edges. Closely related to the complete bipartite graphs are the
crown graphs, formed from complete bipartite graphs by removing the edges of a
perfect matching.
*
Hypercube graph
In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cubical graph, cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube.
has ...
s,
partial cubes, and
median graphs are bipartite. In these graphs, the vertices may be labeled by
bitvector
A bit array (also known as bitmask, bit map, bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level p ...
s, in such a way that two vertices are adjacent if and only if the corresponding bitvectors differ in a single position. A bipartition may be formed by separating the vertices whose bitvectors have an even number of ones from the vertices with an odd number of ones. Trees and squaregraphs form examples of median graphs, and every median graph is a partial cube.
Properties
Characterization
Bipartite graphs may be characterized in several different ways:
* An undirected graph is bipartite
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
it does not contain an odd
cycle.
* A graph is bipartite if and only if it is 2-colorable, (i.e. its
chromatic number
In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...
is less than or equal to 2).
* A graph is bipartite if and only if every edge belongs to an odd number of
bonds, minimal subsets of edges whose removal increases the number of components of the graph.
* A graph is bipartite if and only if the
spectrum
A spectrum (: spectra or spectrums) is a set of related ideas, objects, or properties whose features overlap such that they blend to form a continuum. The word ''spectrum'' was first used scientifically in optics to describe the rainbow of co ...
of the graph is symmetric.
Kőnig's theorem and perfect graphs
In bipartite graphs, the size of
minimum vertex cover is equal to the size of the
maximum matching; this is
Kőnig's theorem. An alternative and equivalent form of this theorem is that the size of the
maximum independent set plus the size of the maximum matching is equal to the number of vertices. In any graph without
isolated vertices the size of the
minimum edge cover plus the size of a maximum matching equals the number of vertices. Combining this equality with Kőnig's theorem leads to the facts that, in bipartite graphs, the size of the minimum edge cover is equal to the size of the maximum independent set, and the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices.
Another class of related results concerns
perfect graph
In graph theory, a perfect graph is a Graph (discrete mathematics), graph in which the Graph coloring, chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic nu ...
s: every bipartite graph, the
complement of every bipartite graph, the
line graph
In the mathematics, mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edge (graph theory), edges of . is constructed in the following way: for each edge i ...
of every bipartite graph, and the complement of the line graph of every bipartite graph, are all perfect. Perfection of bipartite graphs is easy to see (their
chromatic number
In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...
is two and their
maximum clique size is also two) but perfection of the
complements of bipartite graphs is less trivial, and is another restatement of Kőnig's theorem. This was one of the results that motivated the initial definition of perfect graphs. Perfection of the complements of line graphs of perfect graphs is yet another restatement of Kőnig's theorem, and perfection of the line graphs themselves is a restatement of an earlier theorem of Kőnig, that every bipartite graph has an
edge coloring using a number of colors equal to its maximum degree.
According to the
strong perfect graph theorem, the perfect graphs have a
forbidden graph characterization
In graph theory, a branch of mathematics, many important families of Graph (discrete mathematics), graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family whic ...
resembling that of bipartite graphs: a graph is bipartite if and only if it has no odd cycle as a subgraph, and a graph is perfect if and only if it has no odd cycle or its
complement as an
induced subgraph
In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges, from the original graph, connecting pairs of vertices in that subset.
Definition
Formally, let G=(V,E) ...
. The bipartite graphs, line graphs of bipartite graphs, and their complements form four out of the five basic classes of perfect graphs used in the proof of the strong perfect graph theorem. It follows that any subgraph of a bipartite graph is also bipartite because it cannot gain an odd cycle.
Degree
For a vertex, the number of adjacent vertices is called the
degree of the vertex and is denoted
. The
degree sum formula for a bipartite graph states that
:
The degree sequence of a bipartite graph is the pair of lists each containing the degrees of the two parts
and
. For example, the complete bipartite graph ''K''
3,5 has degree sequence
.
Isomorphic
In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...
bipartite graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a bipartite graph; in some cases, non-isomorphic bipartite graphs may have the same degree sequence.
The
bipartite realization problem is the problem of finding a simple bipartite graph with the degree sequence being two given lists of natural numbers. (Trailing zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the digraph.)
Relation to hypergraphs and directed graphs
The
biadjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
of a bipartite graph
is a
(0,1) matrix of size
that has a one for each pair of adjacent vertices and a zero for nonadjacent vertices. Biadjacency matrices may be used to describe equivalences between bipartite graphs, hypergraphs, and directed graphs.
A
hypergraph
In mathematics, a hypergraph is a generalization of a Graph (discrete mathematics), graph in which an graph theory, edge can join any number of vertex (graph theory), vertices. In contrast, in an ordinary graph, an edge connects exactly two vert ...
is a combinatorial structure that, like an undirected graph, has vertices and edges, but in which the edges may be arbitrary sets of vertices rather than having to have exactly two endpoints. A bipartite graph
may be used to model a hypergraph in which is the set of vertices of the hypergraph, is the set of hyperedges, and contains an edge from a hypergraph vertex to a hypergraph edge exactly when is one of the endpoints of . Under this correspondence, the biadjacency matrices of bipartite graphs are exactly the
incidence matrices of the corresponding hypergraphs. As a special case of this correspondence between bipartite graphs and hypergraphs, any
multigraph
In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by mor ...
(a graph in which there may be two or more edges between the same two vertices) may be interpreted as a hypergraph in which some hyperedges have equal sets of endpoints, and represented by a bipartite graph that does not have multiple adjacencies and in which the vertices on one side of the bipartition all have
degree two.
A similar reinterpretation of adjacency matrices may be used to show a one-to-one correspondence between
directed graphs (on a given number of labeled vertices, allowing self-loops) and balanced bipartite graphs, with the same number of vertices on both sides of the bipartition. For, the adjacency matrix of a directed graph with vertices can be any
(0,1) matrix of size
, which can then be reinterpreted as the adjacency matrix of a bipartite graph with vertices on each side of its bipartition. In this construction, the bipartite graph is the
bipartite double cover of the directed graph.
Algorithms
Testing bipartiteness
It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) in
linear time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...
, using
depth-first search
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible al ...
(DFS). The main idea is to assign to each vertex the color that differs from the color of its parent in the DFS forest, assigning colors in a
preorder traversal of the depth-first-search forest. This will necessarily provide a two-coloring of the
spanning forest
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
consisting of the edges connecting vertices to their parents, but it may not properly color some of the non-forest edges. In a DFS forest, one of the two endpoints of every non-forest edge is an ancestor of the other endpoint, and when the depth first search discovers an edge of this type it should check that these two vertices have different colors. If they do not, then the path in the forest from ancestor to descendant, together with the miscolored edge, form an odd cycle, which is returned from the algorithm together with the result that the graph is not bipartite. However, if the algorithm terminates without detecting an odd cycle of this type, then every edge must be properly colored, and the algorithm returns the coloring together with the result that the graph is bipartite.
Alternatively, a similar procedure may be used with
breadth-first search
Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next dept ...
in place of DFS. Again, each node is given the opposite color to its parent in the search forest, in breadth-first order. If, when a vertex is colored, there exists an edge connecting it to a previously-colored vertex with the same color, then this edge together with the paths in the breadth-first search forest connecting its two endpoints to their
lowest common ancestor
In graph theory and computer science, the lowest common ancestor (LCA) (also called least common ancestor) of two nodes and in a Tree (graph theory), tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both and a ...
forms an odd cycle. If the algorithm terminates without finding an odd cycle in this way, then it must have found a proper coloring, and can safely conclude that the graph is bipartite.
For the
intersection graphs of
line segment
In geometry, a line segment is a part of a line (mathematics), straight line that is bounded by two distinct endpoints (its extreme points), and contains every Point (geometry), point on the line that is between its endpoints. It is a special c ...
s or other simple shapes in the
Euclidean plane
In mathematics, a Euclidean plane is a Euclidean space of Two-dimensional space, dimension two, denoted \textbf^2 or \mathbb^2. It is a geometric space in which two real numbers are required to determine the position (geometry), position of eac ...
, it is possible to test whether the graph is bipartite and return either a two-coloring or an odd cycle in time
, even though the graph itself may have up to
edges.
Odd cycle transversal
Odd cycle transversal is an
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
ic problem that asks, given a graph ''G'' = (''V'',''E'') and a number ''k'', whether there exists a set of ''k'' vertices whose removal from ''G'' would cause the resulting graph to be bipartite.
The problem is
fixed-parameter tractable, meaning that there is an algorithm whose running time can be bounded by a polynomial function of the size of the graph multiplied by a larger function of ''k''.
[.] The name ''odd cycle transversal'' comes from the fact that a graph is bipartite if and only if it has no odd
cycles. Hence, to delete vertices from a graph in order to obtain a bipartite graph, one needs to "hit all odd cycle", or find a so-called odd cycle
transversal set. In the illustration, every odd cycle in the graph contains the blue (the bottommost) vertices, so removing those vertices kills all odd cycles and leaves a bipartite graph.
The ''edge bipartization'' problem is the algorithmic problem of deleting as few edges as possible to make a graph bipartite and is also an important problem in graph modification algorithmics. This problem is also
fixed-parameter tractable, and can be solved in time
,
where ''k'' is the number of edges to delete and ''m'' is the number of edges in the input graph.
Matching
A
matching in a graph is a subset of its edges, no two of which share an endpoint.
Polynomial time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
algorithms are known for many algorithmic problems on matchings, including
maximum matching (finding a matching that uses as many edges as possible),
maximum weight matching, and
stable marriage. In many cases, matching problems are simpler to solve on bipartite graphs than on non-bipartite graphs, and many matching algorithms such as the
Hopcroft–Karp algorithm for maximum cardinality matching work correctly only on bipartite inputs.
As a simple example, suppose that a set
of people are all seeking jobs from among a set
of jobs, with not all people suitable for all jobs. This situation can be modeled as a bipartite graph
where an edge connects each job-seeker with each suitable job. A
perfect matching describes a way of simultaneously satisfying all job-seekers and filling all jobs;
Hall's marriage theorem provides a characterization of the bipartite graphs which allow perfect matchings. The
National Resident Matching Program
The National Resident Matching Program (NRMP), also called The Match, is a United States–based private non-profit non-governmental organization created in 1952 to place U.S. Medical education in the United States, medical school students into res ...
applies graph matching methods to solve this problem for
U.S. medical student job-seekers and
hospital residency jobs.
The
Dulmage–Mendelsohn decomposition
In graph theory, the Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a per ...
is a structural decomposition of bipartite graphs that is useful in finding maximum matchings.
Additional applications
Bipartite graphs are extensively used in modern
coding theory
Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and computer data storage, data sto ...
, especially to decode
codewords received from the channel.
Factor graphs and
Tanner graph {{Short description, Bipartite graph in coding theory
In coding theory, a Tanner graph is a bipartite graph that can be used to express constraints (typically equations) that specify an error correcting codes, error correcting code. Tanner graphs p ...
s are examples of this. A Tanner graph is a bipartite graph in which the vertices on one side of the bipartition represent digits of a codeword, and the vertices on the other side represent combinations of digits that are expected to sum to zero in a codeword without errors. A factor graph is a closely related
belief network used for probabilistic decoding of
LDPC and
turbo codes.
In computer science, a
Petri net
A Petri net, also known as a place/transition net (PT net), is one of several mathematical modeling languages for the description of distributed systems. It is a class of discrete event dynamic system. A Petri net is a directed bipartite graph t ...
is a mathematical modeling tool used in analysis and simulations of concurrent systems. A system is modeled 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
In mathematics, projective geometry is the study of geometric properties that are invariant with respect to projective transformations. This means that, compared to elementary Euclidean geometry, projective geometry has a different setting (''p ...
,
Levi graphs are a form of bipartite graph used to model the incidences between points and lines in a
configuration
Configuration or configurations may refer to:
Computing
* Computer configuration or system configuration
* Configuration file, a software file used to configure the initial settings for a computer program
* Configurator, also known as choice board ...
. Corresponding to the geometric property of points and lines that every two lines meet in at most one point and every two points be connected with a single line, Levi graphs necessarily do not contain any cycles of length four, so their
girth
Girth may refer to:
Mathematics
* Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space
* Girth (geometry), the perimeter of a parallel projection of a shape
* Girth ...
must be six or more.
[.]
See also
*
Bipartite dimension, the minimum number of complete bipartite graphs whose union is the given graph
*
Bipartite double cover, a way of transforming any graph into a bipartite graph by doubling its vertices
*
Bipartite hypergraph, a generalization of bipartiteness to
hypergraph
In mathematics, a hypergraph is a generalization of a Graph (discrete mathematics), graph in which an graph theory, edge can join any number of vertex (graph theory), vertices. In contrast, in an ordinary graph, an edge connects exactly two vert ...
s.
*
Bipartite matroid, a class of matroids that includes the
graphic matroid
In the mathematical theory of Matroid theory, matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the tree (graph theory), forests in a given finite undirected graph. The dual matr ...
s of bipartite graphs
*
Bipartite network projection, a weighting technique for compressing information about bipartite networks
*
Convex bipartite graph, a bipartite graph whose vertices can be ordered so that the vertex neighborhoods are contiguous
*
Multipartite graph, a generalization of bipartite graphs to more than two subsets of vertices
*
Parity graph, a generalization of bipartite graphs in which every two
induced path
In the mathematical area of graph theory, an induced path in an undirected graph is a path that is an induced subgraph of . That is, it is a sequence of vertices in such that each two adjacent vertices in the sequence are connected by an edge ...
s between the same two points have the same parity
*
Quasi-bipartite graph, a type of Steiner tree problem instance in which the terminals form an independent set, allowing approximation algorithms that generalize those for bipartite graphs
*
Split graph, a graph in which the vertices can be partitioned into two subsets, one of which is independent and the other of which is a clique
*
Zarankiewicz problem on the maximum number of edges in a bipartite graph with forbidden subgraphs
References
External links
*
Information System on Graph Classes and their Inclusions* {{mathworld , title = Bipartite Graph , urlname = BipartiteGraph , mode=cs2
Bipartite graphs in systems biology and medicine
Graph families
Parity (mathematics)