WisFaq!

Kleuringen van grafen

Kan iemand mij helpen bij deze vraag?
Ik kom er helaas niet uit

a) Bewijs dat elke boom chromatisch getal 2 heeft.
b) geldt het omgekeerde ook?

Alvast bedankt!
Groeten

johan van west
7-12-2010

Antwoord

a) Bewijs met inductie:
We gebruiken dat lagen (niveaus) in een boom geen interconnectie kennen.

Te Bewijzen: Een boom heeft chromatisch getal 2. Dat wil zeggen dat twee kleuren voldoende is om alle knopen in de boom te kleuren zodanig dat geen twee verbonden knopen dezelfde kleur hebben.

Basis: Een boom met diepte 1 (dus 1 knoop). Deze is in te kleuren met twee kleuren waarbij er 1 kleur ongebruikt is. De gehele laag heeft dezelfde kleur = monochroom.

Hypothese: Stel dat voor een boom met diepte n geldt dat deze chromatisch getal twee heeft en dat de n-de laag monochroom is.

Inductiestap: Voor een boom met n+1 lagen geldt dat de knopen in de n+1-de laag alleen verbonden zijn met de knopen de n-de laag. Deze laag is monochroom, dus de n+1-de laag kan gekleurd worden met de kleur die niet aan de n-de laag is gegeven. Volgens de inductiehypothese heeft de boom met diepte n chromatisch getal 2. Omdat we bij het toevoegen van een laag geen nieuwe kleur hebben toegevoegd is het chromatisch getal van de n+1-diepe boom ook 2.
Q.E.D.

b)
Nee, het omgekeerde geldt niet. Bewijs met tegenvoorbeeld:
Neem een vierkant raster (bijvoorbeeld een schaakbord). Ieder hoekpunt in het raster is verbonden met 4 andere hoekpunten.
Iedere rij knopen kan om en om gekleurd worden waarbij de kleuren voor de volgende rij één knoop verspringen. Het raster heeft chromatisch getal 2, maar is geen boom, want de lagen kennen interconnectiviteit.

Coen
14-12-2010