valerio_CR_aleat_semesc

Prévia do material em texto

Lista 4: Redes Aleatórias e Redes Sem Escala
1. Seja ` a Distância Média de um grafo G com n vértices. Mostre que
1≤ `≤ n+1
3
,
sendo que `= 1 ocorre quando G é completo e `= (n+1)/3 quando G é uma busca. Dica: use a fórmula
1+22 +32 + · · ·+n2 = n(n+1)(2n+1)/6.
As cinco questões a seguir utilizam os grafos do arquivo anexo percursos.zip; desconsidere arestas duplicadas,
pesos e orientação (setas) quando houver.
2. Calcule a Densidade p, também chamada Probabilidade de Conexão, de cada um dos grafos.
3. Encontre a Distância Média de cada grafo.
4. Estime a Clusterização de cada grafo, também chamada Coeficiente de Agrupamento.
5. Trace o Histograma de Freqüências de cada um dos grafos. Ou seja, para cada grau de vértice g = 1,2,3, . . .
encontre f (g) = no¯ de vértices com aquele g, e trace o grafo de f : N→ N.
6. Repita o item anterior para Distribuição Cumulativa, ou seja, F : N→N dada por F(g) = f (g)+ f (g+1)+
f (g+2)+ · · ·
As quatro questões a seguir utilizam os grafos 1 e 6 da pasta graphs.
7. Trace seus Histogramas de Freqüências (em coordenadas retangulares).
8. Repita o item anterior para coordenadas logarı́tmicas.
9. Trace seus Histogramas de Freqüências em Distribuição Cumulativa.
10. Repita o item anterior para coordenadas logarı́tmicas.