Descreva, em termos algorítmicos e usando a variável 'cor', como verificar se um grafo simples não direcionado…

Questão

Descreva, em termos algorítmicos e usando a variável 'cor', como verificar se um grafo simples não direcionado é bipartido; qual condição local indica conflito?

1. A) Procurar ciclos de comprimento par; se existir algum, o grafo não é bipartido.
2. B) Colorir vértices conforme paridade do grau (par/ímpar); aresta entre mesmos paridade é conflito.
3. C) Executar DFS e declarar não-bipartido sempre que for encontrado qualquer ciclo.
4. D) Tentar colorir com três cores; se possível, o grafo é bipartido.
5. E) Executar BFS/DFS atribuindo alternadamente duas cores; ao explorar uma aresta, se seus extremos tiverem a mesma cor há conflito ? grafo não é bipartido; caso contrário é bipartido.

✅ Resposta correta: alternativa E

Resolução passo a passo

1. Um grafo é bipartido quando seus vértices podem ser divididos em dois conjuntos, de modo que toda aresta ligue vértices de conjuntos diferentes. Equivalentemente, dá para colorir os vértices com duas cores sem que dois vértices adjacentes recebam a mesma cor.
2. Algoritmo com a variável cor: escolha um vértice inicial de um componente, faça cor[inicial] = 0 e coloque-o em uma fila (BFS) ou pilha (DFS). Enquanto houver vértices a explorar, retire um vértice u; para cada vizinho v de u: se cor[v] não estiver definida, faça cor[v] = 1 - cor[u] e insira v na estrutura; se cor[v] já estiver definida e cor[v] = cor[u], existe conflito e o grafo não é bipartido.
3. A condição local de conflito é: existe uma aresta (u, v) com cor[u] = cor[v]. Se nunca ocorrer, todas as arestas ligam cores diferentes e o grafo é bipartido. Repete-se o processo para cada componente desconectado.
4. Conferindo a alternativa E, ela descreve exatamente esse procedimento: atribuição alternada de duas cores, e conflito quando os extremos de uma aresta têm a mesma cor. Gabarito confirmado.
5. Por que as outras estão erradas: A confunde a condição, pois o que impede a bipartição é a existência de ciclo de comprimento ímpar, não de ciclo par. B usa a paridade do grau, que não tem relação com a bipartição. C trata qualquer ciclo como conflito, mas ciclos pares são compatíveis com grafos bipartidos. D usa três cores, o que corresponde à coloração cromática de número 3 e não ao teste de bipartição, além de inverter a lógica.

💡 Dica: Considere a definição de um grafo bipartido e como as cores podem representar os conjuntos.

Alternativa por alternativa

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