Questão FC236139
Considere a matriz para responder à questão. Os elementos dessa matriz são os valores dos caminhos mínimos, entre os 6 vértices de um grafo não orientado, que resultaram da aplicaç
Outras Questões de Matemática
CESGRANRIO · 2012
Considere a matriz para responder à questão.
Os elementos dessa matriz são os valores dos caminhos mínimos, entre os 6 vértices de um grafo não orientado, que resultaram da aplicação do Algoritmo de Floyd.
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 3 | 4 | 3 | 7 | 10 |
| 2 | 3 | 0 | 2 | 3 | 5 | 8 |
| 3 | 4 | 2 | 0 | 1 | 3 | 6 |
| 4 | 3 | 3 | 1 | 0 | 4 | 7 |
| 5 | 7 | 5 | 3 | 4 | 0 | 3 |
| 6 | 10 | 8 | 6 | 7 | 3 | 0 |
A partir dos valores dos caminhos apresentados na matriz, verifica-se que o centro do grafo corresponde ao vértice de número
- 6
- 5
- 4
- 3
- 2
Mostrar resposta e comentário
Gabarito
D
Comentário do professor
A matriz apresenta as distâncias mínimas entre vértices obtidas pelo Algoritmo de Floyd. Para cada vértice calculamos a sua excentricidade, definida por \(e(v)=\max_{u} d(v,u)\), ou seja, a maior distância de v a qualquer outro vértice.
Tomando o máximo de cada linha da matriz obtemos: 1 → 10, 2 → 8, 3 → 6, 4 → 7, 5 → 7, 6 → 10. Esses valores são as excentricidades dos vértices.
O raio do grafo é a menor excentricidade; aqui o raio é 6. O centro do grafo é o conjunto de vértices cuja excentricidade é igual ao raio.
Como apenas o vértice com número 3 tem excentricidade 6, conclui‑se que o centro do grafo corresponde ao vértice 3.
Conteúdo do catálogo FC Concursos · Atualizado em