El problema de realización de grafos es un problema de decisión en la teoría de grafos . Dada una secuencia finitade números naturales, el problema pregunta si hay una gráfica simple etiquetada tal quees la secuencia de grados de este gráfico.
Soluciones
El problema se puede resolver en tiempo polinomial . Un método para mostrar esto usa el algoritmo de Havel-Hakimi construyendo 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 puede resolverse probando la validez dedesigualdades. [3]
Otras notaciones
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 a veces mediante matrices 0-1 simétricas para sumas de fila dadas .
Problemas relacionados
Problemas similares describen las secuencias de grados de gráficos bipartitos simples o las secuencias de grados de gráficos dirigidos simples . El primer problema es el llamado problema de realización bipartita . El segundo se conoce como problema de realización de dígrafos .
Se demostró que el problema de construir una solución para el problema de realización de grafos con la restricción adicional de que cada una de estas soluciones tiene la misma probabilidad tiene un esquema de aproximación de tiempo polinomial para las secuencias de grados de grafos regulares de Cooper, Martin y Greenhill. [4] El problema general sigue sin resolverse.
Referencias
- ^ Havel, Václav (1955), "Un comentario sobre la existencia de gráficos finitos" , Časopis Pro Pěstování Matematiky (en checo), 80 : 477–480.
- ^ Hakimi, SL (1962), "Sobre la realizabilidad de un conjunto de números enteros como grados de los vértices de un grafo lineal. I", Revista de la Sociedad de Matemáticas Industriales y Aplicadas , 10 (3): 496–506, doi : 10.1137 / 0110037 , HDL : 10338.dmlcz / 128153 , MR 0148049.
- ^ Erdős, P .; Gallai, T. (1960), "Gráfok előírt fokszámú pontokkal" (PDF) , Matematikai Lapok , 11 : 264–274.
- ^ Cooper, Colin; Dyer, Martin ; Greenhill, Catherine (2007), "Sampling regular graphs and a peer-to-peer network", Combinatorics, Probability and Computing , 16 (4): 557–593, CiteSeerX 10.1.1.181.597 , doi : 10.1017 / S0963548306007978 , MR 2334585.