Flashcard FC264282
Se um grafo possui um clique de tamanho 3 (triângulo) mas não contém um clique de tamanho 4, qual o menor número de cores necessárias para colorir os vértices de modo que vértices
Análise Combinatória (Princípio Fundamental da Contagem, Arranjos, Combinações, Permutações)
IDECAN · 2021
Se um grafo possui um clique de tamanho 3 (triângulo) mas não contém um clique de tamanho 4, qual o menor número de cores necessárias para colorir os vértices de modo que vértices adjacentes tenham cores diferentes?
Mostrar resposta e comentário
Resposta
3Explicação:
Um clique de tamanho 3 obriga pelo menos 3 cores, pois cada vértice do triângulo é adjacente aos outros dois.
Se não há quatro vértices mutuamente adjacentes, não é necessário usar mais que 3 cores; portanto o menor número suficiente é 3.
Exemplo:
Considere o grafo com vértices \(A,B,C,D\) onde \(A,B,C\) formam um triângulo e \(D\) é adjacente apenas a \(A\) e \(B\).
Atribuição de cores: \(A=1,\;B=2,\;C=3,\;D=3\).
Atribuição válida porque \(D\) não é adjacente a \(C\), e assim 3 cores bastam.
⬇️ Assista à vídeoaula ⬇️ Aula sobre Princípio Fundamental da Contagem
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/261644
Conteúdo do catálogo FC Concursos · Atualizado em