MathJax

sexta-feira, 15 de março de 2024

2024-127

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

2024-188

Pensando no modelo de grafos aleatórios de Erdos-Renyi, qual é o limiar da probabilidade da existência de arestas para a emergência de um co...