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.

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 G=(V,E) e, sempre que existe ao menos um aluno comum entre as disciplinas i e j, colocamos uma aresta (i,j). 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 V de disciplinas em blocos (subconjuntos) que não se sobrepõem, chamados classes paralelas. Cada classe paralela é um bloco de horários:
\text{uma classe paralela} = \{\,\text{disciplinas que não compartilham nenhum aluno}\}.ã
Num design resolvível, as classes paralelas cobrem V 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 G. Uma coloração é uma função c:V\to\{1,2,\dots,k\} tal que c(i)\neq c(j) sempre que (i,j)\in E. O menor k para o qual existe essa coloração é o número cromático \chi(G). Na prática, procede-se assim:
  1. montar o grafo de conflito G;
  2. aplicar um algoritmo de coloração (por exemplo, guloso melhorado ou DSATUR);
  3. cada cor r corresponde a um horário r, e o conjunto de vértices pintados com r é um bloco de disciplinas sem conflitos.

Resposta

O método proposto é modelar as disciplinas e seus conflitos por um grafo G, depois encontrar uma coloração mínima desse grafo (algoritmos guloso ou DSATUR, por exemplo). O número de cores \chi(G) 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.

Exercícios relacionados