Kleitman–Wang algorithms: Difference between revisions

Revision as of 13:36, 7 July 2014

Latest revision as of 19:56, 12 October 2024

(19 intermediate revisions by 16 users not shown)

Line 1:

{{Short description|Graph theory algorithms}}

----

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 (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-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 [[Enumeration|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>. IsIf 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)==

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,\cdots,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),\cdots,(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-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,\cdots,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),\cdots,(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.

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,\cdotsdots,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),\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==

*{{citation

| last1 = Kleitman | first1 = D. J.

| last2 = Wang | first2 = D. L.

| title = Algorithms for constructing graphs and digraphs with given valences and factors

| journal = Discrete Mathematics

| volume = 6

| year = 1973

| pages = 79-88}}79–88

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

}}

{{reflist}}

{{DEFAULTSORT:Kleitman-Wang algorithms}}

[[Category:Graph algorithms]]