Editing Bipartite graph (section)

==Examples==

When modelling [[heterogeneous relation|relations]] between two different classes of objects, bipartite graphs very often arise naturally. For instance, a graph of football players and clubs, with an edge between a player and a club if the player has played for that club, is a natural example of an ''affiliation network'', a type of bipartite graph used in [[social network analysis]].<ref>{{citation
 | last1 = Wasserman | first1 = Stanley
 | author-link1= Stanley Wasserman
 | last2 = Faust | first2 = Katherine
 | isbn = 9780521387071
 | pages = 299–302
 | publisher = Cambridge University Press
 | series = Structural Analysis in the Social Sciences
 | title = Social Network Analysis: Methods and Applications
 | url = https://books.google.com/books?id=CAm2DpIqRUIC&pg=PA299
 | volume = 8
 | year = 1994}}.</ref>

Another example where bipartite graphs appear naturally is in the ([[NP-complete]]) railway optimization problem, in which the input is a schedule of trains and their stops, and the goal is to find a set of train stations as small as possible such that every train visits at least one of the chosen stations. This problem can be modeled as a [[dominating set]] problem in a bipartite graph that has a vertex for each train and each station and an edge for each pair of a station and a train that stops at that station.<ref name=niedermeier2006invitiation>{{citation|last=Niedermeier|first=Rolf|author-link=Rolf Niedermeier|title=Invitation to Fixed Parameter Algorithms|series=Oxford Lecture Series in Mathematics and Its Applications|year=2006|publisher=Oxford University Press|isbn=978-0-19-856607-6|pages=20–21}}</ref>

A third example is in the academic field of numismatics. Ancient coins are made using two positive impressions of the design (the obverse and reverse). The charts numismatists produce to represent the production of coins are bipartite graphs.<ref name=bracey2012>{{citation|last=Bracey|first=Robert|editor1-first=David M.|editor1-last=Jacobson|editor2-first=Nikos|editor2-last=Kokkinos|chapter=On the graphical interpretation of Herod's year 3 coins|title=Judaea and Rome in Coins 65 BCE – 135 CE: Papers Presented at the International Conference hosted by Spink, 13th – 14th September 2010|year=2012|publisher=[[Spink & Son]]|pages=65–84}}</ref>

More abstract examples include the following:
* Every [[tree (graph theory)|tree]] is bipartite.<ref name="s12"/>
* [[Cycle graph]]s with an even number of vertices are bipartite.<ref name="s12"/>
* Every [[planar graph]] whose [[Glossary of graph theory#Genus|faces]] all have even length is bipartite.<ref>{{citation|first=Alexander|last=Soifer|author-link=Alexander Soifer|year=2008|title=The Mathematical Coloring Book|title-link= The Mathematical Coloring Book |publisher=Springer-Verlag|isbn=978-0-387-74640-1|pages=136–137}}. This result has sometimes been called the "two color theorem"; Soifer credits it to a famous 1879 paper of [[Alfred Kempe]] containing a false proof of the [[four color theorem]].</ref> Special cases of this are [[grid graph]]s and [[squaregraph]]s, in which every inner face consists of 4 edges and every inner vertex has four or more neighbors.<ref>{{citation|title=Combinatorics and geometry of finite and infinite squaregraphs|first1=H.-J.|last1=Bandelt|first2=V.|last2=Chepoi|first3=D.|last3=Eppstein|author3-link=David Eppstein|arxiv=0905.4537|journal=[[SIAM Journal on Discrete Mathematics]]|volume=24|issue=4|pages=1399–1440|year=2010|doi=10.1137/090760301|s2cid=10788524}}.</ref>
* The [[complete bipartite graph]] on ''m'' and ''n'' vertices, denoted by ''K<sub>n,m</sub>'' is the bipartite graph <math>G = (U, V, E)</math>, where ''U'' and ''V'' are disjoint sets of size ''m'' and ''n'', respectively, and ''E'' connects every vertex in ''U'' with all vertices in ''V''.  It follows that ''K<sub>m,n</sub>'' has ''mn'' edges.<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 11.</ref> Closely related to the complete bipartite graphs are the [[crown graph]]s, formed from complete bipartite graphs by removing the edges of a [[perfect matching]].<ref>{{citation
 | last1 = Archdeacon | first1 = D. | author1-link = Dan Archdeacon
 | last2 = Debowsky | first2 = M.
 | last3 = Dinitz | first3 = J. | author3-link = Jeff Dinitz
 | last4 = Gavlas | first4 = H.
 | doi = 10.1016/j.disc.2003.11.021
 | issue = 1–3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | pages = 37–43
 | title = Cycle systems in the complete bipartite graph minus a one-factor
 | volume = 284
 | year = 2004| doi-access = 
 }}.</ref>
* [[Hypercube graph]]s, [[partial cube]]s, and [[median graph]]s are bipartite. In these graphs, the vertices may be labeled by [[bitvector]]s, in such a way that two vertices are adjacent if and only if the corresponding bitvectors differ in a single position. A bipartition may be formed by separating the vertices whose bitvectors have an even number of ones from the vertices with an odd number of ones. Trees and squaregraphs form examples of median graphs, and every median graph is a partial cube.<ref>{{citation|first=Sergei|last=Ovchinnikov|title=Graphs and Cubes|series=Universitext|publisher=Springer|year=2011}}. See especially Chapter 5, "Partial Cubes", pp. 127–181.</ref>