Editing Bipartite graph (section)

===Relation to hypergraphs and directed graphs===
The [[Adjacency matrix of a bipartite graph|biadjacency matrix]] of a bipartite graph <math>(U,V,E)</math> is a [[(0,1) matrix]] of size <math>|U|\times|V|</math> that has a one for each pair of adjacent vertices and a zero for nonadjacent vertices.<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 17.</ref> Biadjacency matrices may be used to describe equivalences between bipartite graphs, hypergraphs, and directed graphs.

A [[hypergraph]] is a combinatorial structure that, like an undirected graph, has vertices and edges, but in which the edges may be arbitrary sets of vertices rather than having to have exactly two endpoints. A bipartite graph <math>(U,V,E)</math> may be used to model a hypergraph in which {{mvar|U}} is the set of vertices of the hypergraph, {{mvar|V}} is the set of hyperedges, and {{mvar|E}} contains an edge from a hypergraph vertex {{mvar|v}} to a hypergraph edge {{mvar|e}} exactly when {{mvar|v}} is one of the endpoints of {{mvar|e}}. Under this correspondence, the biadjacency matrices of bipartite graphs are exactly the [[incidence matrix|incidence matrices]] of the corresponding hypergraphs. As a special case of this correspondence between bipartite graphs and hypergraphs, any [[multigraph]] (a graph in which there may be two or more edges between the same two vertices) may be interpreted as a hypergraph in which some hyperedges have equal sets of endpoints, and represented by a bipartite graph that does not have multiple adjacencies and in which the vertices on one side of the bipartition all have [[degree (graph theory)|degree]] two.<ref>{{SpringerEOM|title=Hypergraph|author=A. A. Sapozhenko}}</ref>

A similar reinterpretation of adjacency matrices may be used to show a one-to-one correspondence between [[directed graph]]s (on a given number of labeled vertices, allowing self-loops) and balanced bipartite graphs, with the same number of vertices on both sides of the bipartition. For, the adjacency matrix of a directed graph with {{mvar|n}} vertices can be any [[(0,1) matrix]] of size <math>n\times n</math>, which can then be reinterpreted as the adjacency matrix of a bipartite graph with {{mvar|n}} vertices on each side of its bipartition.<ref>{{citation
 | last1 = Brualdi | first1 = Richard A.
 | last2 = Harary | first2 = Frank | author2-link = Frank Harary
 | last3 = Miller | first3 = Zevi
 | doi = 10.1002/jgt.3190040107
 | mr = 558453
 | issue = 1
 | journal = [[Journal of Graph Theory]]
 | pages = 51–73
 | title = Bigraphs versus digraphs via matrices
 | volume = 4
 | year = 1980}}. Brualdi et al. credit the idea for this equivalence to {{citation
 | doi = 10.4153/CJM-1958-052-0
 | last1 = Dulmage | first1 = A. L.
 | last2 = Mendelsohn | first2 = N. S. | author2-link = Nathan Mendelsohn
 | mr = 0097069
 | journal = Canadian Journal of Mathematics
 | pages = 517–534
 | title = Coverings of bipartite graphs
 | volume = 10
 | year = 1958| s2cid = 123363425 | doi-access = free
 }}.</ref> In this construction, the bipartite graph is the [[bipartite double cover]] of the directed graph.