All Topics  
Bipartite graph

 

 
   Email Print
   Bookmark   Link
 

 

Bipartite graph
 
 
  Topics Bipartite graph Topic Home

In the mathematical
Mathematics

Mathematics is the study of quantity, structure, space, change, and related topics of pattern and form. Mathematicians seek out patterns whether found in numbers, space, natural science, computers, imaginary abstractions, or elsewhere....
 field of graph theory
Graph theory

In mathematics and computer science, graph theory is the study of graph : mathematical structures used to model pairwise relations between objects from a certain collection....
, 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
Disjoint sets

In mathematics, two Set are said to be disjoint if they have no element in common. For example, and are 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

In graph theory, an independent set or stable set is a set of Vertex in a graph no two of which are adjacent. That is, it is a set V of vertices such that for every two vertices in , there is no graph theory connecting the two....
s. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles
Cycle (graph theory)

Cycle in graph theory and computer science has several meanings:* A closed walk, with repeated vertex allowed. See path . * A closed path, with no other repeated vertices than the starting and ending vertices....
.

The two sets U and V may be thought of as the colors of 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....
 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.






Discussion
Ask a question about 'Bipartite graph'
Start a new discussion about 'Bipartite graph'
Answer questions from other users
Full Discussion Forum



Encyclopedia


In the mathematical
Mathematics

Mathematics is the study of quantity, structure, space, change, and related topics of pattern and form. Mathematicians seek out patterns whether found in numbers, space, natural science, computers, imaginary abstractions, or elsewhere....
 field of graph theory
Graph theory

In mathematics and computer science, graph theory is the study of graph : mathematical structures used to model pairwise relations between objects from a certain collection....
, 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
Disjoint sets

In mathematics, two Set are said to be disjoint if they have no element in common. For example, and are 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

In graph theory, an independent set or stable set is a set of Vertex in a graph no two of which are adjacent. That is, it is a set V of vertices such that for every two vertices in , there is no graph theory connecting the two....
s. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles
Cycle (graph theory)

Cycle in graph theory and computer science has several meanings:* A closed walk, with repeated vertex allowed. See path . * A closed path, with no other repeated vertices than the starting and ending vertices....
.

The two sets U and V may be thought of as the colors of 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....
 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....
: 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
Cardinality

In mathematics, the cardinality of a set is a measure of the "number of Element of the set". For example, the set A = contains 3 elements, and therefore A has a cardinality of 3....
, then G is called a balanced bipartite graph.

Examples


  • Every tree
    Tree (graph theory)

    In mathematics, more specifically graph theory, a tree is a graph in which any two Vertex are connected by exactly one path . Alternatively, any connectedness graph with no Cycle is a tree....
     is bipartite.
  • Cycle graph
    Cycle graph

    In graph theory, a cycle graph is a graph that consists of a single path , or in other words, some number of vertices connected in a closed chain....
    s with an even number of vertices are bipartite.


Testing bipartiteness

If a bipartite graph is connected
Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory. 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

Connected components are part of topology and graph theory, two related branches of mathematics.* For the graph-theoretic concept, see connected component ....
 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 theorem
Marriage theorem

Hall's theorem , also known as the marriage theorem is usually credited to mathematician Philip Hall. The theorem is a combinatorics result that gives the condition allowing the selection of a distinct element from each of a collection of subsets....
 provides a characterization of bipartite graphs which allow perfect matchings.

Bipartite graphs are extensively used in modern Coding theory
Coding theory

Coding theory is a branch of information theory, electrical engineering, digital communication, mathematics, and computer science designing efficient and reliable data transmission methods, so that redundancy in the data can be removed and errors induced by a noisy channel can be corrected....
, 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, where they enable 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 specify 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 discrete distributed systems. A Petri net is a directed bipartite graph, in which the nodes represent transitions , places , and directed arcs ....
 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 which are invariant under projective transformations. The field of projective geometry is itself divided into many subfields, two examples of which are projective algebraic geometry and projective differential geometry ....
, Levi graph
Levi graph

In combinatorics 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 every incidence between a point and a line....
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 consists of a finite set of points, and a finite set 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....
.

Properties


  • A graph is bipartite if and only if
    If and only if

    If and only if, in logic and fields that rely on it such as mathematics and philosophy, is a biconditional logical connective between statements....
     it does not contain an odd cycle. Therefore, a bipartite graph cannot contain a clique
    Clique (graph theory)

    In graph theory, a clique in an undirected graph G is a set of vertex V such that for every two vertices in V, there exists an Edge connecting the two....
     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
    König's theorem (graph theory)

    In the mathematics area of graph theory, K?nig's theorem 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 graph
    Perfect graph

    In graph theory, a perfect graph is a graph in which the Graph coloring of every induced subgraph equals the Glossary of graph theory#Cliques of that subgraph....
    .


See also


  • Complete bipartite graph
    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....
  • Dulmage-Mendelsohn Decomposition
    Dulmage-Mendelsohn decomposition

    In graph theory, the Dulmage-Mendelsohn decomposition is a method used to create a maximal matching on a bipartite graph.It has been used to partition meshes in Finite Element Analysis, and to determine specified, underspecified and overspecified equations in systems of nonlinear equations....
  • Adjacency matrix of a bipartite graph
  • Record linkage
    Record linkage

    Record linkage refers to the task of finding entries that refer to the same entity in two or more files. Record linkage is an appropriate technique when you have to join data sets that do not have a unique Relational model in common....


External links

  • :