Bipartite graph

Bipartite graph

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 sets. 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 the colors of 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.

Examples

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

Testing bipartiteness

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.

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 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.

In projective geometry, Levi graphs are a form of bipartite graph used to model the incidences between points and lines in a configuration.

Properties

* 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.

ee also

* Complete bipartite graph
* Dulmage-Mendelsohn Decomposition

External links

* [http://wwwteo.informatik.uni-rostock.de/isgci/index.html Information System on Graph Class Inclusions] : [http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_69.html bipartite graph]

*


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Complete bipartite graph — A complete bipartite graph with m = 5 and n = 3 Vertices n + m Edges mn …   Wikipedia

  • Convex bipartite graph — In the mathematical field of graph theory, a convex bipartite graph is a bipartite graph with specific properties. A bipartite graph, (U ∪ V, E), is said to be convex over the vertex set U if U can be enumerated such that for all… …   Wikipedia

  • Quasi-bipartite graph — In the mathematical field of graph theory, an instance of the Steiner tree problem (consisting of an undirected graph G and a set R of terminal vertices that must be connected to each other) is said to be quasi bipartite if the non terminal… …   Wikipedia

  • Bipartite — means having two parts, or an agreement between two parties. More specifically, it may refer to any of the following:* 2 (number)In mathematics: * Bipartite graph * Bipartite Cubic, a type of Cubic function * Bipartite matching, a type of… …   Wikipedia

  • Bipartite dimension — In the mathematical field of graph theory, the bipartite dimension of an graph G=(V,E) is the minimum number of bicliques, that is, complete bipartite subgraphs, needed to cover all edges in E. A collection of bicliques covering all edges in G is …   Wikipedia

  • Graph factorization — Not to be confused with Factor graph. 1 factorization of Desargues graph: each color class is a 1 factor …   Wikipedia

  • Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges …   Wikipedia

  • graph theory — Math. the branch of mathematics dealing with linear graphs. [1965 70] * * * Mathematical theory of networks. A graph consists of nodes (also called points or vertices) and edges (lines) connecting certain pairs of nodes. An edge that connects a… …   Universalium

  • 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 …   Wikipedia

  • Graph isomorphism — In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is commonly… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”