Kleitman–Wang algorithms: Difference between revisions

Revision as of 21:55, 18 March 2015

Latest revision as of 19:56, 12 October 2024

(9 intermediate revisions by 9 users not shown)

Line 1:

{{Short description|Graph theory algorithms}}

The '''Kleitman–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 (abstract data type)|list]] of nonnegative [[integer]] pairs a [[directed graph|simple directed graph]] such that its [[directed graphDirected_graph#Degree_sequence|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|Wang|1973}}</ref> gave these algorithms in 1973.

==Kleitman–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 [[Enumeration|list]] <math>S'=((a_1-1,b_1),\dots,(a_{b_i-1}-1,b_{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,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>. If 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,\dots,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),\dots,(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.

Line 11 ⟶ 12:

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 \cdots \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-1}-1,b_{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,b_n))</math> has nonnegative integer pairs and is digraphic.

Note that the list <math>S</math> must not be anin lexicographical order as in the first version. IsIf the given list <math>S</math> is 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,\dots,v_n</math>, i.e. if it is possible to reduce the list <math>S</math> to <math>S'</math>, then weone addadds arcs <math>(v_i,v_1),(v_i,v_2),\dots,(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==

Line 27 ⟶ 28:

| year = 1973

| pages = 79–88

| doi=10.1016/0012-365x(73)90037-x| doi-access = free
}}

{{reflist}}

{{DEFAULTSORT:Kleitman-Wang algorithms}}

[[Category:Graph theory]]

[[Category:AlgorithmsGraph algorithms]]