Reconstruindo gráficos da distribuição de graus

Dada uma distribuição de graus, com que rapidez podemos construir um gráfico que segue a distribuição de graus dada? Um esboço de link ou algoritmo seria bom. O algoritmo deve relatar um "não" caso nenhum gráfico possa ser construído e qualquer exemplo, se vários gráficos puderem ser construídos.

Se você quer dizer como construir um gráfico tão simples (sem auto-loops e sem arestas paralelas), talvez o teorema de Havel-Hakimi seja o que você está procurando. Você mesmo pode pesquisar no Google e a página da Wikipedia Degree (teoria dos grafos) também é útil.

Se o grau de distribuição é dado como uma lista de grau, então você pode fazer o seguinte, dado nós com graus de d 1 , . . . $n$ :$d_1, ... ,d_n$

Crie um gráfico completo em n- vertices. Para cada vértice v i em K n , divida-o em d i cópias. Dividir aqui significa criar um número de cópias com arestas para cada vértice v i com aresta, mas sem arestas para outras cópias de v i . Se d i = 0 , em seguida, simplesmente remover o vértice. No novo gráfico, chame esses vértices de v i j para 1 ≤ j ≤ d i .$K_n$$n$$v_i$$K_n$$d_i$$v_i$$v_i$$d_i = 0$$v_{ij}$$1 \leq j \leq d_i$

Quando terminar, você terá um gráfico muito denso em vértices; chamar este gráfico H . Escolha o seu algoritmo de favorito para o máximo de correspondência (desde o gráfico é tão densa, você provavelmente deve usar um dos algoritmos baseados rápido matriz de multiplicação) e executá-lo em H . Isso retornará uma correspondência$N = d_1 + ... + d_n$$H$$H$. Se a correspondência não for perfeita (ou seja, se ela não cobrir todos os vértices), sua distribuição de graus será impossível; então retornenão.$M$

Se você tem uma correspondência perfeita , em seguida, remover todas as bordas não em M de H , e, em seguida, para cada 1 ≤ i ≤ n mesclar a d i muitos vértices v i 1 , . . . , v i d i em um vértice u $M$$M$$H$$1 \leq i \leq n$$d_i$$v_{i1}, ... , v_{id_i}$$u_i$ . Mesclar dois vértices significa combiná-los em um, de modo que o vértice resultante tenha arestas em todos os vértices em que pelo menos um dos originais tenha arestas. Chame o gráfico resultante ; tem a distribuição de graus desejada.$G$

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