Bipartite graph

Example of a bipartite graph without cycles
A complete bipartite graph with m = 5 and n = 3
The Heawood graph is bipartite.

In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.[1][2]

The two sets and may be thought of as a coloring of the graph with two colors: if one colors all nodes in blue, and all nodes in red, each edge has endpoints of differing colors, as is required in the graph coloring problem.[3][4] 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 to denote a bipartite graph whose partition has the parts and , with denoting the edges of the graph. If a bipartite graph is not connected, it may have more than one bipartition;[5] in this case, the notation is helpful in specifying one particular bipartition that may be of importance in an application. If , that is, if the two subsets have equal cardinality, then is called a balanced bipartite graph.[3] If all vertices on the same side of the bipartition have the same degree, then is called biregular.

  1. ^ Diestel, Reinard (2005), Graph Theory, Graduate Texts in Mathematics, Springer, ISBN 978-3-642-14278-9, archived from the original on 2011-04-09, retrieved 2012-02-27
  2. ^ Asratian, Armen S.; Denley, Tristan M. J.; Häggkvist, Roland (1998), Bipartite Graphs and their Applications, Cambridge Tracts in Mathematics, vol. 131, Cambridge University Press, ISBN 9780521593458.
  3. ^ a b Asratian, Denley & Häggkvist (1998), p. 7.
  4. ^ Scheinerman, Edward R. (2012), Mathematics: A Discrete Introduction (3rd ed.), Cengage Learning, p. 363, ISBN 9780840049421.
  5. ^ Chartrand, Gary; Zhang, Ping (2008), Chromatic Graph Theory, Discrete Mathematics And Its Applications, vol. 53, CRC Press, p. 223, ISBN 9781584888000.

From Wikipedia, the free encyclopedia · View on Wikipedia

Developed by Nelliwinne