El problema de realización de grafos es un problema de decisión en la teoría de grafos . Dada una secuencia finita de números naturales, el problema pregunta si existe un grafo simple etiquetado tal que sea la secuencia de grados de este grafo.
El problema se puede resolver en tiempo polinomial . Un método para demostrar esto utiliza el algoritmo Havel–Hakimi, que construye una solución especial con el uso de un algoritmo recursivo . [1] [2] Alternativamente, siguiendo la caracterización dada por el teorema de Erdős–Gallai , el problema se puede resolver probando la validez de las desigualdades. [3]
El problema también se puede plantear en términos de matrices simétricas de ceros y unos. La conexión se puede ver si uno se da cuenta de que cada gráfico tiene una matriz de adyacencia donde las sumas de las columnas y las sumas de las filas corresponden a . El problema se denota entonces a veces por matrices 0-1 simétricas para sumas de filas dadas .
Problemas similares describen las secuencias de grados de grafos bipartitos simples o las secuencias de grados de grafos dirigidos simples . El primer problema es el llamado problema de realización bipartita . El segundo se conoce como el problema de realización de dígrafos .
Cooper, Martin y Greenhill demostraron que el problema de construir una solución para el problema de realización de gráficos con la restricción adicional de que cada una de esas soluciones tiene la misma probabilidad tiene un esquema de aproximación en tiempo polinomial para las secuencias de grados de gráficos regulares . [4] El problema general aún no se ha resuelto.
