A Comunicação e Redes

Lista 3 Comunicação e Redes

Nome: Matheus Augusto Pinto R.A 11201721392

Profº Guilherme Mota

OBS: As questões onde está marcado “foto” estão no final desse arquivo. Elas foram feitas à mão e depois tirado foto.

1-a) Um grafo aleatório G pode ser gerado através dos passos seguintes. Para cada par de vértices e no conjunto de todos os pares, deve ser decidido por algum experimento aleatório se e deve ou não deve ser uma aresta de G, como por exemplo o lançamento de uma moeda, considerando que a moeda apresenta a probabilidade p de resultar “cara” em um lançamento. O grafo inicialmente não contém arestas, isto é, G = (V,∅) e, para cada par de vértices {i,j} ∈ V , a moeda é lançada. Se o resultado for “cara”, a aresta {i,j} é colocada no grafo, isto é, {i,j} ∈ E(G); caso contrário (“coroa”), {i,j} /∈ E(G). Um grafo genérico assim declarado é denotado por G(n,p) e o chamamos de grafo aleatório com n vértices e probabilidade de aresta p.

A principal utilidade dos grafos aleatórios é responder perguntas sobre as propriedades dos grafos encontrados, por exemplo, em redes biológicas, de cooperação científica entre outras.

b) Os vértices do G(n,p) não podem ter graus muitos diferentes pois não existem vértices mais prováveis e cada aresta irá existir com uma probabilidade fixa p. Logo, para uma quantidade muito grande de vértices, cada um irá se conectar em média com o mesmo número de outros vértices. Assim como prevê o fenômeno do mundo pequeno.

c) Foto

d) A propriedade de G(n,p) que o torna importante para modelar algumas redes complexas é a de que como todas as arestas existem de acordo com a mesma probabilidade, elas estão muito bem distribuídas no grafo, causando esse efeito de expansão.

e) p deve ser 0 para que G(n,p) seja um grafo vazio, pois é nula a probabilidade de qualquer aresta ser gerada. Além disso, p deve ser 1 para que G(n,p) seja um grafo completo já que é certo que todas as arestas possíveis irão ocorrer.

2) Foto

3) O problema do grafo G(n,p) que motivou o desenvolvimento do modelo de grafos aleatórios de Watts-Strogatz foi o fato de que ele apresenta um baixo coeficiente de agrupamento, o que não é desejado em alguns problemas.

Passo determinístico: utilizando uma estrutura de anel iremos adicionar arestas próximas do vértice em questão. Isso irá aumentar o coeficiente de agrupamento e a conectividade do grafo.

Passo probabilístico: teremos que cada aresta ligada ao vértice v irá mudar de posição com probabilidade p. Essa aresta deverá mudar de posição uniformemente ao acaso sem gerar arestas múltiplas nem laços.

4) Foto

5) Foto

6) Pelo fato da probabilidade p ser pequena mudamos poucas arestas de posição, logo, a chance de todos os vértices terem grau similar é alto. Entretanto, diversas redes contêm vértices com grau muito maior que a maioria dos vértices, que são chamados de HUBS.