|
The '''Kleitman-WangKleitman–Wang algorithms''' are two different algorithms in [[graph theory]] solving the [[digraph realization problem]], i.e. the question if there exists for a finite [[list]] of nonnegative [[integer]] pairs a [[directed graph|simple directed graph]] such that its [[directed graph|degree sequence]] is exactly this list. For a positive answer the list of integer pairs is called ''digraphic''. Both algorithms construct a special solution if one exists or prove that one cannot find a positive answer. These constructions are based on [[Recursion (computer science)|recursive algorithm]]s. Kleitman and Wang <ref>{{harvtxt|Kleitman|1973}}</ref> gave these algorithms in 1973.
==Kleitman-WangKleitman–Wang algorithm (arbitrary choice of pairs)==
The algorithm is based on the following theorem.
Let <math>S=((a_1,b_1),\dots,(a_n,b_n))</math> be a finite list of nonnegative integers that is in [[nonincreasing]] [[lexicographical order]] and let <math>(a_i,b_i)</math> be a pair of nonnegative integers with <math>b_i >0</math>. List <math>S</math> is digraphic if and only if the finite [[list]] <math>S'=((a_1-1,b_1),\cdotsdots,(a_{b_{i}b_i-1}-1,b_{b_{i}b_i-1}),(a_{b_i},0),(a_{b_i+1}-1,b_{b_i+1}),(a_{b_i+2},b_{b_i+2}),\dots,(a_{n}a_n,b_{n}b_n))</math> has nonnegative integer pairs and is digraphic.
Note that the pair <math>(a_i,b_i)</math> is arbitrarily with the exception of pairs <math>(a_j,0)</math>. Is the given list <math>S</math> digraphic then the theorem will be applied at most <math>n</math> times setting in each further step <math>S:=S'</math>. This process ends when the whole list <math>S'</math> consists of <math>(0,0)</math> pairs. In each step of the algorithm one constructs the [[directed graph|arcs]] of a digraph with vertices <math>v_1,\cdotsdots,v_n</math>, i.e. if it is possible to reduce the list <math>S</math> to <math>S'</math>, then we add arcs <math>(v_i,v_1),(v_i,v_2),\cdotsdots,(v_{i},v_{b_i-1}),(v_i,v_{b_i+1})</math>. When the list <math>S</math> cannot be reduced to a list <math>S'</math> of nonnegative integer pairs in any step of this approach, the theorem proves that the list <math>S</math> from the beginning is not digraphic.
==Kleitman-WangKleitman–Wang algorithm (maximum choice of a pair)==
The algorithm is based on the following theorem.
Let <math>S=((a_1,b_1),\dots,(a_n,b_n))</math> be a finite list of nonnegative integers that such that <math>a_1 \geq a_2 \geq \dotscdots \geq a_n</math> and let <math>(a_i,b_i)</math> be a pair such that <math>(b_i,a_i)</math> is maximal with respect to the [[lexicographical order]] under all pairs <math>(b_1,a_1),\dots,(b_n,a_n)</math>. List <math>S</math> is digraphic if and only if the finite [[list]] <math>S'=((a_1-1,b_1),\cdots,(a_{b_{i}b_i-1}-1,b_{b_{i}b_i-1}),(a_{b_i},0),(a_{b_i+1}-1,b_{b_i+1}),(a_{b_i+2},b_{b_i+2}),\dots,(a_{n}a_n,b_{n}b_n))</math> has nonnegative integer pairs and is digraphic.
Note that the list <math>S</math> must not be an lexicographical order as in the first version. Is the given list <math>S</math> digraphic then the theorem will be applied at most <math>n</math> times setting in each further step <math>S:=S'</math>. This process ends when the whole list <math>S'</math> consists of <math>(0,0)</math> pairs. In each step of the algorithm one constructs the [[directed graph|arcs]] of a digraph with vertices <math>v_1,\cdotsdots,v_n</math>, i.e. if it is possible to reduce the list <math>S</math> to <math>S'</math>, then we add arcs <math>(v_i,v_1),(v_i,v_2),\cdotsdots,(v_{i}v_i,v_{b_i-1}),(v_i,v_{b_i+1})</math>. When the list <math>S</math> cannot be reduced to a list <math>S'</math> of nonnegative integer pairs in any step of this approach, the theorem proves that the list <math>S</math> from the beginning is not digraphic.
==See also==
*[[Fulkerson-Chen-AnsteeFulkerson–Chen–Anstee theorem]]
==References==
|
