Bipartite graph
From Free net encyclopedia
In the mathematical field of graph theory, a bipartite graph is a special graph where the set of vertices can be divided into two disjoint sets with two vertices of the same set never sharing an edge.
Contents |
Definitions
A simple undirected graph <math>G\ := (V,\ E)</math> is called bipartite if there exists a partition of the vertex set <math>V = V_1 \cup V_2</math> so that both <math>V_1</math> and <math>V_2</math> are independent sets. One often writes <math>G\ := (V_1 + V_2,\ E)</math> to denote a bipartite graph whose partition has the parts <math>V_1</math> and <math>V_2</math>. If <math>|V_1| = |V_2|</math>, that is, if the number of elements in <math>V_1</math> is equal to the number of number of elements in <math>V_2</math>, then <math>G</math> is called a balanced bipartite graph.
Applications
Bipartite graphs are useful for modelling matching problems. An example of bipartite graph is a job matching problem. Suppose we have a set of people P and a set of jobs J, with not all people suitable for all jobs. We can model this as a graph with P + J the set of vertices. If a person <math>p_i</math> is suitable for a certain job <math>j_i</math> there is an edge between <math>p_i</math> and <math>j_i</math> 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.
Examples
- every tree is bipartite
- cycle graphs with an even number of vertices are bipartite
Properties
- a graph is bipartite if and only if it does not contain an odd cycle
- the size of minimum vertex cover is equal to the size of the maximum matching
- 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.
- a graph is bipartite if and only if it is two colorable.
See also
de:Bipartiter Graph it:Grafo bipartito he:גרף דו צדדי pl:Graf dwudzielny th:กราฟสองส่วน vi:Đồ thị hai phía