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

• Em períodos de calor intenso, o comitê de saúde de uma escola pretende divulgar, antes do recreio, um boletim na rádio…
• Por que algumas oficinas de um centro cultural não podem ocorrer no mesmo horário? Na programação de sábado, Robótica…
• — O alerta saiu de Arumã, mas o enlace entre Caju e Ema parou de funcionar — avisou a operadora da central fluvial…
• Por que duas oficinas muito procuradas não podem ocorrer no mesmo horário? Em uma situação fictícia, a organização de…
• — Se eu voltar pelo mesmo corredor, chego de novo na entrada? — perguntou uma visitante ao testar o aplicativo de um…
•  Ontem o mapa do festival me mandou dar uma volta enorme  reclamou uma visitante. Para reduzir aglomeracoes, a…

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