Kromatiskt tal

Från Wikipedia
Hoppa till navigering Hoppa till sök

Kromatiskt tal är ett begrepp inom grafteorin i matematiken. Det kromatiska talet för en graf G, betecknat , är det tal för en graf G som beskriver det minsta antalet färger som behövs för att färglägga grafen G. Vad som menas med att färglägga en graf kan tyckas oklart. I detta fallet kan man tänka sig ett antal hörn eller punkter som, på olika sätt, kombineras ihop med andra hörn. Detta görs genom att man drar linjer från ett hörn till ett annat. Principen går sedan ut på att om två hörn är i kontakt med varandra via en linje, får de inte ha samma färg. Med andra ord, så det är alltså hörnen som man färgar och mellan hörnen dras linjer. Dessutom tillåts inte loopar, vilket betyder att en linje inte får återknytas till där den från början kom ifrån. Då detta är omöjligt att tänka sig vilka färger hörnen i så fall skulle ha.

Klassiska grafer[redigera | redigera wikitext]

K-graf C-graf S-graf W-graf
Complete graph K6.svg Undirected 6 cycle.svg Star network 7.svg Grafo k4 plano.PNG

Där är beteckningen för en så kallad komplett graf (K-graf), en graf där alla hörn är i kontakt med alla de andra hörnen, vilket också alltid gör att en komplett grafs antal hörn är samma som det kromatiska talet.

Bild nummer två är (C-graf), vilket står för cyklisk graf. Dessa är enkelt förklarade som cirklar, med andra ord ett hörn är i kontakt med nästa och det hörnet är i sin tur i kontakt med ytterligare en och så vidare till man når det första hörnet igen.

En stjärngraf (S-graf) betecknas med och är består av ett hörn i mitten och omges av ett antal hörn, alla dessa hörn är i kontakt med mittenhörnet men inte med varandra.

står för wheel, alltså en hjulgraf (W-graf), som kan sägas vara en kombination av stjärn- och cirkelgraf. Det finns ett hörn i mitten som är i kontakt med alla andra hörn som omger den. De hörn som omger mitten sitter alla ihop som i en cirkel, som kan ses i bilden. [1]

Bakgrund[redigera | redigera wikitext]

Det verkar först inte vara något större problem att färglägga dessa hörn med minimum antal färger, men att bestämma det kromatiska talet för en graf har faktiskt en NP (nondeterministic polynomial time [2])-svårighetsgrad. Det är därför vanligt att matematiker inte förväntar sig hitta algoritmer som kan lösa problemet. [3]

Att det kromatiska talet är ett NP-problem betyder i princip, i det här fallet, att det inte finns något smidigt sätt att bestämma det kromatiska talet för en graf G.[4] Och detta var just ett av Richard Karps 21 NP-problem, som han presenterade 1972. [5]

Trots det har flera personer under lång tid kommit på exakta algoritmer för det kromatiska talet för en graf, men endast för speciella fall. Alla algoritmer som tagits fram genom åren har också det problemet att det kan ta fram ett tal som är tillräckligt många färger för att färga en graf, men att bevisa att det inte finns ett mindre tal tar betydligt längre tid. Det finns till exempel problem med 85 hörn som kan ta sekunder att lösa, men minuter om inte timmar för att bevisa att just det kromatiska talet är det minsta. [6]

Olika lösningar på samma problem[redigera | redigera wikitext]

4 hörn med 3 färger på 12 olika sätt

Till exempel på bilden till höger kan man se 12 olika sätt att med det kromatiska talet 3 rita en figur som består av 4 hörn. I detta fall varieras färgerna röd, grön och blå i de olika hörn utan att bryta mot förutsättningarna och samtidigt är det inte fler än 3 färger. Det kromatiska talet är alltså 3, men det finns 12 olika lösningar som alla är korrekta.

Formler[redigera | redigera wikitext]

Där n är antalet hörn:

Graf förutsättning förutsättning
K-graf n
C-graf, n>1 2 för jämna n 3 för udda n
S-graf 2
W-graf, n>2 3 för udda n 4 för jämna n

så här kan vi se att vissa finns exempel på grafer vars lösningar lätt kan beskrivas och vi ser även att det kan spela roll ifall n är udda eller jämnt.[1]

Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg Complete graph K4.svg Complete graph K5.svg

Här kan man se de fem första -graferna (n=1,2,3,4,5). [7]

Alla kromatiska tal är minst 1 och max n, där n är antalet hörn. Det ter sig förmodligen rätt naturligt, att när man får reda på att de grafer som bara har 1 färg är grafer helt utan linjer, alltså ett enda hörn. Grafer där varje hörn är av unik färg är -graferna.

Om m är antal linjer mellan punkter så kan man se att 2 gånger alla linjer alltid är större eller lika med det kromatiska talet gånger det kromatiska talet minus 1. Är man osäker på om detta stämmer kan man testa på Petersens graf som kan ses på bilden till höger.

Petersens graf

sen är det också fastställt att det kromatiska talet är åtminstone klicktalet.

Höga klicktal ger alltså höga kromatiska tal, men motsatsen är inte nödvändigtvis sann. Det finns exempelvis grafer med höga kromatiska tal och med små klicktal.

Vidare är det alltid givet, att om man har och göra med planära grafer så kommer det kromatiska talet, för en sådan graf, alltid att vara högst 4.[8] Det följer av fyrfärgssatsen.

Tillämpningar[redigera | redigera wikitext]

Ett sätt att använda sig av kromatiskt tal i ett verkligt syfte är när man gör kartor [7]. Dessa kartor är färgade på så sätt att alla länder har olika färger, för att man ska tydligt se skillnaderna på länderna och lätt urskilja deras gränser. Att använda sig av så få färger som möjligt (alltså det kromatiska talet) när man ritar kartan är naturligtvis bra. Flera länder har flera länder som de delar gräns med. Då kan man tänka sig själv att det är viktigt att få rätt kromatiskt tal och placera talen rätt. Se fyrfärgssatsen och femfärgssatsen.

Dessutom har sudoku med färgning av grafer att göra. Det kan man ju se på att ingen siffra får befinna sig i samma kvadrat, i samma kolumn eller i samma rad som en likadan siffra.

Trivia[redigera | redigera wikitext]

Ibland skrivs också för , vilket också är benämningen för Eulerkarakteristik [1]

Koppling till kromatiskt polynom[redigera | redigera wikitext]

Det kromatiska talet för en graf med kromatiskt polynom är det minsta positiva heltal som inte är en rot till .

Referenser[redigera | redigera wikitext]

  1. ^ [a b c] Wolfram, Mathworld Wolfram.
  2. ^ eHow, Stephanie Ellen.
  3. ^ DETERMINING THE CHROMATIC NUMBER OF A GRAPH, COLIN McDIARMID
  4. ^ Harary F. Graph Theory. Reading, MA: Addison-Wesley, 1994.
  5. ^ Richard M. Karp (1972). "Reducibility Among Combinatorial Problems". In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103.
  6. ^ Francine HERRMANN, LITA, Université de Metz, Ile de Saulcy, 57045 Metz Cedex France Alain HERTZ, Département de Mathématiques et de Génie Industriel, Ecole Polytechnique, CP 6079, succ. Centre-ville, Montréal (QC) H3C 3A7, Canada.
  7. ^ [a b] Graph Theory Glossary, Chris Caldwell.
  8. ^ Lindström, Bernt; Janson, Svante: Grafteori i Nationalencyklopedins nätupplaga. Läst 8 juli 2015.