Farvelægningsgrafer

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 26. juni 2019; checks kræver 15 redigeringer .

Graffarvning er en grafteoretisk konstruktion ,et særligt tilfælde af grafmarkering . Ved farvelægning tildeles grafelementer etiketter med visse begrænsninger; disse etiketter omtales traditionelt som "farver". I det enkleste tilfælde kaldes en sådan måde at farve toppen af en graf på, hvor to tilstødende hjørner svarer til forskellige farver, vertexfarvning . På samme måde tildeler kantfarvning en farve til hver kant , så to tilstødende kanter har forskellige farver [1] . Til sidst farvelægges områderne af den plane graf tildeler en farve til hvert område, så ikke to områder, der deler en kant, kan have samme farve.

Vertexfarvning er hovedproblemet ved graffarvning, alle andre problemer i dette område kan reduceres til det. For eksempel er farvningen af en grafs kanter farvningen af hjørnerne på dens linjegraf , og farvningen af regionerne i en plan graf er farvningen af hjørnerne af dens dobbelte graf [1] . Andre graffarveproblemer er dog ofte stillet og løst i den oprindelige indstilling. Grunden til dette er dels, fordi det giver en bedre idé om, hvad der sker, og er mere afslørende, og dels fordi nogle problemer er mere bekvemme at løse på denne måde (for eksempel kantfarvning).

Graffarvning finder anvendelse på mange praktiske områder og ikke kun i teoretiske problemer. Udover de klassiske problemtyper kan der også placeres forskellige begrænsninger på grafen, på den måde, farverne tildeles på, eller på selve farverne. Denne metode bruges for eksempel i det populære Sudoku- puslespil . Der er stadig aktiv forskning på dette område.

Historie

De første resultater blev opnået for plane grafer i kortfarveproblemet. I et forsøg på at farvelægge et kort over Englands amter formulerede Francis Guthrie firefarveproblemet , idet han bemærkede, at fire farver er tilstrækkelige til at farvelægge kortet, så to tilstødende regioner har forskellige farver. Hans bror henviste spørgsmålet til sin matematiklærer, Augustus de Morgan , som nævnte det i sit brev til William Hamilton i 1852. Arthur Cayley rejste dette problem på et møde i London Mathematical Society i 1878. Samme år foreslog Tate den første løsning på dette problem. Han reducerede farvningen af hjørnerne af den originale graf til farvningen af kanterne af den dobbelte graf og foreslog, at dette problem altid har en løsning [2] . I 1880 publicerede Alfred Kempe en artikel, hvori han hævdede, at det var lykkedes ham at fastslå resultatet, og i et årti blev problemet med fire farver anset for løst. For denne præstation blev Kempe valgt til Fellow i Royal Society of London og senere præsident for London Mathematical Society [3] .

I 1890 fandt Heawood en fejl i Kempes bevis. I samme artikel beviste han femfarvesætningen , og viste, at ethvert fladt kort kan farvelægges med højst fem farver. Derved støttede han sig til Kempes ideer. I det næste århundrede blev et stort antal teorier udviklet i et forsøg på at reducere det mindste antal farver. Firefarvesætningen blev endelig bevist i 1977 af forskerne Kenneth Appel og Wolfgang Haken ved hjælp af computeroptælling. Ideen om beviset var stærkt afhængig af ideerne fra Heawood og Kempe og ignorerede de fleste af mellemstudierne [4] . Beviset for firefarvesætningen er et af de første beviser, hvor en computer blev brugt.

I 1912 foreslog George David Birkhoff at bruge det kromatiske polynomium , en vigtig del af algebraisk grafteori, til at studere farveproblemer . Det kromatiske polynomium blev efterfølgende generaliseret af William Tutt ( Tutts polynomium ). Kempe gjorde allerede i 1879 opmærksom på det generelle tilfælde, hvor grafen ikke var plan [5] . Mange resultater af generaliseringer af farveplansgrafer på overflader af højere orden dukkede op i begyndelsen af det 20. århundrede.

I 1960 formulerede Claude Burge den perfekte grafformodning , motiveret af en forestilling fra informationsteorien , nemlig grafkapaciteten nul fejl [6] introduceret af Shannon . Udsagnet forblev ubekræftet i 40 år, indtil det blev bevist som den berømte strenge perfekte grafsætning af matematikerne Chudnovskaya , Robertson , Seymour og Thomas i 2002.

Graffarvning som et algoritmisk problem er blevet undersøgt siden 1970'erne: at bestemme det kromatiske tal er et af Karps 21 NP-komplette problemer (1972). Og på nogenlunde samme tidspunkt blev der udviklet forskellige algoritmer baseret på backtracking og Zykovs rekursive sletning og kontraktion [7] . Siden 1981 er graffarvning blevet brugt til registerallokering i compilere [8] .

Definition og terminologi

Vertex farvning

Når folk taler om farvelægning af grafer, mener de næsten altid at farve deres hjørner, det vil sige at tildele farvemærker til grafens spidser, så to vilkårlige spidser, der har en fælles kant, har forskellige farver. Da loopede grafer ikke kan farves på denne måde, er de udelukket.

Terminologien, hvor etiketterne kaldes farver, kommer fra farvelægningen af politiske kort. Etiketter såsom rød eller blå bruges kun, når antallet af farver er lille, men etiketterne antages normalt at være heltal . $\{1,2,3,...\}$

Farvelægning med farver kaldes -farvning . Det mindste antal farver, der er nødvendigt for at farve en graf , kaldes dens kromatiske tal og skrives ofte som . Nogle gange brugt , da det betegner Euler-karakteristikken . En delmængde af hjørner fremhævet i én farve kaldes en farveklasse , hver sådan klasse danner et uafhængigt sæt . Således er -farvning det samme som at opdele hjørner i uafhængige mængder [1] . $k$ $k$ $G$ $\chi (G)$ $\gamma (G)$ $\chi (G)$ $k$ $k$

Kromatisk tal i forhold til afstanden Gromov-Hausdorff

Lade være en vilkårlig graf med vertex sæt . Vi fastsætter to positive reelle tal , og vi vil betragte det som et metrisk rum, hvor afstandene mellem tilstødende hjørner er lig med , og alle andre afstande, der ikke er nul, er lig med . Betegn ved det metriske rum bestående af punkter adskilt fra hinanden med en afstand . Endelig, for alle to metriske mellemrum og , angiver Gromov-Hausdorff afstanden mellem og . Så holder følgende resultat. $G$ $V$ $a<b\leq 2a$ $V$ $b$ $-en$ ${\displaystyle a\Delta _{m))$ $m$ $-en$ $x$ $Y$ $d_{GH}(X,Y)$ $x$ $Y$

Sætning (A.O. Ivanov, A.A. Tuzhilin) [9] : Lad være det største naturlige tal, for hvilket (hvis sådanne naturlige tal ikke findes, så sætter vi ). Så .

m

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

m=0

\chi (G)=m+1

Kommentar.

Det kromatiske tal er , hvis og kun hvis grafen ikke indeholder nogen kanter. I dette tilfælde gælder lighed ikke for nogen , derfor ved konvention, , hvilket fører til den korrekte lighed . $\chi (G)$ $en$ $G$ $d_{GH}(V,a\Delta _{m})=b$ $m$ $m=0$ $\chi (G)=0+1=1$

Per definition ikke overstiger antallet af elementer i sættet . På den anden side er det let at vise, at for hver , derfor, og dermed . $\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$

Kromatisk polynomium

Et kromatisk polynomium er en funktion , der tæller antallet af t - farver i en graf . Af navnet følger det, at denne funktion for givet er et polynomium afhængigt af t . $P(G,t)$ $G$ $G$

Dette faktum blev opdaget af Birkhoff og Lewis, mens de forsøgte at bevise firefarveformodningen [10] .

For eksempel kan grafen i billedet til højre farvelægges på 12 måder ved hjælp af 3 farver. Det kan i princippet ikke males med to farver. Ved at bruge 4 farver får vi 24+4*12 = 72 farvemuligheder: når du bruger alle 4 farver, er der 4! = 24 korrekte måder ( hver tildeling af 4 farver for enhver graf med 4 hjørner er korrekt); og for hver 3 farver ud af disse 4 er der 12 måder at farve på. Så for grafen i eksemplet vil tabellen med antallet af korrekte farver starte sådan her:

Tilgængelig antal farver	en	2	3	fire	…
Antal måder at farve på	0	0	12	72	…

For grafen i eksemplet og selvfølgelig . $P(G,t)=t(t-1)^{2}(t-2)$ $P(G,4)=72$

Et kromatisk polynomium indeholder mindst lige så meget information om farvelighed som et kromatisk tal. Faktisk er det mindste positive heltal, der ikke er en rod af et kromatisk polynomium. $G$ $\chi$

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

Kromatiske polynomier for nogle grafer

Trekantet $K_{3}$	$t(t-1)(t-2)$
Komplet graf $K_n$	$t(t-1)(t-2)\cdots (t-(n-1))$
træ med ribben $n$	$t(t-1)^{{n}}$
Cyklus $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
Greve af Petersen	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t- 352)$

Kantfarvning

En kantfarvning af en graf betyder at tildele farver til kanter på en sådan måde, at ikke to kanter af samme farve hører til det samme toppunkt. Dette problem svarer til at opdele sættet af ansigter i sæt af uafhængige ansigter . Det mindste antal farver, der kræves til en kantfarvning af en graf, er dens kromatiske indeks eller kantkromatiske tal . $G$ $\chi '(G)$

Samlet farvelægning

Totalfarvning er en type farvning af hjørner og kanter på en graf. Med det menes en sådan tildeling af farver, at hverken tilstødende spidser eller tilstødende kanter eller spidser og kanter, der forbinder dem, har samme farve. Det samlede kromatiske antal af en graf er det mindste antal farver, der er nødvendige for enhver komplet farvning. $\chi ''(G)$ $G$

Egenskaber

Egenskaber for det kromatiske polynomium

Hvis er en tom graf [11] , $G$

P(G,t)=1

Hvis grafen er foreningen af usammenhængende undergrafer og [11] , $G$ $H$ $K$

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

Hvis der er en sløjfe i [11] , $G$

P(G,t)=0

Begrænsninger for kromatisk tal

At tildele forskellige farver til alle hjørner giver altid den korrekte farve, så

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

Den eneste form for grafer, der kan farves i én farve, er nul-grafer .
En komplet graf bestående af hjørner kræver farver. $K_n$ $n$ $\chi (K_{n})=n$
I en optimal farvelægning skal der være mindst én grafkant mellem hver to farveklasser, så [12] $m$

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

Hvis er foreningen af usammenhængende undergrafer og , så $G$ $H$ $K$

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

Hvis den indeholder kliker i størrelsen k , så skal der mindst k farver til for at farve denne klike, med andre ord er det kromatiske tal større end eller lig med kliktallet : $G$

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

For intervalgrafer er denne begrænsning nøjagtig.

Ved firefarvesætningen kan enhver plan graf farves med fire farver.
2-farverbare grafer er todelte grafer , inklusive træer .

En graf er todelt, hvis og kun hvis den ikke indeholder cyklusser med ulige længder [11] .

G

Grådig farvelægning viser, at enhver graf kan farves ved at bruge én farve mere end dens maksimale toppunktsgrad [12] .

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

Komplette grafer har og , cyklusgrafer har og , så for dem er denne begrænsning bedst, i alle andre tilfælde kan begrænsningen forbedres: Brooks' sætning [13] siger, at $\chi (G)=n$ $\Delta(G)=n-1$ $\chi (G)=3$ $\Delta(G)=2$

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

for en sammenhængende, simpel graf, hvis er hverken en komplet graf eller en cyklusgraf.

G

G

Grafer med stort kromatisk tal

Grafer med store kliker har store kromatiske tal, men det modsatte er ikke altid sandt. Grötzsch-grafen er et eksempel på en trekantfri 4-farverbar graf, og dette eksempel kan generaliseres til Mycielski-grafen .

Mychelskis sætning (Alexander Zykov 1949, Jan Mychelski 1955): Der findes grafer uden trekanter med vilkårligt store kromatiske tal.

Fra Brooks' sætning skal grafer med stort kromatisk tal have en høj maksimal toppunktsgrad. En anden lokal tilstand, på grund af hvilken det kromatiske tal kan være stort, er tilstedeværelsen af en stor klike. Men grafens farvebarhed afhænger ikke kun af lokale forhold: en graf med stor omkreds ser lokalt ud som et træ, så alle cyklusser er lange, men dens kromatiske tal er ikke lig med 2:

Erdős sætning : Der er grafer med vilkårlig stor omkreds og kromatisk tal [12] .

Begrænsninger på det kromatiske indeks

En kantfarvning er en farvning af hjørnerne af dens linjegraf . Det er $G$ $L(G)$

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

Desuden [14] ,

Königs sætning : , hvis er todelt.

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

G

Generelt er forbindelsen meget stærkere end Brooks' sætning for vertexfarvning [14] giver :

Vizings teorem: En graf med en maksimal toppunktsgrad har et kantkromatisk tal eller .

\Delta

\Delta

\Delta +1

Andre egenskaber

En graf er k - kromatisk, hvis og kun hvis den har en acyklisk orientering , hvor længden af den længste vej er k . Dette blev bevist i Gallai-Hasse-Roy-Vitaver-sætningen [15] .
For plane grafer svarer vertexfarvning til ingen steder nul flow .
Meget mindre er kendt om uendelige grafer. Nedenfor er to resultater for farvelægning af uendelige grafer.

Hvis alle endelige undergrafer i en uendelig graf er k - kromatiske, så er k - kromatisk også (bevist under antagelsen af det valgte aksiom ). Dette er formuleringen af de Bruijn-Erdős sætning [16] . $G$ $G$
Hvis en graf tillader en komplet n -farvning for nogen , så tillader den en uendelig komplet farvning [17] . $n\geqslant n_{0}$

Åbne spørgsmål

Det kromatiske tal for et plan , hvor to punkter støder op til hinanden, hvis der er en enhedsafstand mellem dem, er ukendt. Det kan være 5, 6 eller 7. Andre åbne spørgsmål om det kromatiske antal grafer omfatter Hadwiger-formodningen , som siger, at enhver graf med kromatisk tal k har en komplet graf med k hjørner som dens mindre , Erdős-Faber-Lovas formodning , som begrænser det kromatiske antal komplette grafer, der har præcis ét fælles toppunkt for hvert par af grafer, og Albertsons formodning om, at blandt k - kromatiske grafer er dem med det mindste antal skæringspunkter fuldstændige .

Da Birkov og Lewis introducerede det kromatiske polynomium i deres forsøg på at løse firefarvesætningen, argumenterede de for, at for plane grafer har polynomiet ingen nuller i domænet . Selvom det er kendt, at et sådant kromatisk polynomium ikke har nogen nuller i domænet , og at deres påstand forbliver ubevist. Det forbliver også et åbent spørgsmål, hvordan man skelner grafer med det samme kromatiske polynomium, og hvordan man bestemmer, at et polynomium er kromatisk. $G$ $P(G,t)$ $[4,\infty )$ $[5,\infty )$ $P(G,4)\neq 0$

Farvelægningsalgoritmer

Polynomiske algoritmer

For en todelt graf beregnes farveproblemet i lineær tid ved brug af bredde-først-søgning . I tilfælde af perfekte grafer kan det kromatiske tal og dets tilsvarende farve findes i polynomiel tid ved hjælp af semibestemt programmering . Præcise formler til at finde det kromatiske tal er kendt for mange klasser af grafer (skove, cyklusser , hjul , akkordgrafer ) og kan også beregnes i polynomisk tid.

Nøjagtige algoritmer

Den udtømmende søgealgoritme for tilfælde af k-farvning betragter alle kombinationer af farvearrangementer i en graf med n hjørner og kontrollerer dem for korrekthed. For at beregne det kromatiske tal og det kromatiske polynomium betragter denne algoritme hver k fra 1 til n. I praksis kan en sådan algoritme kun anvendes på små grafer. $k^{n}$

Ved hjælp af dynamisk programmering og estimering af størrelsen af det største uafhængige sæt kan muligheden for k-farvning i en graf løses i tide [18] . Der kendes hurtigere algoritmer til 3- og 4-farvninger, som kører i tid henholdsvis [19] og [20] . $O(2.445^{n})$ $O(1,3289^{n})$ $O(1,7272^{n})$

Sammentrækning

Vertex contraction er en operation, der laver en graf ud fra en graf ved at identificere toppunkter og fjerne de kanter, der forbinder dem og erstatte dem med et toppunkt , hvor kanterne falder ind i toppunkterne og omdirigeres . Denne operation spiller en vigtig rolle i graffarveanalyse. $G$ $g/uv$ $u$ $v$ $w$ $u$ $v$

Det kromatiske tal opfylder gentagelsesrelationen

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

hvor og er ikke-tilstødende hjørner, er en graf med en tilføjet kant . Nogle algoritmer er baseret på dette forhold og producerer et træ som et resultat, nogle gange kaldet et Zykov-træ. Udførelsestiden afhænger af vertex-valgmetoden og . $u$ $v$ $G+uv$ $UV$ $u$ $v$

Det kromatiske polynomium opfylder gentagelsesrelationen

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

hvor og er tilstødende hjørner, er en graf med kanten fjernet . repræsenterer antallet af mulige korrekte farver på grafen, når hjørnerne og kan have samme eller forskellige farver. Hvis og har forskellige farver, så kan vi overveje en graf, hvor og er tilstødende. Hvis og har de samme farver, kan vi overveje en graf, hvor og er flettet. $u$ $v$ $G-uv$ $UV$ $P(G-uv,t)$ $u$ $v$ $u$ $v$ $u$ $v$ $u$ $v$ $u$ $v$

Ovenstående udtryk fører til en rekursiv procedure kaldet fjern- og kontraktalgoritmen , som har dannet grundlaget for mange graffarvealgoritmer. Køretiden opfylder samme gentagelsesrelation som Fibonacci-tallene , så i værste fald vil algoritmen køre i tid for n hjørner og m kanter [21] . I praksis undgår gren- og bundmetoden og afvisningen af isomorfe grafer nogle rekursive kald, køretiden afhænger af metoden til at vælge et par hjørner. $((1+{\sqrt 5})/2)^{{n+m}}=O(1,6180^{{n+m}})$

Grådig farvelægning

Den grådige algoritme sorterer hjørnerne ,..., og tildeler sekventielt toppunktet den mindste tilgængelige farve, der ikke blev brugt til at farve naboerne blandt ,..., , eller tilføjer en ny. Kvaliteten af den resulterende farve afhænger af den valgte rækkefølge. Der er altid en rækkefølge, der bringer den grådige algoritme til det optimale antal farver. På den anden side kan en grådig algoritme være vilkårligt dårlig; for eksempel kan en krone med n hjørner farves med 2 farver, men der er en rækkefølge af knudepunkter, der resulterer i en grådig farvning af farver. $v_{1}$ $v_{n}$ $v_{i}$ $v_{i}$ $v_{1}$ $v_{{i-1}}$ $\chi (G)$ $n/2$

For en akkordgraf , og for dens specielle tilfælde (såsom en intervalgraf ), kan den grådige farvelægningsalgoritme bruges til at finde den optimale farve i polynomiel tid ved at vælge rækkefølgen af hjørnerne til at være den omvendte af den perfekte elimineringsrækkefølge . Denne algoritme kan anvendes på en bredere klasse af grafer ( helt bestillingsbare grafer ), men at finde en sådan rækkefølge for sådanne grafer er et NP-svært problem.

Hvis hjørnerne er ordnet efter deres grader, bruger den grådige farvealgoritme højst farver, hvilket højst er 1 mere end (her , graden af toppunktet ). Denne heuristiske algoritme kaldes nogle gange den walisiske-Powell-algoritme [22] . En anden algoritme indstiller rækkefølgen dynamisk og vælger det næste toppunkt fra det med de mest tilstødende hjørner af forskellige farver. Mange andre graffarvealgoritmer er baseret på grådige farvelægninger og bruger statiske eller dynamiske toppunktsbestillingsstrategier. $max_{i}min\{d(v_{i})+1,i\}$ $\Delta$ $d(v_{i})$ $v_{i}$

Parallelle og distribuerede algoritmer

Et lignende problem opstår inden for distribuerede algoritmer. Lad os sige, at grafens hjørner er computere, der kan kommunikere med hinanden, hvis de er forbundet med en kant. Målet er, at hver computer selv vælger en "farve", så nabocomputere vælger forskellige farver. Dette problem er tæt forbundet med symmetribrudsproblemet . De mest udviklede probabilistiske algoritmer er hurtigere end deterministiske algoritmer for grafer med en tilstrækkelig stor maksimal grad af hjørner . De hurtigste probabilistiske algoritmer bruger teknikken med flere forsøg [23] . $\Delta$

I symmetriske grafer kan deterministiske distribuerede algoritmer ikke finde den optimale toppunktfarvning. Mere information er nødvendig for at undgå symmetri. Der gøres en standardantagelse, at hver toppunkt i starten har en unik identifikator, for eksempel fra sættet . Det antages med andre ord, at vi får en n -farvning. Opgaven er at reducere antallet af farver fra n til f.eks . Jo flere farver der bruges (f.eks. i stedet for ), jo færre beskedudvekslinger kræves [23] . $\{1,2,...,N\}$ $(\Delta+1)$ $O(\Delta)$ $(\Delta+1)$

En simpel version af den distribuerede grådige algoritme for -farvning kræver kommunikationsrunder i værste fald - information skal muligvis gå fra den ene ende af netværkssiden til den anden. $(\Delta+1)$ $\Theta(n)$

Det enkleste interessante tilfælde er n -cyklussen. Richard Cole og Uzi Vishkin [24] har vist, at der er en distribueret algoritme, der reducerer antallet af farver fra n til , ved kun at bruge én nabomeddelelse. Ved at gentage den samme procedure kan man opnå en n -cyklus 3-farvning i forbindelsesrunder (forudsat at der er givet unikke node identifikatorer). $O(log(n))$ $O(log^{*}(n))$

Funktionen , itereret logaritme , er en ekstremt langsomt voksende funktion, "næsten en konstant". Derfor rejser resultaterne af Cole og Vishkin spørgsmålet om, hvorvidt der er en distribueret n-cyklus 3-farvealgoritme, der kører i konstant tid. Nathan Linial viste, at dette er umuligt: enhver deterministisk distribueret algoritme kræver kommunikationsrunder for at reducere en N -farvning til en 3-farvning i en n-cyklus [25] . $log^{*}$ $\Omega (log^{*}(n))$

Teknikken fra Cole og Vishkin kan også anvendes på en vilkårlig graf med en afgrænset grad af hjørner, i hvilket tilfælde køretiden er [26] . Denne metode er blevet generaliseret til enhedscirkelgrafen af Schneider et al . [27] . $P(\Delta)+O(log^{*}(n))$

Kantfarvningsproblemet er også blevet undersøgt i en distribueret model. Pansonezzi og Rizzi opnåede -farvning for i denne model [28] . Den nedre grænse for distribueret vertexfarvning opnået af Linial er også anvendelig til problemet med distribueret kantfarvning [25] . $(2\Delta -1)$ $O(\Delta +log^{*}(n))$

Decentraliserede algoritmer

Decentraliserede algoritmer kaldes algoritmer, hvor intern meddelelsesoverførsel ikke er tilladt (i modsætning til distribuerede algoritmer , hvor processer udveksler data med hinanden). Der er effektive decentraliserede algoritmer, der med succes klarer opgaven med at farvelægge grafer. Disse algoritmer arbejder ud fra den antagelse, at et toppunkt er i stand til at "føle", at ethvert af dets nabospidser har samme farve som det. Det er med andre ord muligt at definere en lokal konflikt. En sådan betingelse er ret ofte opfyldt i applikationer i den virkelige verden - for eksempel, når der transmitteres data over en trådløs kanal, har en sendestation som regel evnen til at opdage, at en anden station forsøger at transmittere samtidigt på den samme kanal. Evnen til at opnå sådan information er tilstrækkelig til, at algoritmer baseret på indlæringsautomater korrekt kan løse graffarveproblemet [29] [30] med sandsynlighed en .

Beregningsmæssig kompleksitet

Farvelægning af grafer er en beregningsmæssigt vanskelig opgave. At finde ud af om en graf kan k - farves for en given k er et NP-komplet problem, bortset fra tilfældene k = 1 og k = 2. Især problemet med at beregne det kromatiske tal er NP-hårdt [31] . 3-farveproblemet er NP-komplet, selv for tilfældet med en plan graf af grad 4 [32] .

Det er også et NP-hårdt problem at farve en 3-farverbar graf med 4 farver [33] og en k -farverbar graf for tilstrækkeligt store værdier af k [34] . $k^{{log(k)/25}}$

At beregne koefficienterne for et kromatisk polynomium er et #P-hårdt problem. Det er blevet bevist, at der ikke er nogen FPRAS- algoritme til at beregne det kromatiske polynomium for et hvilket som helst rationelt tal k ≥ 1,5 bortset fra k = 2, medmindre NP = RP [35] .

Ansøgning

Planlægning

Vertexfarvning modellerer mange planlægningsproblemer [36] . I sin enkleste indstilling bør et givet sæt jobs fordeles over tidsintervaller, idet hvert sådant job optager et segment. De kan udføres i en hvilken som helst rækkefølge, men de to opgaver kan komme i konflikt i den forstand, at de ikke kan udføres på samme tid, fordi de for eksempel bruger fælles ressourcer. Den tilsvarende graf indeholder et toppunkt for hvert job og en kant for hvert modstridende par. Det kromatiske tal på den konstruerede graf er minimumstiden til at fuldføre alle opgaver uden konflikter.

Detaljerne i planlægningsproblemet bestemmer grafens struktur. For eksempel, når der er en opdeling af fly i flyvninger, er den resulterende konfliktgraf en intervalgraf , så farveproblemet kan løses effektivt. Ved fordeling af radiofrekvenser opnås en graf over enhedskonfliktcirkler , og for et sådant problem er der en 3-tilnærmelsesalgoritme .

Registertildeling

En compiler er et computerprogram, der oversætter et computersprog til et andet. For at forbedre udførelsestiden for den resulterende kode er en af kompilatoroptimeringsteknikkerne registerallokering , hvor de hyppigst anvendte variabler i det kompilerede program er lagret i højhastighedsprocessorregistre . Ideelt set lagres variabler i registre, så de alle er i registre på det tidspunkt, de bruges.

Standardtilgangen til dette problem er at reducere det til et graffarveproblem [8] . Compileren bygger en interferensgraf , hvor toppunkter svarer til variabler, og en kant forbinder to af dem, hvis de er nødvendige på samme tid. Hvis denne graf er k -kromatisk, kan variablerne lagres i k registre.

Digitale vandmærker

Teknologien til digitale vandmærker ( eng. digital watermarking ) giver dig mulighed for at overføre nogle skjulte beskeder sammen med data (det være sig mediefiler , eksekverbare filer og andre) (" vandmærke ", vandmærke ). En sådan skjult besked kan bruges i copyright-beskyttelse til at identificere ejeren af dataene.

Dette er vigtigt, for eksempel for at fastslå kilden til deres ulovlige distribution. Eller for at bekræfte rettighederne til data, for eksempel - softwaresystemer på en chip ( system-on-chip ).

Meddelelsen kan også indkodes i den måde, registre er allokeret på. En sådan teknik blev foreslået af Qu og Potkonjak [37] (hvilket er grunden til, at den undertiden kaldes QP-algoritmen).

Den består af følgende: lad være inkompatibilitetsgrafen (interferensgraf) af distributionen af processorregistre, som blev nævnt ovenfor. Dens farvning bruges i programmet - desuden bruges den på en sådan måde, at det er tilladt at ændre indholdet af grafen med en lille stigning i dens kromatiske tal . Det viser sig, at det er muligt at indkode en besked i et softwareprodukt ved hjælp af graffarvning , det vil sige distribution af registre. $G$ $G$

Du kan udtrække denne meddelelse ved at sammenligne fordelingen af registre med den originale farve; [38] der er også måder at verificere, om en besked blev kodet i programmet uden at bruge den originale.

Efterfølgende udviklede og forfinede forskellige forfattere Qu og Potkonjaks ideer [39] . [38] [40]

Andre anvendelser

Graffarveproblemet er blevet stillet i mange andre applikationer, inklusive mønstermatching .

At løse et Sudoku -puslespil kan opfattes som at færdiggøre en 9-farvet farvning af en given graf med 81 hjørner.

Noter

↑ 1 2 3 ( Molloy & Reed 2002 , De grundlæggende definitioner )
↑ ( Donets & Shor 1982 , Historisk baggrund )
↑ ( Kubale 2004 , History of graph coloring )
↑ ( van Lint & Wilson 2001 , kap. 33)
↑ ( Jensen & Toft 1995 , s. 2)
↑ CE Shannon, "Nul-fejlkapaciteten af en støjende kanal," IEEE Trans. Information Theory , pp. 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 > Arkiveret 29. juli 2019 på Wayback Machine
↑ ( Birkhoff & Lewis 1946 )
↑ 1 2 3 4 ( Tutte 1984 , kromatisk polynomium )
↑ 1 2 3 ( Diestel 2005 , Farvede hjørner )
↑ ( Brooks & Tutte 1941 )
↑ 1 2 ( Diestel 2005 , Farvelægningskanter )
↑ ( 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 også ( Cormen, Leiserson & Rivest 1990 , afsnit 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 )
↑ ( Colberg, 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, s. 5-7
Zykov, A. A. (1949), Om nogle egenskaber ved lineære komplekser , Mat. Lør. T. 24(66) (2): 163–188 , < http://mi.mathnet.ru/eng/msb5974 >
Beigel, R. & Eppstein, D. (2005), 3-farvning i tid O(1.3289 n ) , Journal of Algorithms bind 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), Nye metoder til at farve toppen af en graf , Communications of the ACM bind 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 bind 37 (2): 194–197 , DOI 10.1017/S030500410002168X
N. G. de Bruijn, P. Erdős . Et farveproblem for uendelige grafer og et problem i relationsteorien (engelsk) // Nederl. Akad. Wetensch. Proc. Ser. A. - 1951. - T. 54 . - S. 371-373 . (= Indag. Math. 13 )
Byskov, JM (2004), Optælling af maksimale uafhængige sæt med anvendelser til graffarvning , 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. udgave), 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), Registerallokering & spild via graffarvning , Proc. 1982 SIGPLAN Symposium on Compiler Construction , s. 98–105, ISBN 0-89791-074-5 , DOI 10.1145/800230.806984
Cole, R. & Vishkin, U. (1986), Deterministisk møntkastning med applikationer til optimal parallellisterangering , Information and Control bind 70 (1): 32–53 , DOI 10.1016/S0019-9958(86)80023-7
Dailey, D.P. (1980), Unik af farvebarhed og farvebarhed af plane 4-regulære grafer er NP-komplet , Discrete Mathematics bind 30 (3): 289-293 , DOI 10.1016/0012-365X(860-80230)9023
Diestel, R. (2005), Graph theory , < http://www.math.ubc.ca/~solymosi/2007/443/GraphTheoryIII.pdf > Arkiveret 25. november 2014 på Wayback Machine
Duffy, K.; O'Connell, N. & Sapozhnikov, A. (2008), Kompleksitetsanalyse af en decentraliseret graffarvealgoritme , Information Processing Letters bind 107: 60–63, doi : 10.1016/j.ipl.2008.01.002 , < http: //www.hamilton.ie/ken_duffy/Downloads/cfl.pdf >
Fawcett, BW (1978), Om uendelig fuld farvelægning af grafer, Can. J Math. T. XXX: 455-457
Fomin, FV; Gaspers, S. & Saurabh, S. (2007), Forbedrede nøjagtige algoritmer til tælling af 3- og 4-farver , Proc. 13th Annual International Conference, COCOON 2007 , vol. 4598, Lecture Notes in Computer Science , Springer, s. 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 bind 206 (7): 908–929 , DOI 10.1016/j.ic.2008.04.003
Goldberg, A.V .; Plotkin, SA & Shannon, GE (1988), Parallel symmetri-breaking in sparse graphs , SIAM Journal on Discrete Mathematics bind 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 , s. 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 bind 108: 35-53 , DOI 10.1017/S0305004100068936
Jensen, Tommy R. & Toft, Bjarne (1995), Graph Coloring Problemer , John Wiley & Sons, ISBN 0-471-02865-7
Khot, S. (2001), Forbedrede utilnærmelighedsresultater for MaxClique, kromatisk tal og omtrentlig graffarvning , Proc. 42. årlige symposium om grundlaget for datalogi , s. 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 , s. 138-144, ISBN 978-1-60558-606-9
Lawler, EL (1976), En note om kompleksiteten af det kromatiske talproblem , Information Processing Letters bind 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 bind 21 (1): 193–201 , DOI 10.1137/0221015
van Lint, JH & Wilson, R.M. (2001), A Course in Combinatorics (2. udgave), 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), Graffarveproblemer og deres anvendelser i planlægning, Periodica Polytechnica, Electrical Engineering , vol. 48, s. 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 , s. 274-293 , DOI 10.1007/b96249

Nešetřil, Jaroslav & Ossona de Mendez, Patrice (2012), Sætning 3.13 , Sparsity: Graphs, Structures, and Algorithms , vol. 28, Algorithms and Combinatorics, Heidelberg: Springer, s. 42, ISBN 978-3-642-27874-7 , DOI 10.1007/978-3-642-27875-4 .
Panconesi, Alessandro & Rizzi, Romeo (2001), Nogle simple distribuerede algoritmer til sparsomme netværk , Distributed Computing (Berlin, New York: Springer-Verlag ). — V. 14 (2): 97–100, ISSN 0178-2770 , DOI 10.1007/PL00008932
Panconesi, A. & Srinivasan, A. (1996), Om kompleksiteten af distribueret netværksnedbrydning, Journal of Algorithms , vol. tyve
Qu, Gang & Potkonjak, Miodrag (1998), Analyse af vandmærketeknikker til graffarveproblem , ICCAD , s. 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 > Arkiveret 30. juli 2013 kl. Wayback- maskinen
Schneider, J. (2008), A log-star distributed maximum independent set algoritme for growth-bounded graphs , Proceedings of the Symposium on Principles of Distributed Computing , < http://www.dcg.ethz.ch/publications/podc08SW. pdf > Arkiveret 30. juli 2013 på Wayback Machine
Sekine, K.; Imai, H. & Tani, S. (1995), Beregning af Tutte-polynomiet for en graf af moderat størrelse , Proc. 6th International Symposium on Algorithms and Computation (ISAAC 1995) , vol. 1004, Lecture Notes in Computer Science , Springer, s. 224–233, ISBN 3-540-60573-8 , DOI 10.1007/BFb0015427
Tutte, WT (1984), Graph theory, Encyclopedia of mathematics and applications (Cambridge University Press). - bind 21, ISBN 0-521-30241-2
Welsh, DJA & Powell, MB (1967), En øvre grænse for en grafs kromatiske tal og dens anvendelse på tidsplanlægningsproblemer , The Computer Journal bind 10 (1): 85–86 , DOI 10.1093/comjnl/10.1.85
Wilf, H. S. (1986), Algoritmer og kompleksitet , 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, s. 29–36, ISBN 1-59593-499-5 , DOI 10.1145/1178766.1178776