Problema de realización de grafos

El problema de realización de grafos es un problema de decisión en la teoría de grafos . Dada una secuencia finita${\displaystyle (d_{1},\dots ,d_{n})}$de los números naturales, el problema pregunta si existe un grafo simple etiquetado tal que${\displaystyle (d_{1},\dots ,d_{n})}$es la secuencia de grados de este grafo.

En el contexto de la localización, el problema de realización de grafos también puede referirse a encontrar un conjunto de posiciones.${\displaystyle (x_{1},\dots ,x_{n})}$en algún espacio euclidiano tal que las distancias al cuadrado entre las posiciones, dadas por${\displaystyle d_{ij}^{2}}$, igualar los pesos de los bordes${\displaystyle w_{ij}}$para todas las aristas en un grafo ponderado, no dirigido e incompleto. ^{[ 1 ]}

El problema puede resolverse en tiempo polinomial . Un método para demostrar esto utiliza el algoritmo de Havel-Hakimi, construyendo una solución especial mediante un algoritmo recursivo . ^{[ 2 ] [ 3 ]} Alternativamente, siguiendo la caracterización dada por el teorema de Erdős-Gallai , el problema puede resolverse probando la validez de${\displaystyle n}$desigualdades. ^{[ 4 ]}

El problema también puede plantearse en términos de matrices simétricas de ceros y unos. La conexión puede verse si uno se da cuenta de que cada grafo tiene una matriz de adyacencia donde las sumas de las columnas y las sumas de las filas corresponden a${\displaystyle (d_{1},\ldots ,d_{n})}$. El problema se representa a veces mediante matrices simétricas 0-1 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 se denomina problema de realización bipartita . El segundo se conoce como problema de realización de digrafos .

Cooper, Martin y Greenhill demostraron que el problema de construir una solución para el problema de realización de grafos con la restricción adicional de que cada solución tiene la misma probabilidad tiene un esquema de aproximación en tiempo polinomial para las secuencias de grados de grafos regulares . ^{[ 5 ]} El problema general aún no se ha resuelto.