p1 CR UFABC 2016

Prévia do material em texto

Universidade Federal do ABC
Disciplina: Comunicação e Redes - BCM0506
Professor: Valério Ramos Batista
Quadrimestre: 2/2016 Data: 13/7/2016
Parte 2 - Questões de Múltipa-Escolha
1. Considere um grafo conexo G e dois de seus vértices V1 e V2 tomados ao acaso. Seja p a probabilidade de serem vizinhos e C o menor
caminho que os conecta. Se G representa uma rede Small-World, então:
A. Há grandes chaces de termos p pequeno e C curto.
B. Há grandes chaces de termos p ∼= 50% e C comprido.
C. Há poucas chaces de termos p pequeno e C curto.
D. Há grandes chaces de termos p grande e C comprido.
2. Considere um grafo conexo G que representa uma rede Scale-Free. Então
A. Poucos vértices têm muitas arestas incidentes, e muitos vértices têm poucas.
B. Muitos vértices têm muitas arestas incidentes, e poucos vértices têm poucas.
C. Cerca de metade dos vértices tem muitas arestas incidentes, e a outra metade poucas.
D. Cada vértice têm aproximadamente o mesmo número de arestas incidentes.
3. Os principais tipos de rede estudados neste curso são
A. ”Mundo Pequeno”, ”Sem Escala” e ”Aleatórias”.
B. ”de Königserg”, ”Ordenadas” e ”Aleatórias”.
C. ”Mundo Pequeno”, ”de Königsberg” e ”Aleatórias”.
D. ”Ordenadas”, ”Sem Escala” e ”Mundo Pequeno”.
4. Num grafo G, a Ordem, Tamanho e Diâmetro são, respectivamente
A. Número de vértices, de arestas e o maior caminho dentre os menores vértice-a-vértice.
B. Número de arestas, de vértices e o maior caminho dentre os maiores vértice-a-vértice.
C. Número de arestas, de vértices e o menor caminho dentre os menores vértice-a-vértice.
D. Número de vértices, de arestas e o menor caminho dentre os maiores vértice-a-vértice.
5. Considere um grafo conexo e ponderado G, e tome dois de seus vértices V1, V2. Seja P ⊂ G uma árvore de Prim. Então, para ir de V1 a V2
com custo mı́nimo
A. Nem sempre é obtido seguindo por P ; tem que utilizar o Algoritmo de Dijkstra.
B. Pode ser obtido seguindo por P , pois coincidirá com o custo dado pelo Algoritmo de Dijkstra.
C. Nunca pode ser obtido seguindo P , pois Dijkstra sempre dá um custo bem menor.
D. Só pode ser obtido seguindo por P , pois o Algoritmo de Dijkstra nem sempre é válido.
6. Considere o grafo da Figura 1. A Busca em Largura de A para F nos dá
A. A → B → E → F .
B. A → B → D → E → F .
C. A → B → C → D → E → F .
D. A → B → C → E → F .
7. Considere o grafo da Figura 1. A Busca em Profundidade de G para F , segundo Ordem Alfabética, nos dá
A. G → D → A → B → C → E → F .
B. Não é possı́vel, pois D segue C na Ordem Alfabética.
C. G → D → A → B → E → F .
D. G → D → E → F .
8. No grafo da Figura 2, os custos mı́nimos de A para S, de S para B, e de B para A são, respectivamente
A. 11, 9 e 19.
B. 12, 9 e 12.
C. 12, 11 e 12.
D. 11, 12 e 19.
9. No grafo da Figura 2, os valores de µin, µout, e de p2 a p5 são, respectivamente,
A. 2, 2, 0, 1/5, 3/5 e 1/5.
B. 2, 3, 0, 2/5, 2/5 e 1/5.
C. 3, 2, 1/5, 1/5, 2/5 e 1/5.
D. 3, 3, 1/5, 2/5, 1/5 e 1/5.
10. No grafo da Figura 3, a probabilidade de conexão entre os vértices é de
A. 49,1% B. 61,4% C. 57,3% D. 32,6%
Parte 3 - Questões Dissertativas
1. A cidade de Brückchenberg é cortada por um rio, no qual há três ilhas acessı́veis por pontes. Denominando as partes continentais de 1 e 2, e
as ilhas de 3, 4 e 5, para Brückchenberg podemos escrever sua matriz de conexão A, cujas entradas aij indicam o número de pontes entre as
regiões. Claro, diag(A) é nula, e para j > i sabe-se: a15 = 0, aij = 2 se j = 2 + i, e caso contrário aij = 1. Pergunta: é possı́vel visitar
todas as regiões passando em cada ponte somente uma única vez? Se for, faça um desenho do passeio indicando cada passagem sobre ponte
com um seta enumerada (1, 2, 3,...) Senão, enuncie algum resultado visto no curso para provar que tal passeio não existe.
Figura 1 Figura 2 Figura 3