Het chromatisch getal van een graaf

Ik zou graag willen weten wat een chromatorisch getal van een graaf is. Ik heb op verschillende engelse sites al gezocht, maar kon geen duidelijk antwoord vinden.

erwin
Leerling bovenbouw havo-vwo - zaterdag 12 oktober 2002

Antwoord

Definitie: Een kleuring van een graaf G = (V ; E ) is een toewijzing van kleuren aan de punten van G zo dat geen twee verbonden punten dezelfde kleur hebben. Het minimale aantal kleuren nodig om de graaf G te kleuren, wordt het chromatisch getal van G genoemd.

V staat voor vertices (enkelvoud: vertex) en slaat op de verzameling van punten of knopen.
E staat voor edges (enkelvoud: edge) en slaat op de verzameling van zijden of takken.

Zie The Four Color Theorem

zaterdag 12 oktober 2002

©2001-2024 WisFaq