Prévia TP4 - HackMD

--- title: "Prévia do TP4" tags: [grafos, prova, bfs, dfs, dijkstra, mst, bipartido] author: "Leonardo Gloria" layout: default --- # 🧮 Prévia do TP4 **Tópicos:** BFS, DFS, Grafos Bipartidos, Dijkstra, Árvores Geradoras Mínimas (MST) **Quantidade de questões:** 16 **Instruções:** Responda todas as questões. Mostre os passos, algoritmos e estruturas utilizadas (lista de adjacência, matrizes de adjacência, tabelas de distâncias, etc.). Para questões de implementação, entregue o código comentado. --- ### 1. Dado um grafo não direcionado representando amigos em uma rede social, use **BFS** para descobrir o número mínimo de conexões necessárias para que uma pessoa alcance outra (grau de separação). --- ### 2. Usando **DFS**, determine se o grafo abaixo é **conexo**. Mostre a ordem de visita dos vértices. --- ### 3. Dado um grafo direcionado representando dependências entre tarefas, use **DFS** para determinar se há um **ciclo**. Se houver, exiba um exemplo de ciclo encontrado. --- ### 4. Construa o grafo de rotas entre cidades e, usando **BFS**, descubra **quantas cidades estão a uma distância de até 2 estradas** da capital. --- ### 5. Um grupo de estudantes formou pares de “inimizades”. Modele a relação como um grafo e use **bicoloração (2-coloring)** para verificar se é possível dividir os alunos em **dois grupos que não se odeiam**. Se não for possível, mostre um **exemplo de conflito**. --- ### 6. Dado um grafo representando funcionários e projetos (onde uma aresta indica que o funcionário trabalha em determinado projeto), determine se o grafo é **bipartido** e mostre os **conjuntos U e V**. --- ### 7. Em um mapa de cidades conectadas por rodovias com pesos representando distâncias, aplique o **Algoritmo de Dijkstra** para encontrar o **menor caminho de uma cidade origem até todas as outras**. Mostre a tabela de distâncias e o grafo resultante com o caminho mínimo. --- ### 8. Mostre por que o **Algoritmo de Dijkstra** falha em um grafo que possui **arestas com peso negativo**. Forneça um exemplo numérico simples e demonstre o erro passo a passo. --- ### 9. Um aplicativo de entregas precisa calcular o **menor tempo de entrega** entre armazéns e clientes, considerando o **tempo de tráfego como peso das arestas**. Implemente Dijkstra e exiba o tempo mínimo entre o armazém principal e cada cliente. --- ### 10. Dado o grafo de cidades e custos de ligação, aplique o **Algoritmo de Kruskal** para encontrar a **árvore geradora mínima (MST)**. Mostre as arestas escolhidas e o custo total. --- ### 11. Resolva o mesmo problema do exercício anterior usando o **Algoritmo de Prim**, iniciando de um nó diferente. Compare as árvores obtidas e diga se são **únicas** ou **diferentes**. --- ### 12. Explique como o uso de **disjoint set (Union-Find)** ajuda a detectar **ciclos** durante a construção de uma árvore geradora mínima. --- ### 13. Um engenheiro deseja conectar computadores com cabos de menor custo possível. Monte a árvore geradora mínima e indique qual seria o **ganho percentual** em relação à soma de todos os cabos possíveis. --- ### 14.  Você recebeu um mapa com **N ilhas e M pontes**. Cada ponte tem um **custo de construção**. O governo quer ligar todas as ilhas gastando o mínimo possível. Se não for possível conectar todas, imprima **“Impossível”**. *(Dica: use Kruskal.)* --- ### 15.  Dada uma matriz **N×N** representando um mapa onde cada célula tem um custo de travessia, calcule o **custo mínimo** para ir do canto superior esquerdo ao inferior direito, movendo-se apenas nas quatro direções (cima, baixo, esquerda, direita). *(Desafio: resolver usando Dijkstra em matriz – grafo implícito.)* ### 16. MESA - Mesa da Sra Montagny! Já comentamos as festas da Sra. Montagny à beira do Lake Louise em Banff. Nas suas festas ela se compromete a resolver um outro problema que faz tremer organizadores de jantares em todo o mundo: onde sentar os convidados. A magnata simplifica bastante o problema pedindo aos convidados, no mesmo questionário já comentado, que anote na lista dos convidados aqueles que desejariam ter à sua frente na mesa do jantar. A idéia é ter seus amigos sempre à sua frente, para que a conversa possa fluir melhor. A habilidade da socialite é tamanha que ela foi contratada pelo Fairmont Banff Springs hotel (hotel em que vão ocorrer as finais mundiais do ICPC em 2008: Hotel) para trabalhar no arranjo de mesas de banquete. Sua tarefa neste problema é auxiliar novamente a magnata. Dados os desejos dos convidados, seu programa deve decidir se é possível dispô-los numa mesa de forma que cada convidado tenha todos os seus amigos no lado oposto da mesa. ## Entrada A entrada é composta de diversas instâncias. A primeira linha de cada instância contém dois inteiros n (1 <= n <= 100) e m (0 <= m <= n(n-1)/2), onde n é o número de convidados e m é o número de relações de amizade. Cada uma das m linhas seguintes contém dois inteiros u e v indicando que u é amigo de v e v é amigo de u, onde 1 <= u,v <= n. A entrada termina com final de arquivo. ## Saída Para cada instância, você deverá imprimir um identificador Instancia k, onde k é o número da instância atual. Na linha seguinte imprima sim se é possível e nao caso contrário. Após cada instância imprima uma linha em branco. ### Exemplo: ``` Entrada: 3 3 1 2 2 3 1 3 4 3 1 2 1 3 1 4 Saída: Instancia 1 nao Instancia 2 sim ``` --- **Observações do professor:** - Use notação clara (V, E) e indique a representação escolhida (lista de adjacência, matriz de adjacência, etc.). - Para a correção, considerar passos intermediários e justificativa além da resposta final.