Projete um grafo para representar o acervo de uma biblioteca escolar em que vértices são livros e arestas…

Questão

Projete um grafo para representar o acervo de uma biblioteca escolar em que vértices são livros e arestas indicam 'mesma categoria' ou 'mesmo autor'. Explique como permitir que um livro pertença a várias categorias, qual estrutura de dados escolheria (lista de adjacência ou matriz) e por quê, e descreva como realizar uma busca por livros relacionados a partir de um título.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Modelo: usar um grafo bipartido com vértices do tipo Livro e vértices do tipo Categoria/Autor; ligar cada livro às categorias e autores correspondentes. Assim um livro pode ter várias arestas para várias categorias. Escolha lista de adjacência porque o grafo é esparso e permite percursos eficientes. Para buscar livros relacionados a um título: localizar o vértice do livro, coletar vizinhos (categorias/autores) e então listar todos os livros conectados a essas categorias/autores (busca em largura limitada a 2 saltos para obter relacionados). Opcional: atribuir rótulos às arestas para diferenciar autor/categoria.

Explicação

O uso de um grafo bipartido permite representar eficientemente a relação entre livros, categorias e autores, possibilitando que um livro esteja vinculado a múltiplas categorias. A lista de adjacência é adequada devido à natureza esparsa do grafo, otimizando a busca e a manipulação de dados. A estratégia de busca em largura limitada a 2 saltos facilita a identificação de livros relacionados, aproveitando as conexões estabelecidas no grafo.

Raio-X da questão

Questões parecidas com resolução

• Para organizar uma exposição escolar, a turma desenhou as ligações diretas entre quatro setores. Cada letra indica um…
• Técnicos instalam uma rede de comunicação por cabos entre os postos de uma reserva ambiental. Os postos são Riacho…
• Moradores acompanham a criação de um aplicativo para orientar deslocamentos durante a feira do bairro. No mapa…
• Durante os preparativos para uma feira de ciências no bairro, a organização desenhou um mapa digital dos caminhos…
• Por que uma rede de aviso precisa continuar funcionando mesmo quando um ponto para de operar? Em uma cidade litorânea, a…
• — Dá para passar por todas as ruas sem repetir nenhuma? — perguntou um morador, ao ver o triciclo do mutirão de coleta…

Todas as questões de Programação - Propriedades de grafos