|
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 and such that no edge has both end-points in the same set.
Intuitive Definition The best way to think of a bipartite graph is one whose nodes can be colored red and blue such that no edge exists between like colors. For example, this cannot be done with a fully connected graph with 3 vertices (a triangle). (If the first node is colored red and the second one is colored blue, what happens to the third?) Mathematical Definition A simple undirected graph is called bipartite if there exists a partition of the vertex set so that both and are independent sets. One often writes to denote a bipartite graph whose partition has the parts and . If , that is, if the number of elements in is equal to the number of elements in , then 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 is suitable for a certain job there is an edge between and 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 Properties See also | ||||||||
|
| |||||||||
 |
|
| |