Considere o seguinte grafo simples \( G \):
\[ V(G) = \{a, b, c, d, e, f, g\} \]
\[ E(G) = \{ab, ac, ad, bc, be, cd, cf, dg, ef, fg\} \]
Se o grafo \( G \) representa um mapa de cidades onde vértices adjacentes compartilham uma fronteira, determine o número mínimo de cores \( \chi(G) \) que podem ser utilizadas para colorir \( V(G) \), garantindo que vértices adjacentes tenham cores distintas.
a) \( \chi(G) = 6\)
b) \( \chi(G) = 5\)
c) \( \chi(G) = 4\)
d) \( \chi(G) = 3\)
e) NDA
Ideia original de: Glaymar A. França
Nenhum comentário:
Postar um comentário