Reconstrucción de gráficos a partir de la distribución de grados

Dada una distribución de grados, ¿qué tan rápido podemos construir un gráfico que siga la distribución de grados dada? Un enlace o un bosquejo de algoritmo sería bueno. El algoritmo debe informar un "no" en caso de que no se pueda construir un gráfico y cualquier ejemplo si se pueden construir varios gráficos.

Si te refieres a cómo construir un gráfico tan simple (sin auto-bucles y sin bordes paralelos), tal vez el teorema de Havel-Hakimi es lo que estás buscando. Puede buscarlo en Google usted mismo, y la página wikipedia Grado (teoría de grafos) también es útil.

$n$$d_1, ... ,d_n$

$K_n$$n$$v_i$$K_n$$d_i$$v_i$$v_i$$d_i = 0$$v_{ij}$$1 \leq j \leq d_i$

$N = d_1 + ... + d_n$$H$$H$$M$

$M$$M$$H$$1 \leq i \leq n$$d_i$$v_{i1}, ... , v_{id_i}$$u_i$$G$

$O(N^\omega)$$\omega$$2.373$$O(n^{2\omega})$