roosterproblemen grafentheorie

© h.hofstede (h.hofstede@hogeland.nl)

Roosterproblemen.

Stel dat er n studenten S₁, S₂, ..., S_n zijn, en m vakken V₁, V₂, ..., V_m en dat elke student in een aantal van die vakken tentamen moet doen.
Deze situatie is weer te geven met een bipartiete graaf, bijvoorbeeld zoiets:

Hier zie je 5 studenten die mondeling tentamen moeten doen in 4 vakken, met 4 bijbehorende leraren. Als we nou die verbindingslijnen gaan kleuren, en lijnen dezelfde kleur geven als de gebeurtenis op hetzelfde moment plaatsvindt, dan is het aantal kleuren van de graaf ook gelijk aan het aantal tentamenmomenten.

Uit de vorige les weten we dat voor een bipartiete graaf geldt χ' = Δ dus in dit geval weten we dat een kleuring met 3 kleuren mogelijk is want de hoogste graad is 3. Hieronder zie je een mogelijke oplossing:

Er zijn dus 3 tentamenmomenten nodig.
Je zou deze kleuring natuurlijk ook op de volgende manier in een matrix kunnen zetten:

Of in een tabelletje zoals rechts is gebeurd, waar elke kleur een nummer heeft gekregen.
Komt je bekend voor?????
In dat tabelletje moet je de getallen 1 tm 3 zetten waarbij er nooit een getal dubbel in een rij of kolom mag voorkomen...
Komt je nu bekend voor??

Tuurlijk: Het is gewoon een versimpelde SUDOKU !!!!

Ook als je de "gewone" sudoku hiernaast oplost ben je eigenlijk bezig om 9 klassen aan 9 leraren te koppelen op 9 momenten van de week (met als vreemde extra voorwaarde dat de momenten in een 3 × 3 blok moeten verschillen).

Om het helemaal moeilijk te maken zijn sommige van die momenten al vastgelegd.

Meer over roosterproblemen in een latere les.