p2_antiga CR UFABC

Prévia do material em texto

Prova Substitutiva de BCM0506 - 17/8/16
Nome e RA do aluno: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
• Não é permitido ausentar-se da sala durante a prova (sair e voltar).
• Não é permitido usar dispositivos eletrônicos (fones de ouvido, celular, etc.)
• Justifique suas respostas dando os passos da solução, mesmo que diretamente no desenho da
folha de questões. Não basta escrever só o resultado final!
• A Prova tem 3 questões com 10 ı́tens ao todo, cada um valendo 1 ponto. Duração: 110
minutos (1h50min),
1. Para o grafo da Figura 1 obtenha: (a) sua árvore de Prim; (b) o custo mı́nimo de conexão entre
X e T ; (c) a probabilidade de conexão entre os vértices.
Figura 1
2. Considere o grafo da Figura 2. Calcule:
(a) Centralidade de grau em cada vértice;
(b) Centralidade de betweenness em cada
vértice;
(c) Distância média entre os vértices;
(d) O coeficiente de clusterização do grafo.
(e) Descubra se ele é planar ou não.
3. Na Figura 3 temos os roteadores W a
Z. Os custos de conexão vêm escritos sobre
as arestas, são constantes, e usa-se Distance-
Vector para reduzir o custo entre roteadores.
Suas tabelas são renovadas na ordem al-
fabética.
a) Qual será a tabela de Y no instante t = 1?
b) Qual será a tabela de Z do instante t = 2?
Figura 2 Figura 3
****** BOA PROVA ******