El problema de realización de dígrafos es un problema de decisión en la teoría de grafos . Pares dados de enteros no negativos , el problema pregunta si hay una gráfica dirigida simple etiquetada tal que cada vértice tiene grado y excedido .
Soluciones
El problema pertenece a la clase de complejidad P . Se conocen dos algoritmos que lo demuestran. El primer enfoque viene dado por los algoritmos de Kleitman-Wang que construyen una solución especial con el uso de un algoritmo recursivo . El segundo es una caracterización por el teorema de Fulkerson-Chen-Anstee , es decir, uno tiene que validar la exactitud de desigualdades.
Otras notaciones
El problema también se puede plantear en términos de matrices cero-uno . La conexión se puede ver si uno se da cuenta de que cada gráfico dirigido tiene una matriz de adyacencia donde las sumas de las columnas y las sumas de las filas corresponden a y . Tenga en cuenta que la diagonal de la matriz solo contiene ceros. Entonces, el problema a menudo se denota mediante matrices 0-1 para sumas de filas y columnas dadas . En la literatura clásica, el problema a veces se planteaba en el contexto de tablas de contingencia mediante tablas de contingencia con marginales dados .
Problemas relacionados
Problemas similares describen las secuencias de grados de gráficas simples , gráficas directas simples con bucles y gráficas bipartitas simples . El primer problema es el llamado problema de realización de gráficos . El segundo y el tercero son equivalentes y se conocen como el problema de realización bipartita . Chen (1966) ofrece una caracterización para multigrafías dirigidas con un número limitado de arcos y bucles paralelos a una secuencia de grados determinada . La restricción adicional de la acilicidad del gráfico dirigido se conoce como realización dag . Nichterlein y Hartung (2012) demostraron la completitud NP de este problema. Berger & Müller-Hannemann (2011) mostraron que la clase de secuencias opuestas está en P . El problema del muestreo uniforme de un gráfico dirigido a una secuencia de grados fija es construir una solución para el problema de realización del dígrafo con la restricción adicional de que cada solución tiene la misma probabilidad. Este problema ha demostrado ser en FPTAS para secuencias regulares por Catalina Greenhill ( 2011 ) El problema general todavía está sin resolver.
Referencias
- Chen, Wai-Kai (1966), "Sobre la realización de un ( p , s ) -digraph con grados prescritos", Journal of the Franklin Institute , 103 : 406–422
- Nichterlein, André; Hartung, Sepp (2012), "NP-Dureza y Tractabilidad de parámetros fijos de la realización de secuencias de grados con gráficos acíclicos dirigidos", Revista del Instituto Franklin , 7318 : 283-292
- Berger, Annabell; Müller-Hannemann, Matthias (2011), "Dag Realisations of Directed Degree Sequences", Actas de la 18ª Conferencia Internacional sobre Fundamentos de la Teoría de la Computación : 264-275
- Greenhill, Catherine (2011), "Un polinomio enlazado en el tiempo de mezcla de una cadena de Markov para muestrear gráficos regulares dirigidos", Electronic Journal of Combinatorics , 18