El problema de realización de dígrafos es un problema de decisión en la teoría de grafos . Dados pares de números enteros no negativos , el problema pregunta si existe un grafo dirigido simple etiquetado tal que cada vértice tenga grado de entrada y grado de salida .
El problema pertenece a la clase de complejidad P. Se conocen dos algoritmos para demostrarlo. El primer enfoque está 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 corrección de las desigualdades.
El problema también puede plantearse en términos de matrices cero-uno . La conexión puede verse si uno se da cuenta de que cada grafo dirigido tiene una matriz de adyacencia donde las sumas de las columnas y las sumas de las filas corresponden a y . Nótese que la diagonal de la matriz solo contiene ceros. El problema se denota entonces a menudo por 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 dadas .
Problemas similares describen las secuencias de grados de grafos simples , grafos dirigidos simples con bucles y grafos bipartitos simples . El primer problema es el llamado problema de realización de grafos . El segundo y el tercero son equivalentes y se conocen como el problema de realización bipartita . Chen (1966) da una caracterización para multigrafos dirigidos con un número acotado de arcos y bucles paralelos a una secuencia de grados dada . La restricción adicional de la aciclicidad del grafo dirigido se conoce como realización dag . Nichterlein y Hartung (2012) demostraron la NP-completitud de este problema. Berger y Müller-Hannemann (2011) demostraron que la clase de secuencias opuestas está en P. El problema del muestreo uniforme de un grafo dirigido a una secuencia de grado fijo es construir una solución para el problema de realización de dígrafos con la restricción adicional de que cada solución viene con la misma probabilidad. Catherine Greenhill (2011) demostró que este problema se encuentra en FPTAS para secuencias regulares . El problema general aún no se ha resuelto.
