Graffärgning
Färglägg en graf med så få färger som möjligt
Om den här räknaren
Graffärgningsräknaren tar fram det kromatiska talet χ(G) – det minsta antal färger som behövs för att färga en grafs hörn så att ingen kant förbinder två hörn med samma färg – och visar en optimal färgning. Ange antalet hörn och en lista med kanter; den beräknar χ exakt med en branch and bound-sökning, anger maxgraden Δ och den största klicken ω (en undre gräns för χ), markerar bipartita och kompletta grafer och ritar den färgade grafen. Användbar för schemaläggning, registerallokering, kartfärgning och studier av kromatiska tal.
Så färgar du en graf
- Ange antalet hörn; de numreras 1 till n.
- Lista kanterna som par, till exempel 1-2, 2-3 – ett par per förbindelse.
- Läs av det kromatiska talet χ(G) och färgen som tilldelats varje hörn.
- Jämför χ med den största klicken ω för att se varför så många färger behövs, eller ladda ett exempel och utforska.
Vanliga exempel
- En triangel (K₃) behöver 3 färger – alla par av dess hörn är grannar.
- Jämna cykler är bipartita och behöver bara 2 färger; udda cykler som C₅ behöver 3.
- Den kompletta grafen Kₙ behöver exakt n färger.
- En största klick av storlek ω kräver minst ω färger, så χ(G) ≥ ω.
- Grötzschgrafen behöver 4 färger men innehåller ingen triangel, så χ kan vara större än klicktalet.
Vanliga frågor
Vad är det kromatiska talet?
Det kromatiska talet χ(G) är det minsta antal färger som behövs för att färga en grafs hörn så att ingen kant förbinder två hörn med samma färg.
Hur hittas det minsta antalet färger?
Eftersom grafen är liten söker räknaren exakt: den provar 1 färg, sedan 2 och så vidare, och returnerar det första antal för vilket en korrekt färgning finns. Det antalet är garanterat det verkliga minimum.
Vad är maxgrad och största klick?
Maxgraden Δ är det största antalet kanter som möts i ett enskilt hörn. Den största klicken ω är den största mängden hörn som alla är grannar med varandra; eftersom de alla måste ha olika färger är χ(G) minst ω.
Varför kan en graf utan trianglar ändå behöva många färger?
En stor klick kräver många färger, men det är inte det enda skälet. Udda cykler och grafer som Grötzschgrafen behöver extra färger även utan någon triangel, så χ(G) kan vara större än klicktalet.
Finns det en gräns för grafens storlek?
Ja. Exakt graffärgning är beräkningsmässigt svårt, så räknaren begränsar grafen till 12 hörn för att resultaten ska komma direkt och vara stringenta.