¿Funciona este algoritmo para la Realización de Gráficos?

Question

Una secuencia de números enteros $d_1, \dots , d_n$ se llama gráfico si existe un simple gráfico $G$ con él como su secuencia de grados. Decidir si una secuencia es gráfica se llama la Problema de realización de gráficos .

A teorema de Havel y Hakimi da un algoritmo para construir tal gráfico si existe: procede seleccionando repetidamente un vértice de más alto grado $v$ y conectarlo a los vértices de alto hasta el grado de $v$ está agotado.

En cambio, quiero considerar el algoritmo que, a cada paso, conecta un vértice de más alto con un solo vértice de más bajo grado no cero. Obsérvese que este algoritmo, a diferencia del de Havel-Hakimi, no selecciona un vértice del grado más alto y lo conecta hasta que se agota su grado: se selecciona un nuevo vértice del grado más alto cada vez que se añade un borde.

Por ejemplo, dada la secuencia gráfica de grados $2, 2, 2, 1, 1$ el algoritmo procede de la siguiente manera:

$$1,2,2,0,1 \\0 ,1,2,0,1 \\0 ,0,1,0,1 \\0 ,0,0,0,0$$

lo que da como resultado el camino simple $P_5$ en cinco vértices (donde rompí los lazos seleccionando el más alto o más pequeño de la izquierda).

¿Existe algún contraejemplo para el cual este algoritmo no produzca una realización gráfica?

NOTA: Espero que la respuesta sea afirmativa, ya que este algoritmo no conectará nunca dos vértices de bajo grado a menos que agote todo lo demás. Por lo tanto, si cualquier realización gráfica de una cierta secuencia de grados debe contener un borde entre dos vértices de bajo grado hemos terminado, pero no fui capaz de encontrar tal ejemplo.

Answer 1

Hay algunos problemas con su algoritmo:

1)

No distingue entre posiciones solubles y no solubles: Si se le da una secuencia como nn, felizmente irá añadiendo bordes entre las dos. Esto lleva a

2)

Tu algoritmo no produce gráficos sencillos sin tener en cuenta el desempate:

Considere la secuencia 64332222. Esto tiene una realización (sólo dibújelo). Sin embargo, independientemente de los desempate, su algoritmo siempre intentará conectar el primer vértice a uno de los 2s dos veces. Esta es una de las grandes ventajas de havel-hakimi, al agotar instantáneamente el grado de nodos al añadirles bordes no se encuentran con el problema de los multi-bordes.

Si se restringiera el algoritmo para que sólo conectara los bordes inconexos, probablemente produciría realizaciones válidas. Sin embargo, eso sería a costa de tener que pasar mucha más información que la lista de grados (no utilizados) de cada vértice. Creo que tu algoritmo producirá realizaciones válidas porque si tienes una realización en la que hay un borde entre los vértices, digamos ab y cd y ninguno entre ac y bd, entonces puedes eliminar ab,cd y añadir ac,bd para producir otra realización de la misma secuencia. De esta manera debería ser posible evitar/forzar siempre los bordes entre los vértices de alto y bajo grado.