Tänk dig att du ska färglägga en karta så att inga angränsande länder har samma färg. Detta är exakt vad graffärgning handlar om! Det visar sig att varje karta kan färgas med endast fyra färger - detta är det berömda fyrfärgsproblemet som tog över 100 år att bevisa. Graffärgning har tillämpningar från schemaläggning till registrallokering i kompilatorer.

Fördjupning

Graffärgning innebär att tilldela färger till noder i en graf så att inga intilliggande noder har samma färg. Det kromatiska talet χ(G) är det minsta antalet färger som behövs. Problemet är NP-komplett i allmänhet, men har effektiva approximationsalgoritmer och exakta lösningar för speciella grafklasser. Färgningsteori kopplar till algebraisk grafteori och har djupa kopplingar till topologi.

Grundläggande definitioner

En k-färgning av graf G är en funktion f: V(G) → {1,2,...,k} så att f(u) ≠ f(v) för alla intilliggande noder u,v. Det kromatiska talet χ(G) är det minsta k för vilket G har en k-färgning. En graf är k-färgbar om χ(G) ≤ k.

Kromatiska tal för vanliga grafer

Kompletta grafen Kₙ:

· χ(Kₙ) = n (alla noder intilliggande)

Cykel Cₙ:

· χ(Cₙ) = 2 om n är jämnt

· χ(Cₙ) = 3 om n är udda

Bipartit graf:

· χ(G) = 2 för alla icke-tomma bipartita grafer

Träd:

· χ(T) = 2 för alla träd med minst en kant

· χ(T) = 1 för träd med endast en nod

Giriga färgningsalgoritmer

Den giriga algoritmen färgar noder en i taget genom att välja lägsta möjliga färg. Resultatet beror på nodordningen, men algoritmen garanterar en färgning med högst Δ(G)+1 färger där Δ(G) är maximal grad. Olika ordningsstrategier ger olika prestanda.

Girig färgningsalgoritm

Algoritm GreedyColoring(G, ordning):

1. Ordna noderna enligt given strategi

2. För varje nod v i ordningen:

a. Färger_använda = {färger på v:s färgade grannar}

b. Tilldela v den minsta färg ∉ Färger_använda

3. Returnera färgningen

Vanliga ordningsstrategier:

· Largest-first: Högsta grad först

· Smallest-last: Lägsta grad sist (Welsh-Powell)

· Random: Slumpmässig ordning

Brooks sats

Sats (Brooks): För sammanhängande graf G som inte är udda cykel eller komplett graf gäller χ(G) ≤ Δ(G).

Bevis-idé:

· Ordna noder så att de två sista har gemensam granne

· De sista två noderna kan färgas med samma färg

· Girig algoritm använder högst Δ(G) färger

Undantag:

· Udda cykler: χ(C₂ₙ₊₁) = 3 > 2 = Δ(C₂ₙ₊₁)

· Kompletta grafer: χ(Kₙ) = n > n-1 = Δ(Kₙ)

Planära grafer och fyrfärgssatsen

En planär graf kan ritas i planet utan korsande kanter. Fyrfärgssatsen säger att alla planära grafer är 4-färgbara. Beviset från 1976 var det första stora matematiska resultatet som krävde datorhjälp. Femfärgssatsen har ett elegant handbevis från 1890.

Bevis av femfärgssatsen

Sats: Alla planära grafer är 5-färgbara

Bevis (induktion över antal noder):

1. Basfall: Grafer med ≤5 noder trivialt 5-färgbara

2. För graf G med n>5 noder:

· Planär graf har nod v med grad ≤5 (följer av Eulers formel)

· Om deg(v) ≤ 4: Ta bort v, färga resten (induktion), sätt tillbaka v

· Om deg(v) = 5: Specialfall med Kempe-kedjor

3. I båda fallen kan G färgas med 5 färger

Perfekta grafer

En graf G är perfekt om χ(H) = ω(H) för alla inducerade subgrafer H, där ω(H) är kliqstorleken. Perfekta grafer inkluderar bipartita grafer, chordale grafer och jämna hål-fria grafer. Den starka perfekta grafsatsen karakteriserar perfekta grafer.

Starka perfekta graf-satsen

Sats (Chudnovsky et al., 2006): En graf är perfekt om och endast om den inte innehåller udda hål eller udda anti-hål som inducerad subgraf.

Definitioner:

· Hål: Inducerad cykel av längd ≥4

· Anti-hål: Komplementet av ett hål

· Udda hål/anti-hål: Längd udda

Exempel perfekta grafklasser:

· Bipartita grafer (inga udda hål)

· Chordale grafer (inga hål av längd ≥4)

· Komplementära bipartita grafer

Listfärgning och valfrihet

I listfärgning har varje nod en lista av tillåtna färger. Listfärgningstal χₗ(G) är det minsta k så att G kan listfärgas när alla listor har storlek k. Överraskande nog kan χₗ(G) vara mycket större än χ(G). Gal's förmodan säger att χₗ(G) = χ(G) för bipartita grafer.

Skillnad mellan vanlig och listfärgning

Komplett bipartit graf K₂,₄:

· χ(K₂,₄) = 2 (bipartit)

Men med listor:

· Låt A = {a₁, a₂}, B = {b₁, b₂, b₃, b₄}

· Lista för a₁: {röd, blå}

· Lista för a₂: {röd, blå}

· Lista för bᵢ: {röd, grön} för i=1,2

· Lista för bⱼ: {blå, grön} för j=3,4

Omöjligt att färga:

· Om a₁ = röd, då a₂ = blå, b₃,b₄ = grön, b₁,b₂ = grön (konflikt)

· Om a₁ = blå, då a₂ = röd, b₁,b₂ = grön, b₃,b₄ = grön (konflikt)

Tillämpningar

Graffärgning har många praktiska tillämpningar: schemaläggning (tentamensscheman, tågscheman), registrallokering i kompilatorer, frekvenstilldelning i trådlösa nätverk, och sudoku-pussel. Många verkliga problem kan modelleras som graffärgningsproblem.

Tillämpning: Tentamensschemaläggning

Problem: Schemalägg tentamina så inga studenter har konflikt

Modellering:

· Noder = tentamina

· Kanter = studenter som läser båda kurserna

· Färger = tidsluckor

Mål: Minimera antal tidsluckor (kromatiskt tal)

Utvidgningar:

· Olika längd på tentamina

· Förbokade rum och tider

· Lärarers tillgänglighet

· Balanserad fördelning över dagar

Registrallokering i kompilatorer

Problem: Tilldela programvariabler till hårdvaruregister

Interferensgraf:

· Noder = variabler

· Kanter = variabler som är 'levande' samtidigt

· Färger = hårdvaruregister

Optimering:

· Minimera antalet register (kromatiskt tal)

· Spill-kod när register tar slut

· Coalescing för att minska kopieringar

Vanliga misstag

❌ Förväxla kromatiskt tal med maximum clique

χ(G) ≥ ω(G) alltid, men likhet gäller endast för perfekta grafer

Exempel: Udda cykel C₅: χ(C₅) = 3 men ω(C₅) = 2

❌ Tro att girig algoritm alltid ger optimal färgning

Girig algoritm beror på nodordning och kan ge suboptimal färgning

Exempel: Dålig ordning kan ge Δ(G)+1 färger istället för χ(G)

❌ Glömma att kontrollera listfärgning-restriktioner

Listfärgning kan vara mycket svårare än vanlig färgning

Exempel: Bipartit graf kan ha stort listfärgningstal

Tillämpningar

Schemaläggning

Tentamensscheman, tågscheman och resursallokering

Exempel: Universitets tentamensschema där studenter inte kan ha överlappande tentamina

Trådlösa nätverk

Frekvenstilldelning för att undvika interferens

Exempel: Mobilmaster, WiFi-kanaler och Bluetooth-frekvenser

Kompilatoroptimering

Registrallokering och kodoptimering

Exempel: Tilldela programvariabler till CPU-register optimalt

Övningar

1 Lätt

Bestäm det kromatiska talet för cykelgrafen C₇.

Tips

Cykler av udda längd kräver 3 färger

Visa facit

Svar: χ(C₇) = 3

Förklaring: Udda cykel kan inte 2-färgas (skulle kräva att grannar har samma färg). 3 färger räcker: färga alternerande och använd tredje färg för en nod.

2 Medel

Bevisa att χ(G) ≥ ω(G) för alla grafer G.

Tips

Kliq-noder måste alla ha olika färger

Visa facit

Svar: En kliq av storlek ω(G) kräver ω(G) olika färger

Förklaring: I en kliq är alla noder intilliggande, så de måste ha olika färger i vilken färgning som helst.

3 Medel

Visa att den giriga algoritmen använder högst Δ(G)+1 färger.

Tips

Varje nod har högst Δ(G) grannar

Visa facit

Svar: Varje nod blockerar högst Δ(G) färger från sina grannar

Förklaring: När vi färgar nod v har den högst Δ(G) färgade grannar som blockerar högst Δ(G) färger. Färg Δ(G)+1 är alltid tillgänglig.

Sammanfattning

Graffärgning tilldela färger till noder så att intilliggande noder har olika färger. Det kromatiska talet är minsta antalet färger som behövs. Giriga algoritmer ger approximationer. Fyrfärgssatsen säger att planära grafer är 4-färgbara. Perfekta grafer har kromatiskt tal = kliqstorlek. Listfärgning är en generalisering med individuella färglistor. Tillämpningar inkluderar schemaläggning, nätverksfrekvenser och kompilatoroptimering.