Questão FC261644
Ela representa o Estado do Ceará dividido por suas regiões. Considere a tarefa de colorir esse mapa de modo que cada região seja colorida por uma única cor e, além disso, que regiõ
Análise Combinatória (Princípio Fundamental da Contagem, Arranjos, Combinações, Permutações)
IDECAN · 2021
Observe a figura a seguir.
Ela representa o Estado do Ceará dividido por suas regiões. Considere a tarefa de colorir esse mapa de modo que cada região seja colorida por uma única cor e, além disso, que regiões com a mesma fronteira tenham que ter cores diferentes. Qual é a menor quantidade de cores distintas necessárias para a realização dessa tarefa?
- 3
- 4
- 5
- 6
Mostrar resposta e comentário
Gabarito
A
Comentário do professor
Para colorir o mapa obedecendo que regiões com a mesma fronteira não podem ter a mesma cor, precisamos do menor número de cores que evite conflitos entre vizinhas.
No desenho há um conjunto de três regiões mutuamente adjacentes (cada par entre elas partilha fronteira), formando um triângulo no grafo de adjacência. Isso implica que pelo menos \(3\) cores são necessárias, pois duas cores não bastam para colorir um ciclo ímpar de tamanho 3.
Além disso, não existe qualquer conjunto de quatro regiões todas em adjacência mútua; assim, não é preciso mais que \(3\) cores. Logo, a menor quantidade suficiente e necessária é 3.
Conteúdo do catálogo FC Concursos · Atualizado em