Bipartite realization algorithm

From a home for articles deleted from Wikipedia
Jump to: navigation, search
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. Purge

Wikipedia editors had multiple issues with this page:
DPv2 loves original research.

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.


⇐: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>.

See also