Questão FC236140
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 dessa matriz, verifica-se que a mediana do grafo corresponde ao vértice de número
- 1
- 2
- 3
- 4
- 5
Mostrar resposta e comentário
Gabarito
Certo
Comentário do professor
A partir da matriz de distâncias (resultado do algoritmo Floyd), a mediana do grafo é o vértice cuja soma das distâncias a todos os demais vértices é mínima.
Para o vértice 3 somamos as entradas da sua linha: \(4+2+0+1+3+6=16\). Essa quantidade representa a distância total de 3 a todos os vértices do grafo.
Como essa soma é a menor possível entre os vértices (portanto fornece a menor distância agregada ao conjunto), conclui‑se que a mediana do grafo é o vértice 3.
Conteúdo do catálogo FC Concursos · Atualizado em