Em uma universidade, alguns alunos estão matriculados em várias disciplinas. A instituição precisa montar uma tabela de exames onde:
- Nenhum aluno tenha dois exames marcados ao mesmo tempo;
- O número total de horários disponíveis para os exames seja o menor possível (não quer usar 50 horários diferentes).
(a) Explique por que pode haver conflitos de horários entre exames quando alunos cursam disciplinas em comum.
(b) Mostre como o uso de designs combinatórios, como designs de blocos, pode ajudar a organizar os exames em blocos de horários sem conflitos.
(c) Proponha um método para minimizar o número de horários necessários e garanta que nenhuma disciplina que compartilha alunos fique no mesmo horário.
(a) Explique por que pode haver conflitos de horários entre exames quando alunos cursam disciplinas em comum.
(b) Mostre como o uso de designs combinatórios, como designs de blocos, pode ajudar a organizar os exames em blocos de horários sem conflitos.
(c) Proponha um método para minimizar o número de horários necessários e garanta que nenhuma disciplina que compartilha alunos fique no mesmo horário.
Passo 1
O enunciado fala de agendar exames de várias disciplinas respeitando duas condições: (i) nenhum aluno deve ter dois exames ao mesmo tempo e (ii) queremos usar o menor número possível de horários. O conteúdo principal aqui envolve teoria de grafos (para modelar conflitos entre disciplinas) e designs combinatórios (para agrupar disciplinas em “blocos” de horários sem conflitos).
Passo 2
Quando um mesmo aluno está inscrito em duas disciplinas, essas duas disciplinas não podem ter exame no mesmo horário. Isso gera um conflito que podemos representar assim: cada disciplina vira um vértice num grafo
e, sempre que existe ao menos um aluno comum entre as disciplinas
e
, colocamos uma aresta
. Então, qualquer conjunto de vértices sem arestas internas (um conjunto independente) corresponde a disciplinas que podem ter exame simultâneo sem criar conflito de aluno.
Passo 3
Um design de blocos — e em especial um design balanceado incompleto resolvível — nos fornece uma forma de particionar o conjunto
de disciplinas em blocos (subconjuntos) que não se sobrepõem, chamados classes paralelas. Cada classe paralela é um bloco de horários:
Num design resolvível, as classes paralelas cobrem
e são mutuamente disjuntas, de modo que podemos usar cada classe como um horário distinto. A vantagem é que o próprio design garante que dentro de cada bloco não haja arestas do grafo de conflito.
Passo 4
Para minimizar o número de horários, podemos ver isso como o problema de coloração de vértices do grafo
. Uma coloração é uma função
tal que
sempre que
. O menor
para o qual existe essa coloração é o número cromático
. Na prática, procede-se assim:
- montar o grafo de conflito
; - aplicar um algoritmo de coloração (por exemplo, guloso melhorado ou DSATUR);
- cada cor
corresponde a um horário , e o conjunto de vértices pintados com é um bloco de disciplinas sem conflitos.
Resposta
O método proposto é modelar as disciplinas e seus conflitos por um grafo
, depois encontrar uma coloração mínima desse grafo (algoritmos guloso ou DSATUR, por exemplo). O número de cores
será o menor número de horários necessários, e cada cor define o conjunto de disciplinas que podem ter exame simultaneamente sem causar conflito de aluno.