algoritmos de Kleitman-Wang

Los algoritmos de Kleitman-Wang son dos algoritmos diferentes de la teoría de grafos que resuelven el problema de realización de digrafos , es decir, la cuestión de si existe, para una lista finita de pares de enteros no negativos , un grafo dirigido simple tal que su secuencia de grados sea exactamente dicha lista. Para una respuesta positiva, la lista de pares de enteros se denomina digrafo . Ambos algoritmos construyen una solución especial si existe o demuestran que no se puede encontrar una respuesta positiva. Estas construcciones se basan en algoritmos recursivos . Kleitman y Wang ^{[ 1 ]} presentaron estos algoritmos en 1973.

El algoritmo se basa en el siguiente teorema.

Dejar${\displaystyle S=((a_{1},b_{1}),\dots ,(a_{n},b_{n}))}$Sea una lista finita de enteros no negativos en orden lexicográfico no creciente y sea${\displaystyle (a_{i},b_{i})}$sea ​​un par de enteros no negativos con${\displaystyle b_{i}>0}$. Lista${\displaystyle S}$es digráfica si y solo si la lista finita${\displaystyle S'=((a_{1}-1,b_{1}),\dots ,(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}))}$tiene pares de enteros no negativos y es digráfica.

Nótese que el par${\displaystyle (a_{i},b_{i})}$es arbitrariamente con la excepción de pares${\displaystyle (a_{j},0)}$. Si la lista dada${\displaystyle S}$digráfico entonces el teorema se aplicará como máximo${\displaystyle n}$Los tiempos se establecen en cada paso siguiente.${\displaystyle S:=S'}$Este proceso termina cuando toda la lista${\displaystyle S'}$consta de${\displaystyle (0,0)}$pares. En cada paso del algoritmo se construyen los arcos de un digrafo con vértices${\displaystyle v_{1},\dots,v_{n}}$, es decir, si es posible reducir la lista${\displaystyle S}$a${\displaystyle S'}$, luego agregamos arcos${\displaystyle (v_{i},v_{1}),(v_{i},v_{2}),\dots ,(v_{i},v_{b_{i}-1}),(v_{i},v_{b_{i}+1})}$Cuando la lista${\displaystyle S}$no se puede reducir a una lista${\displaystyle S'}$de pares de enteros no negativos en cualquier paso de este enfoque, el teorema demuestra que la lista${\displaystyle S}$Desde el principio no es digráfico.

El algoritmo se basa en el siguiente teorema.

Dejar${\displaystyle S=((a_{1},b_{1}),\dots ,(a_{n},b_{n}))}$sea ​​una lista finita de enteros no negativos tal que${\displaystyle a_{1}\geq a_{2}\geq \cdots \geq a_{n}}$y dejar${\displaystyle (a_{i},b_{i})}$ser un par tal que${\displaystyle (b_{i},a_{i})}$es máximo con respecto al orden lexicográfico en todos los pares${\displaystyle (b_{1},a_{1}),\dots ,(b_{n},a_{n})}$. Lista${\displaystyle S}$es digráfica si y solo si la lista finita${\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}))}$tiene pares de enteros no negativos y es digráfica.

Tenga en cuenta que la lista${\displaystyle S}$no debe estar en orden lexicográfico como en la primera versión. Si la lista dada${\displaystyle S}$es digráfico, entonces el teorema se aplicará como máximo${\displaystyle n}$tiempos, estableciéndose en cada paso siguiente${\displaystyle S:=S'}$Este proceso termina cuando toda la lista${\displaystyle S'}$consta de${\displaystyle (0,0)}$pares. En cada paso del algoritmo, se construyen los arcos de un digrafo con vértices${\displaystyle v_{1},\dots,v_{n}}$, es decir, si es posible reducir la lista${\displaystyle S}$a${\displaystyle S'}$, luego se añaden arcos${\displaystyle (v_{i},v_{1}),(v_{i},v_{2}),\dots ,(v_{i},v_{b_{i}-1}),(v_{i},v_{b_{i}+1})}$Cuando la lista${\displaystyle S}$no se puede reducir a una lista${\displaystyle S'}$de pares de enteros no negativos en cualquier paso de este enfoque, el teorema demuestra que la lista${\displaystyle S}$Desde el principio no es digráfico.

• Teorema de Fulkerson-Chen-Anstee

• Kleitman, DJ; Wang, DL (1973), "Algoritmos para la construcción de grafos y digrafos con valencias y factores dados", Matemáticas Discretas , 6 : 79–88 , doi : 10.1016/0012-365x(73)90037-x