Восстановление графиков из степени распределения

Учитывая распределение степеней, как быстро мы можем построить график, который следует заданному распределению степеней? Ссылка или эскиз алгоритма были бы хорошими. Алгоритм должен сообщать «нет», если граф не может быть построен, и любой один пример, если можно построить несколько графов.

Если вы имеете в виду, как построить такой простой граф (без собственных циклов и параллельных ребер), возможно, вам нужна теорема Гавела-Хакими. Вы можете сами погуглить, и страница википедии Степень (теория графов) также полезна.

$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})$