Loading AI tools
Van Wikipedia, de vrije encyclopedie
De chromatische veelterm van een graaf geeft het aantal mogelijke geldige knopenkleuringen met kleuren, dit is het aantal kleuringen van de knopen van de graaf zodanig dat twee knopen die door een kant verbonden zijn steeds een andere kleur hebben. Het is niet nodig dat alle kleuren gebruikt worden, zolang maar aan deze voorwaarde voldaan is. Dat de functie inderdaad een veelterm is voor elke graaf kan inductief bewezen worden.
Voor een graaf die bestaat uit geïsoleerde knopen zonder kanten, kan elke knoop onafhankelijk van de andere een van de kleuren krijgen. Het totale aantal kleuringen is dus .
In een volledige graaf met knopen kan men een eerste knoop een van de kleuren geven. Een volgende knoop is steeds verbonden met deze eerste knoop en kan dus nog kleuren krijgen; een volgende enz. De chromatische veelterm van een volledige graaf is dus:
Stel a en b zijn twee knopen in een graaf die geen buren zijn, d.w.z. ze zijn niet door een boog verbonden. Dan zijn de kleuringen van G in onder te verdelen in twee types:
Type 1 is een kleuring van de graaf die men bekomt door in de kant (a,b) toe te voegen. De toevoeging van die kant schendt de vereiste van een geldige kleuring niet.
Type 2 komt overeen met de kleuring van een graaf waarin knopen a en b samengevoegd zijn tot één knoop.
Er geldt nu:
De chromatische veelterm van een graaf kan dus uitgedrukt worden in termen van de chromatische veeltermen van een graaf met een extra kant, en een andere graaf met een knoop minder. Dat kan recursief gebeuren tot men uitkomt op grafen die geen niet-naburige knopen hebben. Men verkrijgt dan de chromatische polynoom van de gegeven graaf als de som van de chromatische polynomen van complete grafen, die zoals hierboven is aangegeven veelterm zijn. Daaruit volgt dat de functie inderdaad voor elke graaf een veelterm is.
Als de graaf bestaat uit disjuncte componenten , dan is De kleuring van elke component is volledig onafhankelijk van die van de andere en het totale aantal mogelijke kleuringen is dus gewoon het product van de aantallen kleuringen van de afzonderlijke componenten.
De chromatische veelterm van een boom met n knopen is Men kan de boom opbouwen beginnend met een graaf bestaande uit twee knopen en een kant daartussen. De chromatische veelterm hiervan is . Vervolgens voegt men een voor een de andere knopen toe, waarbij elke nieuwe knoop verbonden wordt met een knoop in de reeds gevormde deelboom. De nieuwe knoop kan kleuren krijgen (enkel de kleur van de knoop waarmee hij verbonden is, is verboden). De toevoeging van een knoop vermenigvuldigt de chromatische veelterm dus met .
Isomorfe grafen hebben dezelfde chromatische veelterm; maar ook grafen die niet isomorf zijn kunnen eenzelfde chromatische veelterm hebben. Grafen met dezelfde chromatische veeltermen noemt men chromatisch equivalente grafen.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.