Questão 9 - Dado os contextos de fluxos máximos e grafos k-coloráveis, assinale a alternativa correta:
a) O problema de min-edge-cover pode ser resolvido com algoritmos de fluxo máximo em tempo polinomial para grafos bipartidos.
b) Todo grafo k-colorável dá origem a um grafo (k-1)-colorável se qualquer vértice for retirado.
c) Se um grafo é bipartido então o maior grau do grafo é menor que o número cromático do grafo.
d) O problema de min-vertex-cover é mais difícil do que o problema de max-independent-set para grafos quaisquer.
e) N.D.A
Ideia original: Daniel Hosomi
Nenhum comentário:
Postar um comentário