HOME

TheInfoList



OR:

In the mathematical field of
graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a
vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet *Vertex (computer graphics), a data structure that describes the position ...
in U to one in V. Vertex sets U and V 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 U and V may be thought of as a coloring of the graph with two colors: if one colors all nodes in U blue, and all nodes in V 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: 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 G=(U,V,E) to denote a bipartite graph whose partition has the parts U and V, with E denoting the edges of the graph. If a bipartite graph is not connected, it may have more than one bipartition; in this case, the (U,V,E) notation is helpful in specifying one particular bipartition that may be of importance in an application. If , U, =, V, , that is, if the two subsets have equal cardinality, then G is called a ''balanced'' bipartite graph., p. 7. If all vertices on the same side of the bipartition have the same degree, then G 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. Another example where bipartite graphs appear naturally is in the ( NP-complete) 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 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 is bipartite. * Cycle graphs with an even number of vertices are bipartite. * Every planar graph whose faces all have even length is bipartite. Special cases of this are grid graphs and squaregraphs, in which every inner face consists of 4 edges and every inner vertex has four or more neighbors. * The complete bipartite graph on ''m'' and ''n'' vertices, denoted by ''Kn,m'' is the bipartite graph G = (U, V, E), 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 ''Km,n'' has ''mn'' edges. Closely related to the complete bipartite graphs are the
crown graph In graph theory, a branch of mathematics, a crown graph on vertices is an undirected graph with two sets of vertices and and with an edge from to whenever . The crown graph can be viewed as a complete bipartite graph from which the edges ...
s, formed from complete bipartite graphs by removing the edges of a
perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactl ...
. * Hypercube graphs, partial cubes, and median graphs are bipartite. In these graphs, the vertices may be labeled by bitvectors, 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: * A graph is bipartite
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bic ...
it does not contain an odd cycle. * A graph is bipartite if and only if it is 2-colorable, (i.e. its chromatic number 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 of the graph is symmetric.


Kőnig's theorem and perfect graphs

In bipartite graphs, the size of
minimum vertex cover In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optim ...
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 In graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. In computer science, the minimum edge cover problem is the problem of finding an edge cover of minimum siz ...
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 graphs: every bipartite graph, the complement of every bipartite graph, the line graph 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 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 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. 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.


Degree

For a vertex, the number of adjacent vertices is called the degree of the vertex and is denoted \deg(v). The degree sum formula for a bipartite graph states that :\sum_ \deg(v) = \sum_ \deg(u) = , E, \, . The degree sequence of a bipartite graph is the pair of lists each containing the degrees of the two parts U and V. For example, the complete bipartite graph ''K''3,5 has degree sequence (5,5,5),(3,3,3,3,3). Isomorphic 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 The bipartite realization problem is a classical decision problem in graph theory, a branch of combinatorics. Given two finite sequences (a_1,\dots,a_n) and (b_1,\dots,b_n) of natural numbers, the problem asks whether there is a labeled simple bi ...
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 of a bipartite graph (U,V,E) is a (0,1) matrix of size , U, \times, V, 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 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 (U,V,E) 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 (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 n\times n, 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, using depth-first search. The main idea is to assign to each vertex the color that differs from the color of its parent in the depth-first search forest, assigning colors in a
preorder traversal In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. ...
of the depth-first-search forest. This will necessarily provide a two-coloring of the spanning forest consisting of the edges connecting vertices to their parents, but it may not properly color some of the non-forest edges. In a depth-first search 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 in place of depth-first search. 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 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 n line segments or other simple shapes in the Euclidean plane, it is possible to test whether the graph is bipartite and return either a two-coloring or an odd cycle in time O(n\log n), even though the graph itself may have up to O\left(n^2\right) edges.


Odd cycle transversal

Odd cycle transversal is an NP-complete
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
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 O\left(2^k m^2\right), 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 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 In computer science and graph theory, the maximum weight matching problem is the problem of finding, in a weighted graph, a matching in which the sum of weights is maximized. A special case of it is the assignment problem, in which the input is ...
, 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 P of people are all seeking jobs from among a set J of jobs, with not all people suitable for all jobs. This situation can be modeled as a bipartite graph (P,J,E) where an edge connects each job-seeker with each suitable job. A
perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactl ...
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 school students into residency training programs located in U ...
applies graph matching methods to solve this problem for U.S. medical student job-seekers and hospital residency jobs. The Dulmage–Mendelsohn decomposition 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, especially to decode codewords received from the channel.
Factor graph A factor graph is a bipartite graph representing the factorization of a function. In probability theory and its applications, factor graphs are used to represent factorization of a probability distribution function, enabling efficient computatio ...
s and
Tanner graph In coding theory, a Tanner graph, named after Michael Tanner, 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. Bot ...
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 A Bayesian network (also known as a Bayes network, Bayes net, belief network, or decision network) is a probabilistic graphical model that represents a set of variables and their conditional dependencies via a directed acyclic graph (DAG). Bay ...
used for probabilistic decoding of LDPC and turbo codes. In computer science, a Petri net 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, Levi graphs are a form of bipartite graph used to model the incidences between points and lines in a configuration. 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 In the mathematical fields of graph theory and combinatorial optimization, the bipartite dimension or biclique cover number of a graph ''G'' = (''V'', ''E'') is the minimum number of bicliques (that is complete bipartite subgraphs), ...
, 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 In graph theory, the term bipartite hypergraph describes several related classes of hypergraphs, all of which are natural generalizations of a bipartite graph. Property B and 2-colorability The weakest definition of bipartiteness is also called ...
, a generalization of bipartiteness to hypergraphs. * Bipartite matroid, a class of matroids that includes the graphic matroids 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 In graph theory, a parity graph is a graph in which every two induced paths between the same two vertices have the same parity: either both paths have odd length, or both have even length.
, a generalization of bipartite graphs in which every two induced paths 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 The Zarankiewicz problem, an unsolved problem in mathematics, asks for the largest possible number of edges in a bipartite graph that has a given number of vertices and has no complete bipartite subgraphs of a given size.. Reprint of 1978 Academic ...
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)