Bipartite realization algorithm
- This article was considered for deletion at Wikipedia on July 25 2014. This is a backup of Wikipedia:Bipartite_realization_algorithm. All of its AfDs can be found at Wikipedia:Special:PrefixIndex/Wikipedia:Articles_for_deletion/Bipartite_realization_algorithm, the first at Wikipedia:Wikipedia:Articles_for_deletion/Bipartite_realization_algorithm.
- Wikipedia editors had multiple issues with this page:
The Bipartite realization algorithm is an algorithm in graph theory solving the bipartite realization problem, i.e. the question if there exists for two finite lists of nonnegative integers a simple bipartite graph such that its degree sequence corresponds exactly to these lists. For a positive answer the pair of lists is called bigraphic. The algorithm constructs a special solution if one exists or proves that one cannot find a positive answer. The constructions is based on a recursive algorithm. It was never been published in a scientific paper but works similar as the Havel-Hakimi Algorithm for the graph realization problem or the Kleitman-Wang algorithms for the digraph realization problem.
The algorithm
The algorithm is based on the following theorem.
Let <math>(a_1\dots,a_n)</math> and <math>(b_1,\dots,b_n)</math> be two finite lists of nonnegative integers such that <math>a_1 \geq \dots \geq a_n</math> and let <math>b_i >0</math>. The pair of lists <math>(a_1\dots,a_n)</math>, <math>(b_1,\dots,b_n)</math> is bigraphic if and only if the pair of lists <math>(a_1-1,\dots,a_{b_i}-1,a_{b_i+1},\dots,a_n)</math>, <math>(b_1,\dots,b_{i-1},0,b_{i+1},\dots,b_n)</math> is bigraphic.
Is the given pair of lists bigraphic then the theorem will be applied at most <math>n</math> times on the current pair of lists. This process ends when both lists only contain zeros. In each step of the algorithm one constructs the edges of a bipartite graph with vertices <math>v_1,\cdots,v_n</math> and <math>w_1,\cdots,w_n</math> in the two partite sets, i.e. if it is possible to reduce the lists, then we add edges <math>\{w_i,v_1\},\{w_i,v_2\},\cdots,\{w_{i},v_{b_1}\}</math>. When one of the current lists contains negative entries in any step of the algorithm, the theorem proves that the lists from the beginning are not bigraphic.
Proof
⇐:When the pair <math>(a_1-1,\dots,a_{b_i}-1,a_{b_i+1},\dots,a_n)</math>, <math>(b_1,\dots,b_{i-1},0,b_{i+1},\dots,b_n)</math> is bigraphic, then there exists a labeled bipartite graph <math>G(U,V, E)</math> with this degree sequence. Especially vertex <math>v_i</math> has degree zero. We connect vertex <math>v_i</math> with vertices <math>u_1,\dots,u_{b_i}</math> by edges and get a bipartite graph with degree sequence <math>(a_1\dots,a_n)</math>,<math>(b_1,\dots,b_n)</math>.
⇒:We consider a bipartite graph <math>G(U,V,E)</math> with degree sequence <math>(a_1\dots,a_n)</math>, <math>(b_1,\dots,b_n)</math> such that a maximum number of vertices <math>u_1,\dots,u_{b_i}</math> is adjacent to vertex <math>v_i.</math> Assume one of these vertices say <math>u_j</math> is not adjacent to vertex <math>v_i.</math> Then there is a vertex <math>u_k</math> with <math>k>b_i \geq j</math> such that <math>\{u_j,v_i\}</math> is no edge and <math>\{u_k,v_i\}</math> is one. Since <math>a_j \geq a_k</math> there is a further vertex <math>v_l</math> such that <math>\{u_j,v_l\}</math> is an edge and <math>\{u_k,v_l\}</math> is none. We delete in <math>G</math> the edges <math>\{u_k,v_i\},\{u_j,v_l\}</math> and add the edges <math>\{u_j,v_i\},\{u_k,v_l\}</math> obtaining a bipartite graph <math>G'</math> with the same degree sequence. The number of adjacent vertices of vertex <math>v_i</math> in <math>u_1,\dots,u_{b_i}</math> is larger than in <math>G</math> in contradiction to our assumption. We conclude that in <math>G</math> vertex <math>v_i</math> is adjacent to all vertices <math>u_1,\dots,u_{b_i}</math>. We delete in <math>G</math> all incident edges of <math>v_i</math> and get a bipartite graph with degree sequence <math>(a_1-1,\dots,a_{b_i}-1,a_{b_i+1},\dots,a_n)</math>, <math>(b_1,\dots,b_{i-1},0,b_{i+1},\dots,b_n)</math>.
