¿Cómo se comprueba si una secuencia es gráfica? (se permiten las aristas múltiples pero no los bucles)

Question

¿Cómo se comprueba si una secuencia es gráfica? ( se permiten las aristas múltiples pero no los bucles) Si las aristas múltiples tampoco están permitidas, el problema se puede resolver con el algoritmo de Havel-Hakimi. Pero si se permiten las aristas múltiples, ¿cómo se resuelve?

Se agradece cualquier ayuda.

Answer 1

Una secuencia $d_1 \ge d_2 \ge \dots \ge d_n$ claramente no es "multigráfico" si $d_1 > d_2 + d_3 + \dots + d_n$ , ya que el primer vértice quiere más aristas fuera de él que todos los demás juntos.

Por otro lado, si ningún grado es mayor que la suma de todos los demás, entonces esto sigue siendo cierto de que disminuimos $d_1$ et $d_2$ (los dos grados mayores) por $1$ . Así que podemos construir (inductivamente) el multigrafo con la secuencia de grados $(d_1-1, d_2-1, d_3, \dots, d_n)$ entonces añade una arista entre los vértices $1$ et $2$ .