Graffärgning - Graph coloring

En korrekt toppunktsfärgning av Petersen -grafen med 3 färger, minsta möjliga antal.

I grafteori , graf färg är ett specialfall av grafen märkning ; det är en tilldelning av etiketter som traditionellt kallas "färger" till element i en graf som har vissa begränsningar. I sin enklaste form är det ett sätt att färga hörnen på en graf så att inga två intilliggande hörn är av samma färg; detta kallas en vertexfärgning . På samma sätt tilldelar en kantfärgning en färg till varje kant så att inga angränsande kanter har samma färg, och en ansiktsfärgning av en plan graf tilldelar en färg till varje sida eller region så att inga två ytor som delar en gräns har samma färg.

Vertexfärgning används vanligtvis för att införa graffärgproblem, eftersom andra färgproblem kan omvandlas till en vertex -färginstans. Till exempel är en kantfärgning av en graf bara en toppunktsfärgning av dess linjediagram , och en ansiktsfärgning av en plan graf är bara en vertexfärgning av dess dubbla . Emellertid anges icke-vertex-färgproblem ofta och studeras som det är. Detta är dels pedagogiskt , dels för att vissa problem bäst studeras i sin icke-vertexform, som vid kantfärgning.

Konventionen att använda färger härstammar från att färga länderna på en karta , där varje ansikte är bokstavligen färgat. Detta generaliserades för att färga ansiktena på en graf inbäddad i planet. Genom plan dualitet blev det färgning av hörnen, och i denna form generaliseras det till alla grafer. I matematiska och datoriska representationer är det typiskt att använda de första positiva eller icke-negativa heltalen som "färger". I allmänhet kan man använda vilken ändlig uppsättning som "färguppsättning". Färgproblemets beskaffenhet beror på antalet färger men inte på vad de är.

Graffärgning har många praktiska tillämpningar såväl som teoretiska utmaningar. Förutom de klassiska typerna av problem kan olika begränsningar också ställas in på grafen, eller på sättet en färg tilldelas, eller till och med själva färgen. Det har till och med nått popularitet hos allmänheten i form av det populära nummerpusslet Sudoku . Graffärgning är fortfarande ett mycket aktivt forskningsområde.

Obs! Många termer som används i denna artikel definieras i Ordlista för grafteori .

Historia

De första resultaten om graffärgning handlar nästan uteslutande om plana grafer i form av färgning av kartor . När han försökte färga en karta över Englands län, postulerade Francis Guthrie de fyra färgstötarna och noterade att fyra färger var tillräckligt för att färga kartan så att inga regioner som delar en gemensam gräns fick samma färg. Guthries bror vidarebefordrade frågan till sin matematiklärare Augustus de Morgan vid University College , som nämnde det i ett brev till William Hamilton 1852. Arthur Cayley tog upp problemet vid ett möte i London Mathematical Society 1879. Samma år Alfred Kempe publicerade ett papper som påstod att fastställa resultatet, och i ett decennium ansågs fyrafärgsproblemet vara löst. För sin prestation valdes Kempe till stipendiat i Royal Society och senare till ordförande för London Mathematical Society.

År 1890 påpekade Heawood att Kempes argument var fel. Men i det papperet bevisade han femfärgsteoremet och sa att varje plan karta kan färgas med högst fem färger, med idéer från Kempe. Under det följande århundradet utvecklades en stor mängd arbete och teorier för att minska antalet färger till fyra tills de fyra färgsatsen slutligen bevisades 1976 av Kenneth Appel och Wolfgang Haken . Beviset gick tillbaka till Heawood och Kempes idéer och ignorerade till stor del den mellanliggande utvecklingen. Beviset på fyrfärgsatsen är också anmärkningsvärt för att vara det första stora datorstödda beviset.

År 1912 introducerade George David Birkhoff det kromatiska polynomet för att studera färgproblemen, som generaliserades till Tutte -polynomet av Tutte , viktiga strukturer i algebraisk grafteori . Kempe hade redan uppmärksammat det allmänna, icke-plana fallet 1879, och många resultat om generaliseringar av plan graffärgning till ytor av högre ordning följde i början av 1900-talet.

År 1960 formulerade Claude Berge en annan gissning om graffärgning, den starka perfekta grafdiformuleringen , ursprungligen motiverad av ett informationsteoretiskt koncept som kallas nollfelkapaciteten för en graf som introducerades av Shannon . Gissningen förblev olöst i 40 år tills den fastställdes som den berömda starka perfekta grafsatsen av Chudnovsky , Robertson , Seymour och Thomas 2002.

Graffärgning har studerats som ett algoritmiskt problem sedan början av 1970-talet: det kromatiska talproblemet (se nedan ) är ett av Karps 21 NP-kompletta problem från 1972, och ungefär samtidigt utvecklades olika exponentiell tidsalgoritmer baserade på backtracking och om radering-kontraktion återfall av Zykov (1949) . En av de viktigaste tillämpningarna av graffärgning, registerallokering i kompilatorer, introducerades 1981.

Definition och terminologi

Denna graf kan vara trefärgad på 12 olika sätt.

Vertex färgning

När den används utan någon kvalifikation är en färgning av en graf nästan alltid en korrekt toppunktsfärgning , nämligen en märkning av grafens hörn med färger så att inga två hörn som delar samma kant har samma färg. Eftersom en toppunkt med en slinga (dvs. en anslutning direkt tillbaka till sig själv) aldrig kunde färgas ordentligt, är det underförstått att grafer i detta sammanhang är looplösa.

Terminologin för att använda färger för hörnetiketter går tillbaka till kartfärgning. Etiketter som rött och blått används bara när antalet färger är litet och normalt är det underförstått att etiketterna dras från heltalen {1, 2, 3, ...}.

En färgning som använder högst k färger kallas en (korrekt) k -färgning . Det minsta antal färger som behövs för att färga en graf G kallas dess kromatiska tal och betecknas ofta χ ( G ). Ibland används γ ( G ), eftersom χ ( G ) också används för att beteckna Eulers egenskaper hos en graf. En graf som kan tilldelas en (korrekt) k -färgning är k -färgbar , och den är k -kromatisk om dess kromatiska nummer är exakt k . En delmängd av hörn som tilldelas samma färg kallas en färgklass , varje sådan klass bildar en oberoende uppsättning . Således är en k- färgning detsamma som en uppdelning av hörnuppsättningen i k oberoende uppsättningar, och termerna k-partit och k-färgbar har samma innebörd.

Kromatiskt polynom

Alla icke-isomorfa grafer på tre hörn och deras kromatiska polynom. Den tomma grafen E ₃ (röd) medger en 1-färgning; de andra erkänner

Det kromatiska polynomet räknar antalet sätt en graf kan färgläggas med några av ett visst antal färger. Om du till exempel använder tre färger kan grafen i den intilliggande bilden färgas på 12 sätt. Med bara två färger kan den inte färgas alls. Med fyra färger kan den färgas på 24 + 4⋅12 = 72 sätt: med alla fyra färgerna finns det 4! = 24 giltiga färgämnen ( varje tilldelning av fyra färger till alla 4-toppunktsdiagram är en korrekt färgning); och för varje val av tre av de fyra färgerna finns det 12 giltiga 3-färgningar. Så för grafen i exemplet skulle en tabell med antalet giltiga färgningar börja så här:

Det kromatiska polynomet är en funktion som räknar antalet t -färger av . Som namnet indikerar, för en given funktion är verkligen ett polynom i . För exempelgrafen , och faktiskt . ${\ displaystyle P (G, t)}$${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle t}$${\ displaystyle P (G, t) = t (t-1)^{2} (t-2)}$${\ displaystyle P (G, 4) = 72}$

Det kromatiska polynomet innehåller mer information om färgbarheten hos G än det kromatiska talet. Faktum är att χ är det minsta positiva heltalet som inte är en nolla av det kromatiska polynomet:

${\ displaystyle \ chi (G) = \ min \ {k \, \ colon \, P (G, k)> 0 \}.}$

Kromatiska polynom för vissa grafer

Triangel K 3	${\ displaystyle t (t-1) (t-2)}$
Komplett graf K n	${\ displaystyle t (t-1) (t-2) \ cdots (t- (n-1))}$
Träd med n hörn	${\ displaystyle t (t-1)^{n-1}}$
Cykel C n	${\ displaystyle (t-1)^{n}+(-1)^{n} (t-1)}$
Petersen graf	${\ displaystyle t (t-1) (t-2) (t^{7} -12t^{6}+67t^{5} -230t^{4}+529t^{3} -814t^{2} +775t-352)}$

Kantfärgning

En kantfärgning av en graf är en korrekt färgning av kanterna , vilket innebär att färgerna tilldelas kanterna så att ingen hörn träffas av två kanter av samma färg. En kantfärgning med k -färger kallas en k -kantfärgning och motsvarar problemet med att dela upp kanten i k -matchningar . Det minsta antalet färger som behövs för en kant färgning av en graf G är den kromatiska index , eller kant kromatisk antal , χ '( G ). En Tait-färgning är en trekantig färgning av ett kubikgraf . Satsen med fyra färger motsvarar påståendet att varje plan kubisk brygglös graf medger en Tait -färgning.

Total färgning

Total färgning är en typ av färgning på hörn och kanter på en graf. När den används utan någon kvalifikation antas alltid en total färgning vara korrekt i den meningen att inga intilliggande hörn, inga angränsande kanter och ingen kant och dess ändhörn är tilldelade samma färg. Det totala kromatiska talet χ ″ ( G ) i en graf G är de färsta färgerna som behövs i en total färgning av G.

Omärkt färgning

En omärkt färgning av ett diagram är en omloppsbana av ett färgämne under verkan av den automorfism grupp av grafen. Observera att färgerna förblir märkta; det är grafen som är omärkt. Det finns en analog av det kromatiska polynomet som räknar antalet omärkta färgämnen för en graf från en given ändlig färguppsättning.

Om vi ​​tolkar en färgning av en graf på hörn som en vektor i , är verkan av en automorfism en permutation av koefficienterna i färgvektorn. ${\ displaystyle d}$${\ displaystyle \ mathbb {Z} ^{d}}$

Egenskaper

Övre gränser för det kromatiska talet

Att tilldela distinkta färger till distinkta hörn ger alltid en korrekt färgning, så

${\ displaystyle 1 \ leq \ chi (G) \ leq n.}$

De enda graferna som kan vara 1-färgade är kantlösa grafer . Ett komplett diagram med n hörn kräver färger. Vid en optimal färgning måste det finnas minst en av grafens m -kanter mellan varje par färgklasser, så ${\ displaystyle K_ {n}}$${\ displaystyle \ chi (K_ {n}) = n}$

${\ displaystyle \ chi (G) (\ chi (G) -1) \ leq 2m.}$

Om G innehåller en klick av storlek k , krävs åtminstone k färger för att färga den klicken; med andra ord, det kromatiska talet är åtminstone klickantalet:

${\ displaystyle \ chi (G) \ geq \ omega (G).}$

För perfekta grafer är denna gräns tätt. Att hitta klickar är känt som klickproblemet .

Mer generellt är en familj av grafer -gränsade om det finns någon funktion så att graferna i kan färgas med de flesta färger, för familjen av de perfekta graferna är denna funktion . ${\ displaystyle {\ mathcal {F}}}$${\ displaystyle \ chi}$${\ displaystyle c}$${\ displaystyle G}$${\ displaystyle {\ mathcal {F}}}$${\ displaystyle c (\ omega (G))}$${\ displaystyle c (\ omega (G)) = \ omega (G)}$

De tvåfärgbara graferna är exakt de tvåpartiga graferna , inklusive träd och skogar. Med de fyra färgteorem kan varje plan graf vara 4-färgad.

En giriga färg visar att varje kurva kan färgas med ett mer färg än den maximala vertex grad ,

${\ displaystyle \ chi (G) \ leq \ Delta (G) +1.}$

Kompletta grafer har och , och udda cykler har och så för dessa grafer är denna gräns bäst möjlig. I alla andra fall kan gränsen förbättras något; Brooks sats säger att ${\ displaystyle \ chi (G) = n}$${\ displaystyle \ Delta (G) = n-1}$${\ displaystyle \ chi (G) = 3}$${\ displaystyle \ Delta (G) = 2}$

Brooks sats : för en ansluten, enkel graf G , om inte G är en fullständig graf eller en udda cykel.${\ displaystyle \ chi (G) \ leq \ Delta (G)}$

Lägre gränser för det kromatiska talet

Flera lägre gränser för de kromatiska gränserna har upptäckts genom åren:

Hoffmans gräns: Låt vara en riktig symmetrisk matris så att när som helst inte är en kant in . Definiera , var är de största och minsta egenvärdena för . Definiera , med som ovan. Sedan: ${\ displaystyle W}$${\ displaystyle W_ {i, j} = 0}$${\ displaystyle (i, j)}$${\ displaystyle G}$${\ displaystyle \ chi _ {W} (G) = 1-{\ tfrac {\ lambda _ {\ max} (W)} {\ lambda _ {\ min} (W)}}}}$${\ displaystyle \ lambda _ {\ max} (W), \ lambda _ {\ min} (W)}$${\ displaystyle W}$${\ textstil \ chi _ {H} (G) = \ max _ {W} \ chi _ {W} (G)}$${\ displaystyle W}$

${\ displaystyle \ chi _ {H} (G) \ leq \ chi (G).}$

Vektorkromatiskt tal :Låtvara en positiv halvdefinierad matris så attnärsomhelstär en kant in. Definieraatt vara det minsta k för vilket en sådan matrisfinns. Sedan ${\ displaystyle W}$${\ displaystyle W_ {i, j} \ leq -{\ tfrac {1} {k -1}}}$${\ displaystyle (i, j)}$${\ displaystyle G}$${\ displaystyle \ chi _ {V} (G)}$${\ displaystyle W}$

${\ displaystyle \ chi _ {V} (G) \ leq \ chi (G).}$

Lovász -nummer : Lovász -talet för ett kompletterande diagram är också en nedre gräns för det kromatiska talet:

${\ displaystyle \ vartheta ({\ bar {G}}) \ leq \ chi (G).}$

Fraktionellt kromatiskt tal : Det grafiska kromatiska talet i en graf är också en nedre gräns för det kromatiska talet:

${\ displaystyle \ chi _ {f} (G) \ leq \ chi (G).}$

Dessa gränser ordnas enligt följande:

${\ displaystyle \ chi _ {H} (G) \ leq \ chi _ {V} (G) \ leq \ vartheta ({\ bar {G}}) \ leq \ chi _ {f} (G) \ leq \ chi (G).}$

Grafer med högt kromatiskt tal

Grafer med stora klickar har ett högt kromatiskt tal, men motsatsen är inte sant. Den Grötzsch diagrammet är ett exempel på en 4-kromatisk graf utan en triangel, och exemplet kan generaliseras till de Mycielskians .

Satsning ( William T. Tutte  1947 , Alexander Zykov  1949 , Jan Mycielski  1955 ): Det finns triangelfria grafer med godtyckligt högt kromatiskt tal.

För att bevisa detta gav båda Mycielski och Zykov en konstruktion av en induktivt definierad familj av triangelfria grafer men med godtyckligt stort kromatiskt tal. Burling (1965) konstruerade axelinriktade rutor i vars skärningskurva är triangelfritt och kräver godtyckligt många färger för att vara korrekt färgade. Denna familj av grafer kallas då Burling -graferna. Samma klass av grafer används för konstruktion av en familj av triangelfria linjesegment i planet, givet av Pawlik et. al. (2014). Det visar att det kromatiska antalet i dess skärningskurva är godtyckligt stort också. Därför innebär detta att axelinriktade rutor i såväl som linjesegment i inte är χ-begränsade . ${\ displaystyle \ mathbb {R} ^{3}}$${\ displaystyle \ mathbb {R} ^{3}}$${\ displaystyle \ mathbb {R} ^{2}}$

Från Brooks sats måste grafer med högt kromatiskt tal ha hög maximal grad. Men färgbarhet är inte ett helt lokalt fenomen: En graf med hög omkrets ser lokalt ut som ett träd, eftersom alla cykler är långa, men dess kromatiska antal behöver inte vara 2:

Sats ( Erdős ): Det finns grafer över godtyckligt hög omkrets och kromatiskt tal.

Gränser för det kromatiska indexet

En kantfärgning av G är en toppunktsfärgning av dess linjediagram , och vice versa. Således, ${\ displaystyle L (G)}$

${\ displaystyle \ chi '(G) = \ chi (L (G)).}$

Det finns ett starkt förhållande mellan kantfärgbarhet och grafens maximala grad . Eftersom alla kanter som infaller i samma hörn behöver sin egen färg har vi ${\ displaystyle \ Delta (G)}$

${\ displaystyle \ chi '(G) \ geq \ Delta (G).}$

Dessutom,

Kőnigs sats : om G är tvåpartig.${\ displaystyle \ chi '(G) = \ Delta (G)}$

I allmänhet är förhållandet ännu starkare än vad Brooks sats ger för vertexfärgning:

Vizing's sats: En graf med maximal gradhar kant-kromatiskt taleller.${\ displaystyle \ Delta}$${\ displaystyle \ Delta}$${\ displaystyle \ Delta +1}$

Övriga fastigheter

En graf har en k -färgning om och bara om den har en acyklisk orientering för vilken den längsta vägen har längd som högst k ; detta är satsen Gallai – Hasse – Roy – Vitaver ( Nešetřil & Ossona de Mendez 2012 ).

För plana grafer är toppunktsfärgningar i huvudsak dubbla till ingenstans-nollflöden .

Om oändliga grafer är mycket mindre känt. Följande är två av de få resultaten om oändlig graffärgning:

• Om alla ändliga undergrafer för en oändlig graf G är k -färgbara, så är G också , under antagandet av valet axiom . Detta är de Bruijn – Erdős sats om de Bruijn & Erdős (1951) .
• Om en graf medger en fullständig n -färgning för varje n ≥ n ₀ , medger den en oändlig fullfärgning ( Fawcett 1978 ).

Öppna problem

Som nämnts ovan är en gissning om Reed från 1998 att värdet är väsentligen närmare den nedre gränsen, ${\ displaystyle \ omega (G) \ leq \ chi (G) \ leq \ Delta (G) +1.}$${\ displaystyle \ chi (G) \ leq \ left \ lceil {\ frac {\ omega (G)+\ Delta (G) +1} {2}} \ right \ rceil.}$

Den kromatiska antalet planet , där två punkter är närliggande om de har enhetsavstånd, är okänd, även om det är en av 5, 6 eller 7. Andra öppna problem som rör den kromatiska antal grafer inkluderar Hadwiger gissningar som anger att varje graf med kromatisk siffra k har ett komplett diagram på k -hörnen som minor , gissningarna Erdős -Faber – Lovász begränsar det kromatiska antalet fackföreningar av kompletta grafer som har högst en toppunkt gemensamt för varje par och Albertson -gissningen som bland k -kromatiska grafer de kompletta graferna är de med minsta kryssningsnummer .

När Birkhoff och Lewis introducerade det kromatiska polynomet i sitt angrepp mot fyrfärgsatsen, gissade de att för plana grafer G har polynomet inga nollor i regionen . Även om det är känt att ett sådant kromatiskt polynom inte har nollor i regionen och att deras gissningar fortfarande är olösta. Det förblir också ett olöst problem att karakterisera diagram som har samma kromatiska polynom och bestämma vilka polynom som är kromatiska. ${\ displaystyle P (G, t)}$${\ displaystyle [4, \ infty)}$${\ displaystyle [5, \ infty)}$${\ displaystyle P (G, 4) \ neq 0}$

Algoritmer

Graffärgning
Beslut
namn	Graffärgning, toppunktsfärgning, k -färgning
Inmatning	Diagram G med n hörn. Heltal k
Produktion	Medger G en korrekt vertexfärgning med k -färger?
Speltid	O (2 n n )
Komplexitet	NP-komplett
Minskning från	3-tillfredsställelse
Garey – Johnson	GT4
Optimering
namn	Kromatiskt tal
Inmatning	Diagram G med n hörn.
Produktion	χ ( G )
Komplexitet	NP-hårt
Tillgänglighet	O ( n  (log n ) −3 (log log n ) 2 )
Otillräcklighet	O ( n 1 − ε ) om inte P = NP
Räknar problem
namn	Kromatiskt polynom
Inmatning	Diagram G med n hörn. Heltal k
Produktion	Talet P  ( G , k ) för korrekta k -färgningar av G
Speltid	O (2 n n )
Komplexitet	#P-komplett
Tillgänglighet	FPRAS för begränsade fall
Otillräcklighet	Ingen PTAS om inte P = NP

Polynomtid

Att avgöra om en graf kan färgas med 2 färger motsvarar att avgöra om grafen är bipartit eller inte , och därmed beräknad i linjär tid med bredde-första sökning eller djup-första sökning . Mer allmänt kan det kromatiska talet och en motsvarande färgning av perfekta grafer beräknas på polynomtid med hjälp av semidefinit programmering . Stängda formler för kromatiskt polynom är kända för många klasser av grafer, såsom skogar, ackordgrafer, cykler, hjul och stegar, så dessa kan utvärderas i polynomtid.

Om grafen är plan och har låg grenbredd (eller är icke-plan men med en känd grennedbrytning), kan den lösas på polynomtid med dynamisk programmering. I allmänhet är den tid som krävs polynom i grafstorleken, men exponentiell i grenbredden.

Exakta algoritmer

Brute -force -sökning efter en k -färgning överväger var och en av tilldelningarna av k -färger till n hörn och kontrollerar för varje om det är lagligt. För att beräkna det kromatiska talet och det kromatiska polynomet används denna procedur för varje , opraktiskt för alla utom de minsta inmatningsgraferna. ${\ displaystyle k^{n}}$${\ displaystyle k = 1, \ ldots, n-1}$

Genom att använda dynamisk programmering och en gräns för antalet maximala oberoende uppsättningar kan k -färgbarhet bestämmas i tid och rum . Med hjälp av principen om inkludering -uteslutning och Yates algoritm för den snabba zetatransformen kan k -färgbarhet bestämmas i tid för alla k . Snabbare algoritmer är kända för 3- och 4-colorability, som kan bestämmas i tid och , respektive. ${\ displaystyle O (2.4423^{n})}$${\ displaystyle O (2^{n} n)}$${\ displaystyle O (1.3289^{n})}$${\ displaystyle O (1.7272^{n})}$

Kontraktion

Den sammandragning av en graf G är grafen som erhålls genom att identifiera hörnen u och v , och avlägsna eventuella kanter mellan dem. De återstående kanterna som ursprungligen drabbades av u eller v är nu infall till deras identifiering. Denna operation spelar en stor roll i analysen av graffärgning. ${\ displaystyle G/uv}$

Det kromatiska talet uppfyller återkommande förhållande :

${\ displaystyle \ chi (G) = {\ text {min}} \ {\ chi (G+uv), \ chi (G/uv) \}}$

på grund av Zykov (1949) , där u och v är icke-intilliggande hörn, och är grafen med kanten uv tillagd. Flera algoritmer bygger på att utvärdera denna återkommande och det resulterande beräkningsträdet kallas ibland ett Zykov -träd. Speltiden är baserad på en heurist för val av hörnen u och v . ${\ displaystyle G+uv}$

Det kromatiska polynomet uppfyller följande återkommande förhållande

${\ displaystyle P (G-uv, k) = P (G/uv, k)+P (G, k)}$

där u och v är intilliggande hörn, och är grafen med kanten uv borttagen. representerar antalet möjliga korrekta färgningar av grafen, där hörnen kan ha samma eller olika färger. Då uppstår rätt färgning från två olika grafer. För att förklara, om hörnen u och v har olika färger, kan vi lika gärna överväga en graf där u och v ligger intill. Om u och v har samma färger kan vi lika gärna överväga en graf där u och v är sammandragna. Tuttes nyfikenhet på vilka andra grafegenskaper som tillfredsställde detta återkommande fick honom att upptäcka en bivariat generalisering av det kromatiska polynomet, Tutte -polynomet . ${\ displaystyle G-uv}$${\ displaystyle P (G-uv, k)}$

Dessa uttryck ger upphov till ett rekursivt förfarande som kallas deletion -contraction algoritm , som ligger till grund för många algoritmer för graffärgning. Drifttiden uppfyller samma återkommande relation som Fibonacci -siffrorna , så i värsta fall körs algoritmen i tid inom en polynomfaktor på för n hörn och m -kanter. Analysen kan förbättras till inom ett polynom faktor av antalet av spänner träd i ingångs grafen. I praktiken används gren- och bundna strategier och grafisomorfismavvisning för att undvika vissa rekursiva samtal. Speltiden beror på den heurist som används för att välja toppunktsparet. ${\ displaystyle \ left ({\ tfrac {1+{\ sqrt {5}}} {2}} \ right)^{n+m} = O (1.6180^{n+m})}$${\ displaystyle t (G)}$

Girig färgning

Två giriga färgningar av samma graf med olika toppunktsordningar. Rätt exempel generaliserar till tvåfärgbara grafer med n hörn, där den giriga algoritmen expanderar färger.${\ displaystyle n/2}$

Den giriga algoritmen betraktar hörnpunkterna i en specifik ordning ,…, och tilldelar den minsta tillgängliga färgen som inte används av grannarna bland ,…, och lägger till en ny färg om det behövs. Kvaliteten på den resulterande färgen beror på den valda beställningen. Det finns en ordning som leder till en girig färgning med det optimala antalet färger. Å andra sidan kan giriga färgningar vara godtyckligt dåliga; till exempel kan krondiagrammet på n hörn vara tvåfärgade, men har en ordning som leder till en girig färgning med färger. ${\ displaystyle v_ {1}}$${\ displaystyle v_ {n}}$${\ displaystyle v_ {i}}$${\ displaystyle v_ {i}}$${\ displaystyle v_ {1}}$${\ displaystyle v_ {i-1}}$${\ displaystyle \ chi (G)}$${\ displaystyle n/2}$

För ackordgrafer och för speciella fall av ackordgrafer såsom intervalldiagram och likgiltighetsgrafer kan den giriga färgalgoritmen användas för att hitta optimala färgningar i polynomtid genom att välja toppunktsordningen för att vara omvänd av en perfekt elimineringsordning för Graf. De perfekt beställbara graferna generaliserar den här egenskapen, men det är NP-svårt att hitta en perfekt ordning av dessa grafer.

Om hörnen ordnas efter deras grader använder den resulterande giriga färgen högst färger, högst en mer än grafens maximala grad. Denna heurist kallas ibland Welsh -Powell -algoritmen. En annan heuristik på grund av Brélaz fastställer ordningen dynamiskt medan algoritmen fortsätter och väljer nästa toppunkt intill det största antalet olika färger. Många andra graffärgningsheuristiker är på samma sätt baserade på giriga färger för en specifik statisk eller dynamisk strategi för att ordna hörnen, dessa algoritmer kallas ibland sekventiella färgalgoritmer . ${\ displaystyle {\ text {max}} _ {i} {\ text {min}} \ {d (x_ {i})+1, i \}}$

Det maximala (värsta) antalet färger som kan erhållas av den giriga algoritmen, genom att använda en toppunktsordning som valts för att maximera detta antal, kallas Grundy -talet i en graf.

Parallella och distribuerade algoritmer

Inom området distribuerade algoritmer är graffärgning nära besläktad med problemet med symmetribrytning . De nuvarande toppmoderna randomiserade algoritmerna är snabbare för tillräckligt stor maximal grad Δ än deterministiska algoritmer. De snabbaste randomiserade algoritmerna använder multitest-tekniken av Schneider et al.

I en symmetrisk graf kan en deterministisk distribuerad algoritm inte hitta en riktig vertexfärgning. En del hjälpinformation behövs för att bryta symmetrin. Ett standardantag är att varje nod initialt har en unik identifierare , till exempel från uppsättningen {1, 2, ..., n }. Med andra ord antar vi att vi får en n -färg. Utmaningen är att minska antalet färger från n till t.ex. Δ + 1. Ju fler färger som används, t.ex. O (Δ) istället för Δ + 1, desto färre kommunikationsrundor krävs.

En enkel distribuerad version av den giriga algoritmen för (Δ + 1) -färgning kräver Θ ( n ) kommunikationsrundor i värsta fall-information kan behöva spridas från ena sidan av nätverket till en annan sida.

Det enklaste intressanta fallet är en n - cykel . Richard Cole och Uzi Vishkin visar att det finns en distribuerad algoritm som minskar antalet färger från n till O (log  n ) i ett synkront kommunikationssteg. Genom att iterera samma procedur är det möjligt att få en 3 -färgning av en n -cykel i O ( log *  n ) kommunikationssteg (förutsatt att vi har unika nodidentifierare).

Funktionen log * , upprepade logaritm , är en extremt långsamt växande funktion, "nästan konstant". Därför väckte resultatet av Cole och Vishkin frågan om det finns en konstant tidsfördelad algoritm för 3-färgning av en n- cykel. Linial (1992) visade att detta inte är möjligt: ​​någon deterministisk distribuerad algoritm kräver Ω ( log *  n ) kommunikationssteg för att reducera en n -färgning till en 3 -färgning i en n -cykel.

Tekniken av Cole och Vishkin kan också tillämpas i godtyckliga grafer med begränsad grad; körtiden är poly (Δ) + O ( log *  n ). Tekniken utökades till enhetsdiskgrafer av Schneider et al. De snabbaste deterministiska algoritmerna för (Δ + 1) -färgning för små Δ beror på Leonid Barenboim, Michael Elkin och Fabian Kuhn. Algoritmen av Barenboim et al. körs i tiden O (Δ) +  log * ( n )/2, vilket är optimalt när det gäller n eftersom den konstanta faktorn 1/2 inte kan förbättras på grund av Linials nedre gräns. Panconesi & Srinivasan (1996) använder nätverksnedbrytningar för att beräkna en Δ+1 -färgning i tid . ${\ displaystyle 2^{O \ vänster ({\ sqrt {\ log n}} \ höger)}}$

Problemet med kantfärgning har också studerats i den distribuerade modellen. Panconesi & Rizzi (2001) uppnår en (2Δ-1) -färgning i O (Δ +  log *  n ) tid i denna modell. Den nedre gränsen för distribuerad vertexfärgning på grund av Linial (1992) gäller också problemet med fördelad kantfärgning.

Decentraliserade algoritmer

Decentraliserade algoritmer är sådana där ingen meddelandeöverföring är tillåten (i motsats till distribuerade algoritmer där lokal meddelandeöverföring sker), och det finns effektiva decentraliserade algoritmer som färgar en graf om en korrekt färgning finns. Dessa antar att en vertex kan känna av om någon av dess grannar använder samma färg som vertexen, dvs om det finns en lokal konflikt. Detta är ett milt antagande i många applikationer, t.ex. vid tilldelning av trådlösa kanaler är det vanligtvis rimligt att anta att en station kommer att kunna upptäcka om andra störande sändare använder samma kanal (t.ex. genom att mäta SINR). Denna avkänningsinformation är tillräcklig för att låta algoritmer baserade på inlärningsautomater hitta en korrekt graffärgning med sannolikhet.

Beräkningskomplexitet

Graffärgning är beräkningsmässigt svårt. Det är NP -komplett att avgöra om en given graf tillåter en k -färgning för en given k med undantag för fallen k ∈ {0,1,2}. I synnerhet är det NP-svårt att beräkna det kromatiska talet. Problemet med tre färger förblir NP-komplett även på 4-regelbundna plana grafer . För varje k > 3 existerar emellertid en k -färgning av ett plant diagram med de fyra färgsatsen , och det är möjligt att hitta en sådan färgning i polynomtid.

Den mest kända approximationsalgoritmen beräknar högst en färgning inom en faktor O ( n (log log  n ) ² (log n) ^-3 ) av det kromatiska talet. För alla ε  > 0, som approximerar den kromatiska nummer inom n ^{1- ε} är NP-svårt .

Det är också NP-svårt att färga en trefärgbar graf med 4 färger och en k- färgbar graf med k ^{(log k  ) / 25} färger för tillräckligt stor konstant k .

Beräkningskoefficienterna för det kromatiska polynomet är #P-hårt . Faktum är att även beräkningen av värdet är #P-hård vid någon rationell punkt k förutom k  = 1 och k  = 2. Det finns ingen FPRAS för att utvärdera det kromatiska polynomet vid någon rationell punkt k  ≥ 1,5 förutom k  = 2 om inte NP  =  RP . ${\ displaystyle \ chi (G, k)}$

För kantfärgning ger beviset på Vizinges resultat en algoritm som använder högst Δ+1 färger. Att avgöra mellan de två kandidatvärdena för kantkromatiskt tal är emellertid NP-komplett. När det gäller approximationsalgoritmer visar Vizingings algoritm att kantkromatiskt tal kan approximeras till inom 4/3, och hårdhetsresultatet visar att det inte finns någon (4/3-  ε  ) -algoritm för någon ε> 0 om inte P = NP . Dessa är bland de äldsta resultaten i litteraturen om approximationsalgoritmer, även om inget papper uttryckligen använder den tanken.

Ansökningar

Schemaläggning

Vertex färgmodeller till ett antal schemaläggningsproblem . I den renaste formen måste en viss uppsättning jobb tilldelas tidsluckor, varje jobb kräver en sådan plats. Jobb kan schemaläggas i valfri ordning, men par av jobb kan vara i konflikt i den meningen att de kanske inte tilldelas samma tidslucka, till exempel för att de båda är beroende av en delad resurs. Motsvarande graf innehåller en toppunkt för varje jobb och en kant för varje motstridigt jobb. Det kromatiska antalet i grafen är exakt den lägsta tillverkningstiden , den optimala tiden för att slutföra alla jobb utan konflikter.

Detaljer om schemaläggningsproblemet definierar grafens struktur. Till exempel, när du tilldelar flygplan till flygningar, är det resulterande konfliktdiagrammet ett intervalldiagram , så färgproblemet kan lösas effektivt. Vid tilldelning av bandbredd till radiostationer är det resulterande konfliktdiagrammet en enhetsdiskgraf , så färgproblemet är 3-approximabelt.

Registrera tilldelning

En kompilator är ett datorprogram som översätter ett datorspråk till ett annat. För att förbättra exekveringstiden av den resulterande koden är en av de metoder för kompilatorn optimering är registerallokering , där de mest använda värden för den kompilerade programmet hålls i de snabba processorregister . Helst tilldelas värden till register så att de alla kan bo i registren när de används.

Textbokens tillvägagångssätt för detta problem är att modellera det som ett graffärgningsproblem. Kompilatorn konstruerar en störningsgraf , där hörn är variabler och en kant förbinder två hörn om de behövs samtidigt. Om grafen kan färgas med k färger kan alla uppsättningar variabler som behövs samtidigt lagras i högst k register.

Andra applikationer

Problemet med att måla en graf uppstår inom många praktiska områden som mönstermatchning , schemaläggning av sport, utformning av sittplaner, tidtabell för tentamen, schemaläggning av taxibilar och lösning av Sudokupussel .

Andra färgämnen

Ramsey -teorin

En viktig klass av felaktiga färgproblem studeras i Ramsey -teorin , där grafens kanter tilldelas färger, och det finns ingen begränsning av färgerna på infallande kanter. Ett enkelt exempel är vänskapssatsen , som säger att det i varje färgning av kanterna på det fullständiga diagrammet med sex hörn kommer att finnas en monokromatisk triangel; illustreras ofta genom att säga att varje grupp på sex personer antingen har tre gemensamma främlingar eller tre gemensamma bekanta. Ramsey -teorin handlar om generaliseringar av denna idé för att söka regelbundenhet bland störningar och hitta allmänna förutsättningar för förekomsten av monokromatiska subgrafer med given struktur. ${\ displaystyle K_ {6}}$

Andra färgämnen

Färgning kan också övervägas för signerade grafer och vinstdiagram .

Se även

• Kritisk graf
• Graf homomorfism
• Hajós konstruktion
• Sudokus matematik
• Flerdelad graf
• Unikt färgbart diagram
• Graffärgningsspel

Anteckningar

Referenser

externa länkar

• High-Performance Graph Coloring Algorithms Suite med 8 olika algoritmer (implementerade i C ++) som används i boken A Guide to Graph Coloring: Algorithms and Applications (Springer International Publishers, 2015).
• Graph Coloring Page av Joseph Culberson (graffärgningsprogram)
• CoLoRaTiOn av Jim Andrews och Mike Fellows är ett graffärgspussel
• Länkar till Graph Coloring -källkoder
• Kod för effektivt beräkning av Tutte, Chromatic and Flow Polynomials av Gary Haggard, David J. Pearce och Gordon Royle
• En graffärgning Web App av Jose Antonio Martin H.