Knudefarvning
 | Der er ingen kildehenvisninger i denne artikel, hvilket er et problem. (juni 2020) (Lær hvordan og hvornår man kan fjerne denne skabelonbesked) |
Knudefarvning af en graf drejer sig om tildeling af farver til grafens knuder, på en sådan måde, at vilkårlige to kantforbundne knuder har forskellige farver – dette kaldes en egentlig knudefarvning. Det er klart, at der for en vilkårlig graf findes egentlige knudefarvninger, nemlig ved at tildele hver knude en separat farve. Farverne specificeres ved en afbildning φ : V → F , hvor F kan eksempelvis være et afsnit af de naturlige tal. φ(v) er den til v ∈ V givne farve, hvor V er mængden af knuder i grafen. Det mindste antal farver i en egentlig knudefarvning af en graf G kaldes det kromatiske tal, eller det knudekromatiske tal, for G og det betegnes χ (G).
Eksempler på knudefarvning for forskellige grafer[redigér | rediger kildetekst]
- De komplette grafer Kn har alle kromatisk tal χ(Kn) = n, hvor n er et naturligt tal. Da vilkårlige forskellige knuder i Kn er kantforbundne, skal hver knude derfor have sin egen farve.
- En graf G har en tom kantmængde, hvis den kan knudefarves med én farve; dvs. χ(G) = 1. Sådan en graf består kun af en knude.
- En kreds Cn bestående af et lige antal knuder (og kanter) har kromatisk tal 2. Farvningen af grafen fås ved at lade de 2 farver alternere langs kredsen, dvs. bruge farverne skiftevis (se figuren). Hvorimod en kreds Cn af et ulige antal knuder (og kanter) har kromatisk tal 3. Forsøger man at farve grafen ved at lade 2 farver alternere langs kredsen, vil man opdage at den sidste knude der skal farves er forbundet med to kanter, hvis endeknuder har forskellige farver. Dvs. denne knude skal farves med en tredje farve ifølge definitionen af en egentlig kantfarvning.
