Exercício MACS 11º Ano (2016 F2): Grafos e Coloração Mínima de Modalidades

3.
No Encontro Desportivo Internacional, existem atletas que estão inscritos em mais do que uma modalidade.
Para que todos consigam realizar um treino de adaptação ao estádio onde se irão realizar as provas, vai ser criado um horário com blocos de utilização das instalações.
De cada bloco deverão fazer parte as modalidades nas quais não haja atletas inscritos simultaneamente.
A constituição de cada bloco será definida considerando os dados da Tabela 3, na qual o símbolo X indica as modalidades que podem ser inseridas num mesmo bloco.

Tabela 3

Modalidades	A	B	C	D	E	F	G	H
A			X	X		X
B							X
C	X					X		X
D	X							X
E
F	X		X
G		X
H				X

Determine, tendo em conta as condições dadas, o número mínimo de blocos que será necessário constituir, de modo que todos os atletas possam realizar o treino de adaptação em todas as modalidades em que estão inscritos.
Na sua resposta:
– apresente um grafo que modele a situação;
– identifique as modalidades que constituem cada um dos blocos.

Indicar o número mínimo de blocos que é necessário constituir (4) Exemplo de um grafo que modele a situação: A H B G F E D C