Färglägga grafer

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 26 juni 2019; kontroller kräver 15 redigeringar .

Graffärgning är en grafteoretisk konstruktion , ett specialfall av grafmarkering. Vid färgläggning tilldelas grafelement etiketter med vissa begränsningar; dessa etiketter kallas traditionellt för "färger". I det enklaste fallet kallas ett sådant sätt att färga toppen av en graf , där två närliggande hörn motsvarar olika färger, vertexfärgning . På liknande sätt tilldelar kantfärgning en färg till varje kant så att två intilliggande kanter har olika färger [1] . Slutligen tilldelar regionfärgningen av en plan graf en färg till varje region, så att vartannat område som delar en gräns inte kan ha samma färg.

Vertexfärgning är huvudproblemet med graffärgning, alla andra problem i detta område kan reduceras till det. Till exempel är färgningen av kanterna på en graf färgningen av hörnen på dess linjegraf , och färgningen av regionerna i en plan graf är färgningen av hörnen på dess dubbla graf [1] . Men andra graffärgningsproblem uppstår och löses ofta i den ursprungliga inställningen. Anledningen till detta är dels för att det ger en bättre uppfattning om vad som händer och är mer avslöjande, dels för att vissa problem är mer bekväma att lösa på detta sätt (till exempel kantfärgning).

Graffärgning finner tillämpning inom många praktiska områden, och inte bara i teoretiska problem. Förutom de klassiska typerna av problem kan olika begränsningar även läggas på grafen, på hur färger tilldelas eller på själva färgerna. Denna metod används till exempel i det populära Sudoku- pusslet . Det finns fortfarande aktiv forskning inom detta område.

Historik

De första resultaten erhölls för plana grafer i kartfärgningsproblemet. I ett försök att färglägga en karta över grevskapen i England, formulerade Francis Guthrie fyrfärgsproblemet , och noterade att fyra färger räcker för att färglägga kartan så att två intilliggande regioner har olika färger. Hans bror hänvisade frågan till sin matematiklärare, Augustus de Morgan , som nämnde den i sitt brev till William Hamilton 1852. Arthur Cayley tog upp detta problem vid ett möte i London Mathematical Society 1878. Samma år föreslog Tate den första lösningen på detta problem. Han reducerade färgningen av hörnen på den ursprungliga grafen till färgningen av kanterna på den dubbla grafen och föreslog att detta problem alltid har en lösning [2] . 1880 publicerade Alfred Kempe en artikel som hävdade att han hade lyckats fastställa resultatet, och under ett decennium ansågs problemet med fyra färger vara löst. För denna prestation valdes Kempe till en kollega i Royal Society of London och senare president för London Mathematical Society [3] .

År 1890 hittade Heawood ett fel i Kempes bevis. I samma artikel bevisade han femfärgssatsen , vilket visar att vilken platt karta som helst kan färgläggas med högst fem färger. Därvid förlitade han sig på Kempes idéer. Under nästa århundrade utvecklades ett stort antal teorier i ett försök att minska det minsta antalet färger. Fyrfärgssatsen bevisades slutligen 1977 av forskarna Kenneth Appel och Wolfgang Haken med hjälp av datoruppräkning. Idén med beviset förlitade sig starkt på idéerna från Heawood och Kempe och ignorerade de flesta av mellanstudierna [4] . Beviset för fyrafärgssatsen är ett av de första bevisen där en dator användes.

År 1912 föreslog George David Birkhoff att använda det kromatiska polynomet , en viktig del av algebraisk grafteori, för att studera färgproblem . Det kromatiska polynomet generaliserades därefter av William Tutt ( Tutts polynom ). Kempe redan 1879 uppmärksammade det allmänna fallet då grafen inte var plan [5] . Många resultat av generaliseringar av färgplansgrafer på ytor av högre ordning dök upp i början av 1900-talet.

År 1960 formulerade Claude Burge den perfekta grafförmodan , motiverad av en idé från informationsteorin , nämligen grafkapaciteten nollfel [6] som introducerades av Shannon . Uttalandet förblev obekräftat i 40 år, tills det bevisades som den berömda strikta perfekta grafsatsen av matematikerna Chudnovskaya , Robertson , Seymour och Thomas 2002.

Graffärgning som ett algoritmiskt problem har studerats sedan 1970-talet: att bestämma det kromatiska talet är ett av Karps 21 NP-kompletta problem (1972). Och ungefär samtidigt utvecklades olika algoritmer baserade på backtracking och Zykovs rekursiva radering och kontraktion [7] . Sedan 1981 har graffärgning använts för registerallokering i kompilatorer [8] .

Definition och terminologi

Vertexfärgning

När folk pratar om att färglägga grafer menar de nästan alltid att färga sina hörn, det vill säga att tilldela färgetiketter till grafens hörn så att alla två hörn som har en gemensam kant har olika färger. Eftersom loopade grafer inte kan färgas på detta sätt är de uteslutna.

Terminologin där etiketterna kallas färger kommer från färgläggningen av politiska kartor. Etiketter som rött eller blått används endast när antalet färger är litet, men etiketterna antas vanligtvis vara heltal . $\{1,2,3,...\}$

Att färga med färger kallas -färgning . Det minsta antalet färger som behövs för att färga en graf kallas dess kromatiska tal och skrivs ofta som . Används ibland , eftersom det betecknar Euler-egenskapen . En delmängd av hörn markerade i en färg kallas en färgklass , varje sådan klass bildar en oberoende uppsättning . Således är -färgning detsamma som att dela upp hörn i oberoende mängder [1] . $k$ $k$ $G$ $\chi (G)$ $\gamma (G)$ $\chi (G)$ $k$ $k$

Kromatiskt tal i termer av avståndet Gromov-Hausdorff

Låta vara en godtycklig graf med vertex set . Vi fixar två positiva reella tal , och vi kommer att betrakta det som ett metriskt utrymme där avstånden mellan angränsande hörn är lika med , och alla andra avstånd som inte är noll är lika med . Beteckna med det metriska utrymmet som består av punkter separerade från varandra med ett avstånd . Slutligen, för två metriska utrymmen och , beteckna Gromov-Hausdorff-avståndet mellan och . Då gäller följande resultat. $G$ $V$ $a<b\leq 2a$ $V$ $b$ $a$ ${\displaystyle a\Delta _{m))$ $m$ $a$ $X$ $Y$ $d_{GH}(X,Y)$ $X$ $Y$

Sats (A.O. Ivanov, A.A. Tuzhilin) [9] : Låt vara det största naturliga talet för vilket (om sådana naturliga tal inte finns, då sätter vi ). Sedan .

m

d_{GH}(V,a\Delta _{m})=b

m=0

\chi (G)=m+1

Kommentar.

Det kromatiska talet är , om och endast om grafen inte innehåller några kanter. I det här fallet gäller inte jämlikhet för någon , därför enligt konvention, , vilket leder till korrekt jämlikhet . $\chi (G)$ $ett$ $G$ $d_{GH}(V,a\Delta _{m})=b$ $m$ $m=0$ $\chi (G)=0+1=1$

Per definition överstiger inte antalet element i uppsättningen . Å andra sidan är det lätt att visa att för varje , därför, och därmed . $\chi (G)$ $n$ $V$ $d_{GH}(V,a\Delta _{p})\leq \max\{a,\,ba\}<b$ $p\geq n$ $m<n$ $\chi (G)=m+1\leq n$

Kromatiskt polynom

Ett kromatiskt polynom är en funktion som räknar antalet t - färgningar i en graf . Av namnet följer att för givet är denna funktion ett polynom beroende på t . $P(G,t)$ $G$ $G$

Detta faktum upptäcktes av Birkhoff och Lewis när de försökte bevisa de fyra färgerna [10] .

Till exempel kan grafen i bilden till höger färgläggas på 12 sätt med 3 färger. Den kan i princip inte målas med två färger. Med 4 färger får vi 24+4*12 = 72 färgalternativ: när du använder alla 4 färgerna finns det 4! = 24 korrekta sätt ( varje tilldelning av 4 färger för en graf med 4 hörn är korrekt); och för varje 3 färger av dessa 4 finns det 12 sätt att färga. Sedan för grafen i exemplet börjar tabellen med antal korrekta färger så här:

Tillgängligt antal färger	ett	2	3	fyra	…
Antal sätt att färga	0	0	12	72	…

För grafen i exemplet och, naturligtvis, . $P(G,t)=t(t-1)^{2}(t-2)$ $P(G,4)=72$

Ett kromatiskt polynom innehåller minst lika mycket information om färgsättning som ett kromatiskt tal. Det är faktiskt det minsta positiva heltal som inte är en rot av ett kromatiskt polynom. $G$ $\chi$

\chi (G)=\min\{t\,\colon \,P(G,t)>0\}.

Kromatiska polynom för vissa grafer

Triangulär $K_{3}$	$t(t-1)(t-2)$
Komplett graf $K_n$	$t(t-1)(t-2)\cdots (t-(n-1))$
träd med revben $n$	$t(t-1)^{{n}}$
Cykel $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
Greve av Petersen	$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 innebär att tilldela färger till kanter på ett sådant sätt att inte två kanter av samma färg hör till samma vertex. Detta problem motsvarar att dela upp uppsättningen ansikten i uppsättningar av oberoende ansikten . Det minsta antalet färger som behövs för en kantfärgning av en graf är dess kromatiska index eller kantkromatiska nummer . $G$ $\chi '(G)$

Total färgläggning

Totalfärgning är en typ av färgläggning av hörn och kanter på en graf. Med det menas en sådan tilldelning av färger att varken angränsande hörn, eller intilliggande kanter, eller hörn och kanter som förbinder dem, har samma färg. Det totala kromatiska antalet av en graf är det minsta antal färger som behövs för en komplett färgning. $\chi ''(G)$ $G$

Egenskaper

Egenskaper för det kromatiska polynomet

Om är en tom graf [11] , $G$

P(G,t)=1

Om grafen är föreningen av disjunkta subgrafer och [11] , $G$ $H$ $K$

P(G,t)=P(H,t)P(K,t)

Om det finns en slinga i [11] , $G$

P(G,t)=0

Restriktioner för kromatiskt nummer

Att tilldela olika färger till alla hörn ger alltid rätt färg, så

1\leq \chi (G)\leq n.

Den enda sortens grafer som kan färgas i en färg är nollgrafer .
En komplett graf som består av hörn kräver färger. $K_n$ $n$ $\chi (K_{n})=n$
I en optimal färgläggning måste det finnas minst en grafkant mellan varannan färgklass, så [12] $m$

\chi (G)(\chi (G)-1)\leq 2m.

Om är föreningen av osammanhängande subgrafer och , då $G$ $H$ $K$

\chi (G)=max\{\chi (H),\chi (K)\}

Om den innehåller klicker av storlek k , behövs minst k färger för att färga denna klick, med andra ord, det kromatiska talet är större än eller lika med klicknumret : $G$

\chi (G)\geq \omega (G).

För intervallgrafer är denna begränsning exakt.

Genom fyrafärgssatsen kan vilken plan graf som helst färgas med fyra färger.
2-färgbara grafer är tvådelade grafer , inklusive träd .

En graf är tvådelad om och endast om den inte innehåller cykler med udda längd [11] .

G

Girig färgning visar att vilken graf som helst kan färgläggas med en färg mer än dess maximala vertexgrad [12] .

\chi (G)\leq \Delta (G)+1.

Kompletta grafer har och , cykelgrafer har och , så för dem är denna begränsning bäst, i alla andra fall kan begränsningen förbättras: Brooks' teorem [13] säger att $\chi (G)=n$ $\Delta(G)=n-1$ $\chi (G)=3$ $\Delta(G)=2$

\chi (G)\leq \Delta (G)

för en sammankopplad, enkel graf om är varken en komplett graf eller en cykelgraf.

G

G

Grafer med stort kromatiskt tal

Grafer med stora klick har stora kromatiska tal, men det omvända är inte alltid sant. Grötzsch-grafen är ett exempel på en triangelfri 4-färgbar graf, och detta exempel kan generaliseras till Mycielski-grafen .

Mychelskis teorem (Alexander Zykov 1949, Jan Mychelski 1955): Det finns grafer utan trianglar med godtyckligt stora kromatiska tal.

Från Brooks teorem måste grafer med stort kromatiskt tal ha en hög maximal vertexgrad. Ett annat lokalt tillstånd på grund av vilket det kromatiska talet kan vara stort är närvaron av en stor klick. Men grafens färgbarhet beror inte bara på lokala förhållanden: en graf med stor omkrets ser lokalt ut som ett träd, så alla cykler är långa, men dess kromatiska tal är inte lika med 2:

Erdős teorem : Det finns grafer med godtyckligt stor omkrets och kromatiskt tal [12] .

Restriktioner för det kromatiska indexet

En kantfärgning är en färgning av hörnen på dess linjediagram . Det är $G$ $L(G)$

\chi '(G)=\chi (L(G)).

Dessutom [14] ,

Königs sats : , om är tvådelad.

\chi '(G)=\Delta (G)

G

I allmänhet är sambandet mycket starkare än vad Brooks sats för vertexfärgning [14] ger :

Vizings teorem: En graf med maximal vertexgrad har ett kantkromatiskt tal eller .

\Delta

\Delta

\Delta +1

Andra egenskaper

En graf är k - kromatisk om och endast om den har en acyklisk orientering , för vilken längden på den längsta banan är k . Detta bevisades i Gallai-Hasse-Roy-Vitavers sats [15] .
För plana grafer motsvarar vertexfärgning ingenstans nollflöde .
Mycket mindre är känt om oändliga grafer. Nedan finns två resultat för färgläggning av oändliga grafer.

Om alla finita subgrafer i en oändlig graf är k -kromatiska, så är k - kromatiska (bevisade under antagandet av valets axiom ). Detta är formuleringen av de Bruijn-Erdős sats [16] . $G$ $G$
Om en graf medger en fullständig n -färgning för någon , då tillåter den en oändlig fullständig färgning [17] . $n\geqslant n_{0}$

Öppna frågor

Det kromatiska numret för ett plan där två punkter ligger intill om det finns ett enhetsavstånd mellan dem är okänt. Det kan vara 5, 6 eller 7. Andra öppna frågor om det kromatiska antalet grafer inkluderar Hadwiger-förmodan , som säger att varje graf med kromatiskt nummer k har en komplett graf med k hörn som sin mindre , Erdős-Faber-Lovas gissningar , som begränsar det kromatiska antalet kompletta grafer som har exakt en gemensam vertex för varje par av grafer, och Albertsons gissning att bland k - kromatiska grafer är de med minst antal skärningspunkter kompletta .

När Birkov och Lewis introducerade det kromatiska polynomet i deras försök att lösa fyrfärgssatsen, hävdade de att för plana grafer har polynomet inga nollor i domänen . Även om det är känt att ett sådant kromatiskt polynom inte har några nollor i domänen , och att deras påstående förblir obevisade. Det förblir också en öppen fråga hur man särskiljer grafer med samma kromatiska polynom och hur man avgör att ett polynom är kromatiskt. $G$ $P(G,t)$ $[4,\infty )$ $[5,\infty )$ $P(G,4)\nekv 0$

Färgläggningsalgoritmer

Polynomalgoritmer

För en tvådelad graf beräknas färgningsproblemet i linjär tid med hjälp av bredd-först-sökning . I fallet med perfekta grafer kan det kromatiska talet och dess motsvarande färgning hittas i polynomtid med semidefinite programmering . Exakta formler för att hitta det kromatiska talet är kända för många klasser av grafer (skogar, cykler , hjul , ackordsgrafer ) och kan även beräknas i polynomtid.

Exakta algoritmer

Den uttömmande sökalgoritmen för fallet med k-färgning beaktar alla kombinationer av färgarrangemang i en graf med n hörn och kontrollerar att de är korrekta. För att beräkna det kromatiska talet och det kromatiska polynomet tar denna algoritm varje k från 1 till n. I praktiken kan en sådan algoritm endast tillämpas på små grafer. $k^{n}$

Genom att använda dynamisk programmering och uppskatta storleken på den största oberoende uppsättningen kan möjligheten för k-färgning i en graf lösas i tid [18] . Snabbare algoritmer för 3- och 4-färgningar är kända som går i tid [19] respektive [20] . $O(2 445^{n})$ $O(1,3289^{n})$ $O(1,7272^{n})$

Sammandragning

Vertexkontraktion är en operation som gör en graf från en graf genom att identifiera hörn och , ta bort kanterna som förbinder dem och ersätta dem med en vertex , där kanterna faller in mot hörnen och omdirigeras . Denna operation spelar en viktig roll i graffärgningsanalys. $G$ $g/uv$ $u$ $v$ $w$ $u$ $v$

Det kromatiska talet uppfyller repetitionsrelationen

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

där och är icke-angränsande hörn, är en graf med en extra kant . Vissa algoritmer är baserade på detta förhållande och producerar ett träd som ett resultat, ibland kallat ett Zykov-träd. Exekveringstiden beror på vertexvalsmetoden och . $u$ $v$ $G+uv$ $UV$ $u$ $v$

Det kromatiska polynomet uppfyller återfallsrelationen

$P(G-uv,t)=P(G/uv,t)+P(G,t)$ ,

där och är angränsande hörn, är en graf med kanten borttagen . representerar antalet möjliga korrekta färger av grafen, när hörnen och kan ha samma eller olika färger. Om och har olika färger, så kan vi överväga en graf där och är intilliggande. Om och har samma färger, kan vi överväga en graf där och är sammanslagna. $u$ $v$ $G-uv$ $UV$ $P(G-uv,t)$ $u$ $v$ $u$ $v$ $u$ $v$ $u$ $v$ $u$ $v$

Uttrycken som ges ovan leder till en rekursiv procedur som kallas remove and contract algoritmen , som har legat till grund för många graffärgningsalgoritmer. Körtiden uppfyller samma återfallsrelation som Fibonacci-talen , så i värsta fall kommer algoritmen att köras i tid för n hörn och m kanter [21] . I praktiken undviker metoden förgrening och bunden och förkastandet av isomorfa grafer vissa rekursiva anrop, körtiden beror på metoden för att välja ett par hörn. $((1+{\sqrt 5})/2)^{{n+m}}=O(1,6180^{{n+m}})$

Girig färgläggning

Den giriga algoritmen sorterar hörnen ,..., och tilldelar sekventiellt till vertexen den minsta tillgängliga färgen som inte användes för att färga grannarna bland ,..., , eller lägger till en ny. Kvaliteten på den resulterande färgningen beror på den valda ordningen. Det finns alltid en ordning som för den giriga algoritmen till det optimala antalet färger. Å andra sidan kan en girig algoritm vara godtyckligt dålig; till exempel kan en krona med n hörn färgas med 2 färger, men det finns en ordning på hörn som resulterar i en girig färgning av färger. $v_{1}$ $v_{n}$ $v_{i}$ $v_{i}$ $v_{1}$ $v_{{i-1}}$ $\chi (G)$ $n/2$

För en ackordsgraf och för dess speciella fall (som en intervallgraf ), kan den giriga färgningsalgoritmen användas för att hitta den optimala färgningen i polynomtid genom att välja ordningen på hörnen så att den är den omvända av den perfekta elimineringsordningen . Denna algoritm kan tillämpas på en bredare klass av grafer ( helt beställningsbara grafer ), men att hitta en sådan ordning för sådana grafer är ett NP-svårt problem.

Om hörnen är ordnade efter deras grader, använder den giriga färgningsalgoritmen högst färger, vilket är högst 1 mer än (här , graden av vertex ). Denna heuristiska algoritm kallas ibland för Welsh-Powell-algoritmen [22] . En annan algoritm ställer in ordningen dynamiskt och väljer nästa vertex från den med de mest intilliggande hörnen av olika färger. Många andra graffärgningsalgoritmer är baserade på giriga färgsättningar och använder statiska eller dynamiska vertexordningsstrategier. $max_{i}min\{d(v_{i})+1,i\}$ $\Delta$ $d(v_{i})$ $v_{i}$

Parallella och distribuerade algoritmer

Ett liknande problem uppstår inom området distribuerade algoritmer. Låt oss säga att grafens hörn är datorer som kan kommunicera med varandra om de är förbundna med en kant. Målet är att varje dator ska välja en "färg" för sig själv, så att närliggande datorer väljer olika färger. Detta problem är nära relaterat till symmetribrytningsproblemet . De mest utvecklade probabilistiska algoritmerna är snabbare än deterministiska algoritmer för grafer med en tillräckligt stor maximal grad av hörn . De snabbaste probabilistiska algoritmerna använder tekniken med flera försök [23] . $\Delta$

I symmetriska grafer kan deterministiska distribuerade algoritmer inte hitta den optimala vertexfärgen. Mer information behövs för att undvika symmetri. Ett standardantagande görs att varje vertex initialt har en unik identifierare, till exempel från mängden . Med andra ord antas det att vi får en n -färgning. Uppgiften är att minska antalet färger från n till t.ex. Ju fler färger som används (till exempel istället för ), desto färre meddelandeutbyten kommer att krävas [23] . $\{1,2,...,N\}$ $(\Delta+1)$ $O(\Delta )$ $(\Delta+1)$

En enkel version av den distribuerade giriga algoritmen för -färgning kräver kommunikationsrundor i värsta fall - information kan behöva gå från ena änden av nätverkssidan till den andra. $(\Delta+1)$ $\Theta(n)$

Det enklaste intressanta fallet är n -cykeln. Richard Cole och Uzi Vishkin [24] har visat att det finns en distribuerad algoritm som minskar antalet färger från n till , med endast ett grannmeddelande. Genom att upprepa samma procedur kan man få en n -cykel 3-färgning i anslutningsrundor (förutsatt att unika nodidentifierare ges). $O(log(n))$ $O(log^{*}(n))$

Funktionen , itererad logaritm , är en extremt långsamt växande funktion, "nästan en konstant". Därför väcker resultaten av Cole och Vishkin frågan om det finns en distribuerad n-cykel 3-färgningsalgoritm som körs i konstant tid. Nathan Linial visade att detta är omöjligt: varje deterministisk distribuerad algoritm kräver kommunikationsrundor för att reducera en N -färgning till en 3-färgning i en n-cykel [25] . $log^{*}$ $\Omega (log^{*}(n))$

Tekniken från Cole och Vishkin kan också tillämpas på en godtycklig graf med en avgränsad grad av hörn, i vilket fall körtiden är [26] . Denna metod har generaliserats till enhetscirkelgrafen av Schneider et al [27] . $P(\Delta )+O(log^{*}(n))$

Kantfärgningsproblemet har också studerats i en distribuerad modell. Pansonezzi och Rizzi uppnådde -färgning för i denna modell [28] . Den nedre gränsen för distribuerad vertexfärgning som uppnås av Linial är också tillämplig på problemet med distribuerad kantfärgning [25] . $(2\Delta -1)$ $O(\Delta +log^{*}(n))$

Decentraliserade algoritmer

Decentraliserade algoritmer kallas algoritmer där intern meddelandeöverföring inte är tillåten (i motsats till distribuerade algoritmer , där processer utbyter data med varandra). Det finns effektiva decentraliserade algoritmer som framgångsrikt klarar uppgiften att färglägga grafer. Dessa algoritmer fungerar utifrån antagandet att en vertex kan "känna" att någon av dess närliggande hörn har samma färg som den. Det är med andra ord möjligt att definiera en lokal konflikt. Ett sådant villkor uppfylls ganska ofta i verkliga applikationer - till exempel när data överförs över en trådlös kanal, har en sändande station som regel förmågan att upptäcka att en annan station försöker sända samtidigt på samma kanal. Förmågan att erhålla sådan information är tillräcklig för att algoritmer baserade på inlärningsautomater korrekt ska lösa graffärgningsproblemet [29] [30] med sannolikhet ett .

Beräkningskomplexitet

Graffärgning är en beräkningsmässigt svår uppgift. Att ta reda på om en graf kan k -färgas för ett givet k är ett NP-komplett problem, förutom fallen k = 1 och k = 2. I synnerhet är problemet med att beräkna det kromatiska talet NP-hårt [31] . 3-färgsproblemet är NP-komplett även för fallet med en plan graf av grad 4 [32] .

Det är också ett NP-svårt problem att färga en 3-färgbar graf med 4 färger [33] och en k -färgbar graf för tillräckligt stora värden på k [34] . $k^{{log(k)/25}}$

Att beräkna koefficienterna för ett kromatiskt polynom är ett #P-hårt problem. Det har bevisats att det inte finns någon FPRAS- algoritm för att beräkna det kromatiska polynomet för något rationellt tal k ≥ 1,5 annat än k = 2, såvida inte NP = RP [35] .

Applikation

Planering

Vertexfärgning modellerar många planeringsproblem [36] . I sin enklaste inställning bör en given uppsättning jobb fördelas över tidsintervall, varje sådant jobb upptar ett segment. De kan utföras i vilken ordning som helst, men de två jobben kan komma i konflikt i den meningen att de inte kan utföras samtidigt eftersom de till exempel använder delade resurser. Motsvarande graf innehåller en vertex för varje jobb och en kant för varje motstridig par. Det kromatiska numret på den konstruerade grafen är den minsta tiden för att slutföra alla jobb utan konflikter.

Detaljerna i schemaläggningsproblemet bestämmer grafens struktur. Till exempel, när det finns en uppdelning av flygplan i flygningar, är den resulterande konfliktgrafen en intervallgraf , så färgningsproblemet kan lösas effektivt. Vid distribution av radiofrekvenser erhålls en graf över enhetskonfliktcirklar , och för ett sådant problem finns en 3-approximationsalgoritm .

Registertilldelning

En kompilator är ett datorprogram som översätter ett datorspråk till ett annat. För att förbättra exekveringstiden för den resulterande koden är en av kompilatoroptimeringsteknikerna registerallokering , där de mest använda variablerna i det kompilerade programmet lagras i höghastighetsprocessorregister . Idealiskt lagras variabler i register så att de alla finns i register vid den tidpunkt de används.

Standardmetoden för detta problem är att reducera det till ett graffärgningsproblem [8] . Kompilatorn bygger en interferensgraf , där hörn motsvarar variabler, och en kant förbinder två av dem om de behövs samtidigt. Om denna graf är k -kromatisk kan variablerna lagras i k register.

Digitala vattenstämplar

Tekniken för digitala vattenstämplar ( eng. digital watermarking ) låter dig överföra ett dolt meddelande tillsammans med data (vare sig det är mediafiler , körbara filer och andra) (" vattenstämpel ", vattenstämpel ). Ett sådant dolt meddelande kan användas i upphovsrättsskyddet för att identifiera ägaren av data.

Detta är viktigt, till exempel för att fastställa källan till deras illegala distribution. Eller för att bekräfta rättigheterna till data, till exempel - mjukvarusystem på ett chip ( system-on-chip ).

Meddelandet kan också kodas på det sätt som register tilldelas. En sådan teknik föreslogs av Qu och Potkonjak [37] (vilket är anledningen till att den ibland kallas QP-algoritmen).

Den består av följande: låt vara inkompatibilitetsdiagrammet (interferensdiagram) för distributionen av processorregister, som nämndes ovan. Dess färgning används i programmet - dessutom används den på ett sådant sätt att det är tillåtet att ändra innehållet i grafen med en liten ökning av dess kromatiska nummer . Det visar sig att det är möjligt att koda ett meddelande i en mjukvaruprodukt med hjälp av graffärgning , det vill säga distributionen av register. $G$ $G$

Du kan extrahera detta meddelande genom att jämföra distributionen av register med den ursprungliga färgen; [38] det finns också sätt att verifiera om ett meddelande kodades i programmet utan att använda originalet.

Därefter utvecklade och förfinade olika författare Qus och Potkonjaks idéer [39] . [38] [40]

Andra användningsområden

Graffärgningsproblemet har uppstått i många andra applikationer, inklusive mönstermatchning .

Att lösa ett Sudoku -pussel kan ses som att slutföra en 9-färgsfärgning av en given graf med 81 hörn.

Anteckningar

↑ 1 2 3 ( Molloy & Reed 2002 , The Basic Definitions )
↑ ( Donets & Shor 1982 , Historisk bakgrund )
↑ ( Kubale 2004 , Historia om graffärgning )
↑ ( van Lint & Wilson 2001 , kap. 33)
↑ ( Jensen & Toft 1995 , s. 2)
↑ CE Shannon, "Nullfelskapaciteten hos en bullrig kanal," IEEE Trans. Information Theory , s. 8-19, 1956.
↑ ( Zykov 1949 )
↑ 1 2 ( Chaitin 1982 )
↑ AOIvanov, AATuzhilin (2019), The Gromov-Hausdorff Distance between Simplexes and Two-Distance Spaces , < https://arxiv.org/pdf/1907.09942.pdf > Arkiverad 29 juli 2019 på Wayback Machine
↑ ( Birkhoff & Lewis 1946 )
↑ 1 2 3 4 ( Tutte 1984 , Chromatic polynomial )
↑ 1 2 3 ( Diestel 2005 , Färga hörn )
↑ ( Brooks & Tutte 1941 )
↑ 1 2 ( Diestel 2005 , Coloring edges )
↑ ( Nesetřil & Ossona de Mendez 2012 )
↑ ( de Bruijn, Erdős 1951 )
↑ ( Fawcett 1978 )
↑ ( Lawler 1976 )
↑ ( Beigel & Eppstein 2005 )
↑ ( Fomin, Gaspers & Saurabh 2007 )
↑ ( Sekine, Imai & Tani 1995 )
↑ ( Welsh & Powell 1967 )
↑ 1 2 ( Schneider 2010 )
↑ ( Cole & Vishkin 1986 ), se även ( Cormen, Leiserson & Rivest 1990 , avsnitt 30.5)
↑ 1 2 ( Linial 1992 )
↑ ( Goldberg, Plotkin & Shannon 1988 )
↑ ( Schneider 2008 )
↑ ( Panconesi & Rizzi 2001 )
↑ ( Leith & Clifford 2006 )
↑ ( Duffy, O'Connell & Sapozhnikov 2008 )
↑ ( Garey, Johnson & Stockmeyer 1974 ); ( Garey & Johnson 1979 ).
↑ ( Dailey 1980 )
↑ ( Guruswami & Khanna 2000 )
↑ ( Khot 2001 )
↑ ( Goldberg & Jerrum 2008 )
↑ ( Marx 2004 )
↑ ( Qu & Potkonjak 1998 )
↑ 1 2 ( Zhu & Thomborson 2006 )
↑ ( Collberg, Thomborson & Townsend 2004 )
↑ ( Myles & Collberg 2003 )

Litteratur

Donets, G. A. & Shor, N. Z. (1982), An Algebraic Approach to the Plane Graph Coloring Problem , Naukova Dumka, sid. 5-7
Zykov, A. A. (1949), Om några egenskaper hos linjära komplex , Mat. lö. T. 24(66) (2): 163–188 , < http://mi.mathnet.ru/eng/msb5974 >
Beigel, R. & Eppstein, D. (2005), 3-färgning i tid O(1.3289 n ) , Journal of Algorithms vol 54 (2)): 168–204 , DOI 10.1016/j.jalgor.2004.06.008
Birkhoff, G.D. & Lewis, D.C. (1946), Chromatic Polynomials , Trans. amer. Matematik. soc. T. 60 : 355-451 , >
Brélaz, D. (1979), New methods to color the tops of a graph , Communications of the ACM vol. 22 (4): 251–256 , DOI 10.1145/359094.359101
Brooks, R.L. & Tutte, WT (1941), On coloring the nodes of a network , Proceedings of the Cambridge Philosophical Society vol 37 (2): 194–197 , DOI 10.1017/S030500410002168X
N. G. de Bruijn, P. Erdős . Ett färgproblem för oändliga grafer och ett problem i relationsteorin (engelska) // Nederl. Akad. Wetensch. Proc. Ser. A. - 1951. - T. 54 . - S. 371-373 . (= Indag. Math. 13 )
Byskov, JM (2004), Uppräkning av maximala oberoende uppsättningar med tillämpningar för graffärgning , Operations Research Letters vol. 32 (6): 547–556 , DOI 10.1016/j.orl.2004.03.002
Cormen, T.H.; Leiserson, CE & Rivest, RL (1990), Introduction to Algorithms (1:a upplagan), The MIT Press
Collberg, Christian; Thomborson, Clark & Townsend, Gregg M. (2004), Dynamic Graph-Based Software Watermarking , < ftp://ftp.cs.arizona.edu/reports/2004/TR04-08.pdf >
Chaitin , GJ (1982), Registerfördelning & spilling via graffärgning , Proc. 1982 SIGPLAN Symposium on Compiler Construction , sid. 98–105, ISBN 0-89791-074-5 , DOI 10.1145/800230.806984
Cole, R. & Vishkin, U. (1986), Deterministisk myntkastning med tillämpningar för optimal parallelllistrankning , Information and Control vol. 70 (1): 32–53 , DOI 10.1016/S0019-9958(86)80023-7
Dailey, D.P. (1980), Det unika med färgbarheten och färgbarheten hos plana 4-regelbundna grafer är NP-kompletta , Discrete Mathematics vol 30 (3): 289–293 , DOI 10.1016/0012-365X(860-80230)902
Diestel, R. (2005), Graph theory , < http://www.math.ubc.ca/~solymosi/2007/443/GraphTheoryIII.pdf > Arkiverad 25 november 2014 på Wayback Machine
Duffy, K.; O'Connell, N. & Sapozhnikov, A. (2008), Complexity analysis of a decentralized graph coloring algorithm , Information Processing Letters vol . 107: 60–63, doi : 10.1016/j.ipl.2008.01.002 , < http: //www.hamilton.ie/ken_duffy/Downloads/cfl.pdf >
Fawcett, BW (1978), Om oändliga fullfärgningar av grafer, Can. J Math. T. XXX: 455–457
Fomin, FV; Gaspers, S. & Saurabh, S. (2007), Förbättrade exakta algoritmer för att räkna 3- och 4-färgningar , Proc. 13:e årliga internationella konferensen, COCOON 2007 , vol. 4598, Lecture Notes in Computer Science , Springer, sid. 65-74, ISBN 978-3-540-73544-1
Garey, MR & Johnson, DS (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , W. H. Freeman, ISBN 0-7167-1045-5
Goldberg, LA & Jerrum, M. (juli 2008), Inapproximability of the Tutte polynomial , Information and Computation vol. 206 (7): 908–929 , DOI 10.1016/j.ic.2008.04.003
Goldberg, A.V .; Plotkin, SA & Shannon, GE (1988), Parallell symmetry-breaking in sparse graphs , SIAM Journal on Discrete Mathematics vol 1 (4): 434–446 , DOI 10.1137/0401044
Guruswami, V. & Khanna, S. (2000), On the hardness of 4-coloring a 3-colorable graph , Proceedings of the 15th Annual IEEE Conference on Computational Complexity , sid. 188–197, ISBN 0-7695-0674-7 , DOI 10.1109/CCC.2000.856749
Jaeger, F.; Vertigan, DL & Welsh, DJA (1990), On the computational complexity of the Jones and Tutte polynomials , Mathematical Proceedings of the Cambridge Philosophical Society vol. 108: 35–53 , DOI 10.1017/S0305004100068936
Jensen, Tommy R. & Toft, Bjarne (1995), Graph Coloring Problems , John Wiley & Sons, ISBN 0-471-02865-7
Khot, S. (2001), Förbättrade inapproximability-resultat för MaxClique, kromatiskt antal och ungefärlig graffärgning , Proc. 42:a årliga symposiet om grunderna för datavetenskap , sid. 600–609, ISBN 0-7695-1116-3 , DOI 10.1109/SFCS.2001.959936
Kubale, M. (2004), Graph Colorings , American Mathematical Society, ISBN 0-8218-3458-4
Kuhn, F. (2009), Weak graph colorings: distributed algorithms and applications , Proceedings of the 21st Symposium on Parallelism in Algorithms and Architectures , sid. 138–144, ISBN 978-1-60558-606-9
Lawler, EL (1976), A not on the complexity of the chromatic number problem , Information Processing Letters vol 5 (3): 66–67 , DOI 10.1016/0020-0190(76)90065-X
Leith, DJ & Clifford, P. (2006), A Self-Managed Distributed Channel Selection Algorithm for WLAN , Proc. RAWNET 2006, Boston, MA , < http://www.hamilton.ie/peterc/downloads/rawnet06.pdf >
Linial, N. (1992), Locality in distributed graph algorithms , SIAM Journal on Computing vol. 21 (1): 193–201 , DOI 10.1137/0221015
van Lint, JH & Wilson, R.M. (2001), A Course in Combinatorics (2nd ed.), Cambridge University Press, ISBN 0-521-80340-3
Molloy, Michael & Reed, Bruce (2002), Graph coloring and the probabilistic method , Springer, ISBN 3-540-42139-4 , ISSN 0937-5511
Marx, Dániel (2004), Graffärgningsproblem och deras tillämpningar i schemaläggning, Periodica Polytechnica, Electrical Engineering , vol. 48, sid. 11–16, CiteSeerX:10.1.1.95.4268
Mycielski, J. (1955), Sur le coloriage des graphes , Colloq. Matematik. Vol. 3: 161–162 , < http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3119.pdf > .

Myles, Ginger & Collberg, Christian S. (2003), Software Watermarking Through Register Allocation: Implementation, Analysis, and Attacks , ICISC , sid. 274-293 , DOI 10.1007/b96249

Nešetřil, Jaroslav & Ossona de Mendez, Patrice (2012), Theorem 3.13 , Sparsity: Graphs, Structures, and Algorithms , vol. 28, Algorithms and Combinatorics, Heidelberg: Springer, sid. 42, ISBN 978-3-642-27874-7 , DOI 10.1007/978-3-642-27875-4 .
Panconesi, Alessandro & Rizzi, Romeo (2001), Några enkla distribuerade algoritmer för glesa nätverk , Distributed Computing (Berlin, New York: Springer-Verlag ). — V. 14 (2): 97–100, ISSN 0178-2770 , DOI 10.1007/PL00008932
Panconesi, A. & Srinivasan, A. (1996), On the complexity of distributed network decomposition, Journal of Algorithms , vol. tjugo
Qu, Gang & Potkonjak, Miodrag (1998), Analys av vattenmärkningstekniker för graffärgningsproblem , ICCAD , sid. 190-193 , DOI 10.1145/288548.288607
Schneider, J. (2010), A new technique for distributed symmetry breaking , Proceedings of the Symposium on Principles of Distributed Computing , < http://www.dcg.ethz.ch/publications/podcfp107_schneider_188.pdf > Arkiverad 30 juli 2013 kl. Wayback- maskinen
Schneider, J. (2008), A log-star distributed maximal independent set algorithm for growth-bounded graphs , Proceedings of the Symposium on Principles of Distributed Computing , < http://www.dcg.ethz.ch/publications/podc08SW. pdf > Arkiverad 30 juli 2013 på Wayback Machine
Sekine, K.; Imai, H. & Tani, S. (1995), Beräkna Tutte-polynomet för en graf av måttlig storlek , Proc. 6th International Symposium on Algorithms and Computation (ISAAC 1995) , vol. 1004, Lecture Notes in Computer Science , Springer, sid. 224–233, ISBN 3-540-60573-8 , DOI 10.1007/BFb0015427
Tutte, WT (1984), Graph theory, Encyclopedia of mathematics and applications (Cambridge University Press). - Vol. 21, ISBN 0-521-30241-2
Welsh, DJA & Powell, MB (1967), En övre gräns för en grafs kromatiska tal och dess tillämpning på tidtabellsproblem , The Computer Journal vol 10 (1): 85–86 , DOI 10.1093/comjnl/10.1.85
Wilf, H. S. (1986), Algoritmer och komplexitet , Prentice–Hall
Zhu, William & Thomborson, Clark (2006), Recognition in software watermarking , MCPS '06: Proceedings of the 4th ACM international workshop on Contents protection and security , ACM, sid. 29–36, ISBN 1-59593-499-5 , DOI 10.1145/1178766.1178776