Em um grafo ponderado que modela ruas de uma cidade, como representar na aresta tanto a distância quanto o…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar as principais formas de organizar e representar a informação de maneira estruturada (matrizes, registros, listas e grafos) ou não estruturada (números, palavras, valores verdade).
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em um grafo ponderado que modela ruas de uma cidade, como representar na aresta tanto a distância quanto o tempo de deslocamento como dados distintos no mesmo grafo?
- A) Atribuir múltiplos atributos a cada aresta, por exemplo um par ou dicionário (distância, tempo).
- B) Um grafo ponderado não pode ter múltiplos atributos por aresta.
- C) Em um grafo ponderado, a distância deve ser ignorada ao modelar o tempo de deslocamento.
- D) Apenas um único dado deve ser registrado por aresta em um grafo ponderado.
- E) Todos os nós podem armazenar tempos e distâncias sem relação com arestas.
✅ Resposta correta: alternativa A
Resolução passo a passo
- Um grafo ponderado associa a cada aresta um peso, normalmente um único número. O problema pede que a mesma aresta (um trecho de rua) guarde duas informações distintas: a distância e o tempo de deslocamento.
- A solução usual é deixar de tratar a aresta como portadora de um único número e passar a associar a ela um conjunto de atributos. Na prática, isso pode ser feito com um par ordenado, como (distância, tempo), ou com um dicionário, como {"distancia": 500, "tempo": 40}. Cada atributo continua ligado à mesma aresta, sem criar arestas duplicadas.
- Assim, a alternativa A está correta, pois descreve exatamente essa forma de representar múltiplos dados por aresta. Ao escolher a aresta com base em um critério, o algoritmo pode usar o atributo adequado, como a distância para o caminho mais curto em metros ou o tempo para o caminho mais rápido.
- A alternativa B está errada, pois não há impedimento conceitual para uma aresta ter vários atributos; apenas a definição básica usa um peso.
- A alternativa C está errada, pois ignorar a distância ao modelar o tempo perderia informação que pode ser necessária, sem qualquer justificativa na modelagem.
- A alternativa D está errada, pois restringe o modelo a um único dado por aresta, justamente a limitação que o problema quer superar.
- A alternativa E está errada, pois distâncias e tempos de deslocamento pertencem às ruas (arestas), não aos cruzamentos (nós), e os nós não os substituem.
💡 Dica: Considere como representar múltiplas informações em um grafo.
Alternativa por alternativa
Cada aresta pode armazenar vários campos; assim algoritmos podem escolher o atributo relevante (menor tempo ou menor distância) sem alterar a estrutura do grafo.
O aluno confunde a definição básica de grafo ponderado, em que cada aresta tem um peso, com uma regra de que só é permitido um valor por aresta. A definição não proíbe que o peso seja um objeto com vários campos.
Por que engana: Confundir a definição de grafo ponderado, acreditando que apenas um atributo pode ser associado a cada aresta.
O aluno acredita que, para modelar o tempo, é preciso descartar a distância, como se o grafo só aceitasse uma grandeza. Não percebe que as duas informações podem coexistir na mesma aresta.
O aluno generaliza a ideia de peso único da definição de grafo ponderado como uma exigência obrigatória do modelo, sem considerar que o peso pode ser composto por vários dados.
O aluno desloca a informação de tempo e distância para os nós, como se os cruzamentos carregassem os dados dos trechos entre eles. Isso ignora que a distância e o tempo pertencem ao deslocamento pela rua, que é representado pela aresta.
Raio-X da questão
grafo ponderado
fixacao
grafo ponderado · atributos de arestas
Revisar como representar dados em grafos ponderados.
Confundir a definição de grafo ponderado, acreditando que apenas um atributo pode ser associado a cada aresta.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Uma prefeitura quer modelar ruas e rotas de ônibus de um bairro como um grafo direcionado com pesos (tempo de viagem)…
- Dado um grafo ponderado não dirigido onde vértices são cidades e cada aresta armazena distância (km) e limite de…
- Ao modelar rotas de ônibus de uma cidade em um algoritmo, qual estrutura de dados (registro, matriz, lista ou grafo) é…
- Uma equipe de mobilidade urbana modelou um conjunto de cidades como um grafo. Cada vértice representa uma cidade, cada…
- Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado dirigido cujas arestas representam tempos de…
- A partir de um grafo que representa cidades como vértices e as estradas como arestas, qual informação pode ser extraída?
Todas as questões de Organização e representação da informação
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog