De digitale vraagbaak voor het wiskundeonderwijshome | vandaag | gisteren | bijzonder | gastenboek | wie is wie? | verhalen | contact |
||||||||||||||||||
|
\require{AMSmath}
Kleuringen van grafenWe hebben opgemerkt dat voor een graaf g een ondergrens voor X(G) kunnen vinden door te zoeken naar de grootste volledige deelgraaf Kn in G. AntwoordLaten we is uitgaan van het 'worst case scenario': de complete graaf (ook wel clique genoemd). In een clique zijn alle knopen verbonden met elkaar maar niet met zichzelf*, dus hebben alle knopen een andere kleur. Het chromatisch getal (X(G)) van een clique is dus gelijk aan het aantal knopen N. De maximale valentie ($
home | vandaag | bijzonder | gastenboek | statistieken | wie is wie? | verhalen | colofon ©2001-2024 WisFaq - versie 3
|