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

Roosterproblemen  (deel 2)
       
Nu we wat kennis over matchings hebben opgedaan kunnen we ons verdiepen in een beetje moeilijkere roosterproblemen.
Bij de vorige les hierover hadden we steeds te maken met n studenten (of klassen) die aan m vakken (of docenten) gekoppeld moesten worden, en dat moest 1-op-1:
       

       
Het was niets anders dan het kleuren van de verbindingslijnen, en voor zo min mogelijk lesperiodes moest dat dus met zo min mogelijk kleuren (alle lijnen van één kleur konden in dezelfde periode). Rechts zie je een oplossing met de kleuren rood groen en blauw. Omdat voor een bipartiete graaf geldt χ' = Δ  kan dat dus in Δ periodes. Tot zover de vorige les over roosterproblemen.

Laten we zaak wat gecompliceerder maken.....altijd leuk......

Stel bijvoorbeeld dat er maar een beperkt aantal leslokalen beschikbaar is (en dat elke les in een apart lokaal moet). Hoeveel periodes zijn er dan nodig?
Stel bijvoorbeeld dat er 24 lessen moeten worden gegeven, en dat het met de vorige les is gelukt om dat in  5 periodes te doen. Dat betekent dat er gemiddeld per periode  24/5 = 4,8 lessen worden gegeven, dus ook dat er minstens 5 lokalen beschikbaar zullen moeten zijn. De grote vraag is dan:  Kán het ook altijd met 5 lokalen? 

Het antwoord is  JA!

Daarvoor hebben we eerst een stelling nodig:

Stelling 1 
Stel dat je in een bipartiete graaf twee matchings M en N hebt gemaakt die geen gemeenschappelijke verbindingslijn hebben (die heten dan trouwens disjunct).  Als nu M > N  dan zijn er altijd twee nieuwe matchings M' en N' te maken zodat  M' = M - 1  en  N '= N + 1  (dus M eentje lager maken en N eentje hoger) die samen precies dezelfde verbindingslijnen als M en N hebben.
Ofwel:  als er meer rode lijnen dan groene zijn, dan kun je een nieuwe kleuring maken met de rode één minder en de groenen één meer.  Je kunt de kleuren rood en groen als het ware gelijkmatiger  "herverdelen".

Bewijs.
  Bekijk de graaf die bestaat uit alle lijnen van M en N samengenomen. Dan is elk deel van deze graaf  óf een even cykel met knooppunten om-en-om in M en N,  OF het is een pad met knooppunten om-en-om in M en N.
Maar omdat M > N  moet er dan wel een pad te vinden zijn dat begint en eindigt in M.
Nou:  wissel van dat pad alle kleuren  (Dus de lijnen van M gaan naar N en andersom). Dan is nu N één groter geworden en M één kleiner!
■      
       
Neem van het voorbeeld hierboven de matchings M = rood en N = blauw  (dan is M = 4 en N = 3)
Dan kun je het pad V4S5V1S4 vinden dat  rood-blauw-rood is.  Draai de kleuren daarvan om en je krijgt de nieuwe matchings M en N waarbij nu N één groter is geworden en M één kleiner:
       

       
Stelling 2.
Je kunt elke bipartiete graaf verdelen in n verschillende (disjuncte) matchings  (n ≥ Δ)   M1, M2, M3, ..., Mn   zodat ze allemaal hoogstens één in grootte verschillen.

Bewijs:
  Met de vorige stelling is dat eenvoudig.
Als twee matchings méér dan één verschillen dan pas je gewoon stelling 1 toe om groottes naar elkaar toe te brengen. Dat doe je net zolang tot er nergens meer twee matchings zijn die meer dan één verschillen.
       
Dat betekent voor ons roosterprobleem, dat er met een beperkt aantal lokalen altijd een rooster te maken is zolang dat aantal lokalen maar minstens gelijk is aan het gemiddelde aantal benodigde lokalen.  Kortom, heb je 24 lessen die in 5 periodes gegeven moeten worden, dan kan dat altijd met  4,8, dus met 5 lokalen.

N.B.
De manier van die matchings even groot maken van stelling 1 geeft meteen een recept om zo'n rooster te vinden!!
       
Voorbeeld.
       
Er zijn 7 studenten die een mondeling tentamen in 6 vakken  (dus bij 6 docenten) moeten doen. In de volgende figuur zie je welke student welk vak moet doen.
       
 
       
In graaf zie je dat  Δ = 4 dus dat moet met 4 kleuren gekleurd kunnen worden.  Hieronder zie je zo'n mogelijk kleuring met het tentamenrooster ernaast.
       

       
Je ziet dat er bij dit rooster in periode rood  6 lokalen nodig zijn, in periode blauw 4 lokalen in periode groen 3 lokalen en in periode paars ook 3 lokalen.
In totaal worden er 16 lessen in 4 periodes gegeven, dus dat zou moeten kunnen in  4 lokalen!!

Laten we rood en groen gelijker gaan maken. Er zijn twee rood-groene  paden die in aanmerking komen, want die beginnen met rood en eindigen ook met rood, namelijk  S1V2S2V1S3V3  of  S7V4S4V5
Laten we van de eerste route alle kleuren rood-groen wisselen:
       

       
Dat geeft de nieuwe graaf met het nieuwe tentamenrooster ernaast. Nu heeft rood nog 5 lokalen, maar groen 4.
Laten we vervolgens rood-paars gelijker gaan maken.
Daarvoor komen twee routes in aanmerking:  V1S3V2S2  of  S7V4
Het eenvoudigst is hier om S7V4 paars te maken:
       

       
Daarmee is een tentamenrooster gevonden met in elke periode slechts 4 benodigde lokalen. Je ziet: er zijn nog meerdere varianten mogelijk.
       

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