Lets say that our undirected graph consists of vertices representing subjects, and edges representing student-subject relationship. In particular an edge $(i,j)$ is present between subjects $i$ and $j$ is there is a student taking both subjects.

We are going now to assign each vertex a "label" or a "color" representing its time slot (e.g. color$(i)=$ "4th time slot in Monday". We put a restriction that two neighboring vertices (i.e. having an edge between them: a student is taking them both) cannot have the same color; because the student taking both can not attend more than one subject in a time slot. This is the graph vertex coloring problem: given a graph, color its vertices such that no neighboring vertices have the same color. The trivial solution is to give each vertex a unique color. But this is not an interesting solution because you have limited number of color (time slots) and many subject; usually more than the number of time slots.

We might be interested in minimizing the number of colors used. The minimum number of colors needed to color a graph is called the graph's chromatic number, and computing that number is an NP-complete problem, and so there is no efficient algorithm to solve it exactly in the worst case unless P=NP. We may be interested though in a way to approximate it, there is an algorithm to approximate the chromatic number within a multiplicative factor. Notice that knowing the minimum number of colors doesn't mean we found such a coloring.

## No comments:

Post a Comment