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

• Descreva um algoritmo em alto nível que, dado um grafo não direcionado representado por lista de adjacência, identifique…
• O que caracteriza um grafo bipartido em termos de agrupamento dos vértices e das arestas que os conectam?
• Descreva, em pseudocódigo, um algoritmo que receba como dado um grafo direcionado G = (V,E) representando dependências…
• Descreva um algoritmo em alto nível que, dado um grafo não direcionado representado por lista de adjacência, identifique…
• Descreva sucintamente como verificar se um grafo simples não direcionado é k-regular usando sua lista de adjacência; que…
• Projete um algoritmo (pseudocódigo) que, dado um grafo não direcionado representado por lista de adjacência, determine…

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