Imagem: rede representando estudantes (Mariana, Lucas, Ana) e clubes (Robótica, Teatro). Arestas…

Questão

Imagem: rede representando estudantes (Mariana, Lucas, Ana) e clubes (Robótica, Teatro). Arestas: Mariana–Robótica, Lucas–Robótica, Lucas–Teatro, Robótica–Teatro. Avalie se a rede é bipartida e proponha um algoritmo para testar e explicar o resultado.

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

Resposta esperada

Para testar bipartição use uma coloração por BFS/DFS: escolher um vértice, atribuir cor A, colorir vizinhos com cor B, continuar; se encontrar uma aresta conectando dois vértices da mesma cor, não é bipartido. Aplicando aos dados: particionaríamos estudantes {Mariana, Lucas, Ana} e clubes {Robótica, Teatro} inicialmente; porém existe aresta Robótica–Teatro (entre clubes), o que gera uma aresta dentro de uma mesma partição. Ao executar BFS com coloração, ao processar Robótica e visitar Teatro, ambas receberiam cores conflitantes (ou já teriam a mesma cor), revelando o conflito: há uma aresta entre nós do mesmo conjunto, portanto a rede não é bipartida. A saída do algoritmo deve indicar 'não bipartido' e reportar a aresta conflito (Robótica–Teatro). Como alternativa de correção, remover ou reclassificar a aresta entre clubes transformaria a rede em bipartida se nenhuma outra aresta interna existir.

Explicação

A rede é considerada bipartida se seus vértices podem ser divididos em dois conjuntos, onde não existem arestas conectando vértices do mesmo conjunto. No caso apresentado, a aresta entre Robótica e Teatro conecta dois clubes, o que viola a condição de bipartição. O algoritmo de coloração revela esse conflito ao encontrar vértices da mesma cor conectados, confirmando que a rede não é bipartida.

Raio-X da questão

Questões parecidas com resolução

• Descreva como representar a rede de amizades de uma turma como um grafo e detalhe um procedimento passo a passo para…
• Em uma competição escolar, os alunos formaram equipes para resolver problemas de lógica. Cada equipe desenhou um grafo…
• Ao modelar uma rede de colaboração entre alunos em um algoritmo — onde conexões representam quem já trabalhou com quem —…
• Em um projeto, uma turma quer representar uma rede social da escola. Cada estudante pode estar ligado a alguns colegas…
• Explique como um grafo pode ser utilizado para representar a rede de contatos em uma escola.
• Descreva como você pode representar um grafo para mostrar as amizades entre colegas de classe. Utilize exemplos.

Todas as questões de Programação - Programação usando grafos e árvores