Kleitman – Wangovy algoritmy - Kleitman–Wang algorithms

The Kleitman – Wangovy algoritmy jsou dva různé algoritmy v teorie grafů řešení problém realizace digrafu, tj. otázka, zda existuje pro konečnou seznam nezáporné celé číslo páry a jednoduchý směrovaný graf takový, že jeho sekvence stupňů je přesně tento seznam. Pro kladnou odpověď se volá seznam celočíselných párů digrafické. Oba algoritmy vytvářejí speciální řešení, pokud existuje, nebo prokazují, že nelze najít kladnou odpověď. Tyto konstrukce jsou založeny na rekurzivní algoritmy. Kleitman a Wang ^[1] dal tyto algoritmy v roce 1973.

Kleitman-Wangův algoritmus (libovolný výběr párů)

Algoritmus je založen na následující větě.

Nechat ${ displaystyle S = ((a_ {1}, b_ {1}), tečky, (a_ {n}, b_ {n}))}$ být konečný seznam nezáporných celých čísel, která jsou v nezvyšující se lexikografický řád a nechte ${ displaystyle (a_ {i}, b_ {i})}$ být dvojicí nezáporných celých čísel s ${ displaystyle b_ {i}> 0}$. Seznam ${ displaystyle S}$ je digrafický, právě když je konečný seznam ${ displaystyle S '= ((a_ {1} -1, b_ {1}), tečky, (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}), tečky, (a_ {n}, b_ {n}))}$ má nezáporné celočíselné páry a je digrafické.

Všimněte si, že pár ${ displaystyle (a_ {i}, b_ {i})}$ je libovolně s výjimkou párů ${ displaystyle (a_ {j}, 0)}$. Pokud daný seznam ${ displaystyle S}$ digrafický pak bude věta použita maximálně ${ displaystyle n}$ nastavení času v každém dalším kroku ${ displaystyle S: = S '}$. Tento proces končí, když celý seznam ${ displaystyle S '}$ skládá se z ${ displaystyle (0,0)}$ páry. V každém kroku algoritmu se vytvoří oblouky digrafu s vrcholy ${ displaystyle v_ {1}, tečky, v_ {n}}$, tj. pokud je možné seznam zmenšit ${ displaystyle S}$ na ${ displaystyle S '}$, pak přidáme oblouky ${ displaystyle (v_ {i}, v_ {1}), (v_ {i}, v_ {2}), tečky, (v_ {i}, v_ {b_ {i} -1}), (v_ { i}, v_ {b_ {i} +1})}$. Když seznam ${ displaystyle S}$ nelze redukovat na seznam ${ displaystyle S '}$ nezáporných celočíselných párů v kterémkoli kroku tohoto přístupu, věta dokazuje, že seznam ${ displaystyle S}$ od začátku není digrafický.

Kleitman-Wangův algoritmus (maximální výběr páru)

Algoritmus je založen na následující větě.

Nechat ${ displaystyle S = ((a_ {1}, b_ {1}), tečky, (a_ {n}, b_ {n}))}$ být konečný seznam nezáporných celých čísel takový, že ${ displaystyle a_ {1} geq a_ {2} geq cdots geq a_ {n}}$ a nechte ${ displaystyle (a_ {i}, b_ {i})}$ být takovým párem ${ displaystyle (b_ {i}, a_ {i})}$ je maximální s ohledem na lexikografický řád pod všemi páry ${ displaystyle (b_ {1}, a_ {1}), tečky, (b_ {n}, a_ {n})}$. Seznam ${ displaystyle S}$ je digrafický, právě když je konečný seznam ${ 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}), tečky, (a_ {n}, b_ {n}))}$ má nezáporné celočíselné páry a je digrafické.

Všimněte si, že seznam ${ displaystyle S}$ nesmí být v lexikografickém pořadí jako v první verzi. Pokud daný seznam ${ displaystyle S}$ je digrafický, pak bude věta použita maximálně ${ displaystyle n}$ časy, nastavení v každém dalším kroku ${ displaystyle S: = S '}$. Tento proces končí, když celý seznam ${ displaystyle S '}$ skládá se z ${ displaystyle (0,0)}$ páry. V každém kroku algoritmu jeden vytvoří oblouky digrafu s vrcholy ${ displaystyle v_ {1}, tečky, v_ {n}}$, tj. pokud je možné seznam zmenšit ${ displaystyle S}$ na ${ displaystyle S '}$, pak jeden přidá oblouky ${ displaystyle (v_ {i}, v_ {1}), (v_ {i}, v_ {2}), tečky, (v_ {i}, v_ {b_ {i} -1}), (v_ { i}, v_ {b_ {i} +1})}$. Když seznam ${ displaystyle S}$ nelze redukovat na seznam ${ displaystyle S '}$ nezáporných celočíselných párů v kterémkoli kroku tohoto přístupu, věta dokazuje, že seznam ${ displaystyle S}$ od začátku není digrafický.

Viz také

• Věta Fulkerson – Chen – Anstee

Reference

• Kleitman, D. J .; Wang, D. L. (1973), „Algoritmy pro konstrukci grafů a digrafů s danými valencemi a faktory“, Diskrétní matematika, 6: 79–88, doi:10.1016 / 0012-365x (73) 90037-x