Algorytmy Kleitmana-Wanga

Kleitmana -Wanga to dwa różne algorytmy w teorii grafów rozwiązujące problem realizacji digrafu , tj. pytanie, czy dla skończonej listy nieujemnych par liczb całkowitych istnieje prosty graf skierowany , którego sekwencja stopni jest dokładnie tą listą. Aby uzyskać pozytywną odpowiedź, lista par liczb całkowitych nazywana jest digraficzną . Oba algorytmy konstruują specjalne rozwiązanie, jeśli takie istnieje lub dowodzi, że nie można znaleźć pozytywnej odpowiedzi. Konstrukcje te opierają się na algorytmy rekurencyjne . Kleitman i Wang podali te algorytmy w 1973 roku.

Algorytm Kleitmana – Wanga (dowolny wybór par)

Algorytm opiera się na następującym twierdzeniu.

Niech ${\ Displaystyle S = ((a_ {1}, b_ {1}), \ kropki, (a_ {n}, b_ {n}}}}$ będzie skończoną listą nieujemnych liczb całkowitych w nierosnącym porządku leksykograficznym i niech będzie parą nieujemnych liczb całkowitych z ${\ Displaystyle (a_ {i}, b_ {i})}$ ${\ displaystyle b_ {i}> 0}$ . Lista ${\ displaystyle S}$ jest digraficzna wtedy i tylko wtedy, gdy skończona lista ${\ Displaystyle S '= ((a_ {1 }-1,b_{1}),\kropki ,(a_{b_{i}-1}-1,b_{b_{i}-1}),(a_{b_{i}},0),( a_{b_{i}+1},b_{b_{i}+1}),(a_{b_{i}+2},b_{b_{i}+2}),\kropki ,(a_{n },b_{n}))}$ ma nieujemne pary liczb całkowitych i jest digraficzny.

$j$$(a_{j},0)$ ) ( . If the given list $S$ digraphic then the theorem will be applied at most $n$ times setting in each further step $S:=S'$. This process ends when the whole list składa się z $Displaystyle$$(0,0)$ . W każdym $.$ algorytmu konstruuje się łuki digrafu z wierzchołkami listy ${ \displaystyle S}$ do $S'$ następnie dodajemy łuki ${\ Displaystyle (v_ {i}, v_ {1}), ( v_{i},v_{2}),\kropki ,(v_{i},v_{b_{i}-1}),(v_{i},v_{b_{i}+1})}$ . Kiedy listy $S$ zredukować do listy $W$$przypadku nieujemnych$ par liczb całkowitych w dowolnym kroku tego podejścia, twierdzenie dowodzi, że lista początku nie jest digraficzna.

Algorytm Kleitmana – Wanga (maksymalny wybór pary)

Algorytm opiera się na następującym twierdzeniu.

Niech ${\ Displaystyle S = ((a_ {1}, b_ {1}), \ kropki, (a_ {n}, b_ {n}}}} będzie$ skończoną listą nieujemnych liczb całkowitych takich, że za $Displaystyle a_ {1} \ geq a_ {2} \ geq \ cdots \ geq a_ {n}}$ niech ${\ Displaystyle (a_ {i}, b_ {i})}$ być parą taką, że ${\ Displaystyle (b_ {i}, a_ {i})}$ jest maksymalna w odniesieniu do porządek leksykograficzny pod wszystkimi parami ${\ Displaystyle (b_ {1}, a_ {1}), \ kropki, (b_ {n}, a_ {n} )}$ . lista ${\ Displaystyle S}$ jest digraficzny wtedy i tylko wtedy, gdy skończona lista $\ Displaystyle S'= ((a_ {1} -1, b_ {1}), \ cdots ,(a_{b_{i}-1}-1,b_{b_{i}-1}),(a_{b_{i}},0),(a_{b_{i}+1},b_ {b_{i}+1}),(a_{b_{i}+2},b_{b_{i}+2}),\dots ,(a_{n},b_{n}))} ma liczbę$ nieujemną par liczb całkowitych i jest digraficzny.

Zauważ, że lista nie może być w porządku $leksykograficznym$ jak w pierwszej wersji. $Jeśli$ dana lista $,$$twierdzenie$ zostanie zastosowane co najwyżej ustawiając w każdym kolejnym kroku Ten proces kończy się, gdy cała lista $Displaystyle$ się z $(0,0)$ pary. ${\ Displaystyle S}$$.$ algorytmu konstruuje się łuki digrafu z wierzchołkami zredukować do ${\ Displaystyle S'}$ , następnie dodaje się łuki ${\ Displaystyle (v_ {i}, v_ {1}), (v_ {i}, v_ {2}), \ kropki ,(v_{i},v_{b_{i}-1}),(v_{i},v_{b_{i}+1})}$ . Gdy listy nie można zredukować do listy nieujemnych par liczb całkowitych na $żadnym$ etapie tego podejścia, twierdzenie dowodzi, że lista $displaystyle S}$${\ displaystyle S}$ od początku nie jest digraficzny.

Zobacz też

• Twierdzenie Fulkersona – Chena – Anstee

• Kleitman, DJ; Wang, DL (1973), „Algorytmy konstruowania wykresów i digrafów z podanymi wartościowościami i czynnikami”, Discrete Mathematics , 6 : 79–88, doi : 10,1016 / 0012-365x (73) 90037-x