Graffarvning



Den information, vi har kunnet samle om Graffarvning, er blevet omhyggeligt gennemgået og struktureret for at gøre den så nyttig som muligt. Du er sandsynligvis kommet her for at finde ud af mere om Graffarvning. På internettet er det let at fare vild i et virvar af sider, der taler om Graffarvning, men som ikke giver dig det, du gerne vil vide om Graffarvning. Vi håber, at du vil fortælle os i kommentarerne, om du kan lide det, du har læst om Graffarvning nedenfor. Hvis de oplysninger om Graffarvning, som vi giver dig, ikke er hvad du søgte, så lad os det vide, så vi kan forbedre denne hjemmeside dagligt.

.

I grafteori , graf farvning består i at tildele en farve til hver af sine knudepunkter, således at to toppunkter forbundet med en kant er af en anden farve. Vi prøver ofte at bruge det mindste antal farver, kaldet det kromatiske nummer . Den brøkdelte farve er at søge ikke en, men flere farver pr. Toppunkt og tilknytte omkostningerne til hver. Anvendelsesområdet for graffarvning dækker især problemet med allokering af frekvenser i telekommunikation, design af elektroniske chips eller tildeling af registre i kompilering .

Historisk

De første resultater af graffarvning vedrører næsten udelukkende plane grafer  : det var da et spørgsmål om farvekort. I forsøget på at farve et kort over de amter i England , Francis Guthrie postulerede den fire-farve formodninger . Han bemærkede, at det kun havde brug for fire farver for to amter med en fælles grænse for at være forskellige farver. Guthries bror sendte spørgsmålet videre til sin matematikprofessor, Augustus de Morgan fra University College London . De Morgan nævnte dette problem i et brev til William Rowan Hamilton i 1852. Arthur Cayley rejste dette spørgsmål ved et London Mathematical Society kollokvium i 1879. Samme år offentliggjorde Alfred Kempe, hvad han hævdede at være en demonstration af det. årti troede man, at problemet med fire farver var løst. Kempe blev valgt til stipendiat i Royal Society og blev derefter præsident for London Mathematical Society .

I 1890 påpegede Percy John Heawood , at Kempes demonstration var falsk. Hvad ham angår, viste han sætningen af ​​de fem farver  (in) ved at tage ideer op fra Kempe. Mange værker blev offentliggjort i det følgende århundrede for at reducere antallet af farver til fire, indtil den endelige demonstration af Kenneth Appel og Wolfgang Haken . Beviserne genbrugte Heawood og Kempes ideer og næppe nogen efterfølgende udvikling. Det er også det første store bevis, der massivt bruger computeren.

Definition (kromatisk tal)

Begrebet farve er kun defineret til enkle grafer uden løkker og uden flere kanter.

Givet en simpel graf G = (S, A) , er en stald af G en delmængde af S, hvis hjørner er to-to-to ikke-tilstødende, og en k-farvning af G er en deling af S i k stabil.

En k -farvning af G er en funktion c fra S til {1,2, ..., k}, således at for ethvert par tilstødende hjørner u og v af S , c (u) ≠ c (v) .

Vi foretrækker generelt den definition, vi gav først, fordi vi for de fleste spørgsmål relateret til begrebet farve ikke ønsker at skelne mellem de farver, der kun adskiller sig ved permutation af farveindekserne (hvilket er tilfældet for det centrale problem, der er knyttet til farve, det at bestemme det mindste antal farver i en farve på G , det vil sige dets kromatiske antal ). For eksempel, hvis G består af to hjørner u og v og en kant, der forbinder dem, så fungerer de to f og g med f (u) = 1 , f (v) = 2 og g (u) = 2 , g ( v) = 1 er forskellige farver til den anden definition, men ækvivalente for den første.

I sine forskellige bøger (på fransk eller engelsk), Berge bruges begge vurderinger og til at betegne den kromatiske antal G . I dag vedtager de fleste værker symbolet (mens det snarere vedrører en invariant relateret til begrebet cyklus).

Endelig taler vi i visse sammenhænge også om farvning for at betegne en funktion, der forbinder en farve med hjørnerne i en graf, men tilfredsstiller andre egenskaber (f.eks. I forbindelse med optimering af kodegenerering på en maskine, der omfatter et stort antal registre).

Egenskaber og formodninger

Kromatisk antal og maksimal grad

Brooks 'sætning siger, at man kan farve en tilsluttet graf ved hjælp af højst Δ farver, hvor Δ er den maksimale grad af grafen, bortset fra tilfælde af den komplette graf og den ulige længdecyklusgraf, hvor det er nødvendigt Δ + 1 farver.

Det faktum, at grafen højst kan farves med Δ + 1 farver, vises meget let. Faktisk er det tilstrækkeligt at farve hjørnerne en efter en i en hvilken som helst rækkefølge: hver gang du farverer et toppunkt, skal du vælge en anden farve end alle de, der allerede er brugt til naboerne til dette toppunkt, som allerede er farvet; da et toppunkt højst har Δ naboer, er Δ + 1 farver altid tilstrækkelige.

Fortjenesten ved Brooks 'sætning er derfor at reducere dette antal farver, der er nødvendigt til Δ for de fleste grafer.

Hadwiger-formodning

Den mest berømte formodning er utvivlsomt den for Hadwiger i 1943. Hadwiger-antallet af en graf G er lig med det største heltal k, således at G har en mindre isomorf til den komplette graf med k- hjørner. Hadwiger-formodningen er så, at:

For enhver graf uden sløjfe G , den kromatiske antal G er mindre end eller lig med antallet af Hadwiger af G .

Den Hadwiger formodninger er bevist for grafer med en Hadwiger antal på højst 6; beviset er baseret på sætningen med fire farver .

Hadwiger - Nelson problem

Den Golomb graf er unit-afstand og kræver 4 farver til at farve sine knudepunkter.

Bestem det kromatiske tal på grafen, hvis hjørner er punkterne i (euklidisk) plan, og således at to hjørner er tilstødende, hvis afstanden mellem dem er 1.

En anden formulering er: Hvad er det mindste antal farver, der kræves for at kunne farve en hvilken som helst afstandsenhedsgraf  

Ifølge Tommy Jensen og Bjarne Toft blev problemet først stillet af Edward Nelson i 1950 og først udgivet af Gardner i 1960. Hugo Hadwiger havde imidlertid offentliggjort et resultat relateret til problemet allerede i 1945.

I øjeblikket er alt, hvad vi kan sige, at dette tal er mellem 5 og 7. Den mest kendte nedre grænse har længe været 4, inden den blev forbedret i 2018 af Aubrey de Gray , der byggede en graf for afstandsenhed, der krævede 5 farver. Den øvre grænse opnås ved en sekskantet tessellation af flyet. Nogle resultater vedrørende denne formodning afhænger af det valgte aksiom .

Grünbaum formodning

“For ethvert m> 1 og n> 2 findes der en n- regelmæssig graf med kromatisk tal m og maskecelle mindst n . "

Resultatet er trivielt for n = 2 og m = 2.3, men for m> 3 kendes kun få grafer, der illustrerer formodningen. Den Chvatal graf er en af dem.

Lavere grænser for

Hvis en graf "G" indeholder en klikstørrelse "k" (et sæt "k" -hjørner forbundet to og to), kræver disse hjørner "k" forskellige farver, hvilket betyder, at (hvor angiver størrelsen på det største klik " G "). Imidlertid er denne nedre grænse også NP-vanskelig at opnå. I 1979 introducerede en artikel af László Lovász en mængde forbundet med hver graf: beregnes i polynomisk tid og verificering af følgende sandwich-sætning (med betegnelse af den komplementære graf): Ligestilling finder sted for blandt andet perfekte grafer, hvilket gør det muligt beregne deres kromatiske antal.

En anden nedre grænse er det brækkede kromatiske tal , altid større end , NP-svært at beregne ved at generere kolonner (det er et lineært program, hvis variabler indekseres af grafens stabile, i eksponentielt tal).

Eksempler på anvendelse

Telekommunikation

Nogle telekommunikationsnet består af sendere, der hver sender på en bestemt frekvens. Når to sendere er for tætte, kan de ikke tildeles den samme frekvens på grund af interferens (medmindre muligvis et bjerg adskiller dem).

Vi forbinder en graf med netværket - hvert toppunkt er en emitter, og hver kant specificerer, at vi ikke vil allokere den samme frekvens til de to emittere, der svarer til dens to ender - og dermed bestemme en allokering, der kan udføres med et minimum af frekvenser (inklusive driftstilladelsen kan medføre betydelige omkostninger). Dette problem er et specielt tilfælde af graffarveproblemet.

Lad os specificere, at de teknologiske begrænsninger afhænger af den geografiske lettelse, man kan ikke antage, at en graf opnået fra telekommunikationsnetværk er en diskgraf .

For visse frekvensallokeringsproblemer kan det være nødvendigt at allokere flere frekvenser til den samme sender; at indføre en minimumsforskel mellem de frekvenser, der er allokeret til to nærliggende sendere (og ikke længere kun, at de er forskellige); ved at kræve at tildele en sender en frekvens, der kun er valgt blandt en delmængde af de tilgængelige frekvenser ... Farvningen fremstår derefter som et specielt tilfælde af disse varianter.

Uforligelighedsproblemer

  • Organiser en eksamen i henhold til de emner, som hver studerende skal bestå. Hvordan stilles flere tests parallelt uden at skade en kandidat
  • Optimer brugen af ​​arbejdsmaskiner. Hvordan placeres parallelle produktioner ved hjælp af flere maskiner
  • Hvordan får man mennesker eller dyr til at leve sammen under hensyntagen til deres uforenelighed
  • At løse Sudoku kan reduceres til et graffarveproblem.

Algoritmiske egenskaber

Algoritmiske problemer

To algoritmiske farveproblemer er:

  • beslutningsproblem  : givet G , en graf og k et heltal, er der en gyldig farve på G ved hjælp af k farver
  • optimeringsproblem: givet G , hvad er dets kromatiske tal

NP-fuldstændighed

For ethvert k større end 2 er farveproblemet med k farver NP-komplet.

Bestemmelse af det kromatiske tal i en graf er generelt et NP-vanskeligt problem . Således medmindre P = NP , er der ingen polynomalgoritme, der bestemmer det kromatiske antal af en vilkårlig graf. Dette problem er et optimeringsproblem, der stiller følgende spørgsmål: lad G være en given graf, hvad er det mindste antal farver, der er nødvendigt for at have en gyldig farve på G

Det tilknyttede tilnærmelsesproblem er også NP-komplet, uanset det ønskede tilnærmelsesforhold. Med andre ord er problemet ikke i APX-klassen .

Polynomiske tilfælde

Der er polynomiske algoritmer, hvis vi begrænser os til klasser af grafer.

  • Hvis k er sat til 2 , består beslutningsproblemet i at afgøre, om G er toparts eller ej. Dette kan gøres ved at kontrollere, at der ikke er nogen ulige cyklus med en breddevej .
  • For intervalgrafer løser vi problemet i lineær tid med en grådig algoritme .
  • Mere generelt er triangulerede grafer (intervalgrafer) problemet løst i lineær tid .
  • Trekantede grafer er perfekte grafer . Et meget vanskeligere resultat (fra László Lovász et al. ) Etablerer (ved at udvikle en hel teori), at vi i polynomisk tid kan bestemme det kromatiske antal af enhver perfekt graf (for en definition se sætning om perfekte grafer ) .
  • for plane grafer gør sætningen af ​​de fire farver det muligt at bestemme eksistensen af ​​en k-farvning, så snart k er større end 4 (i konstant tid, fordi der altid eksisterer en). Desuden ved vi, hvordan man finder sådan en 4-farvning i kvadratisk tid . På den anden side forbliver problemet NP-komplet for k = 3 .

Algoritmer

I dette afsnit citerer vi nogle algoritmer (af eksponentiel kompleksitet i almindelighed) lad os citere Zykov-algoritmen (efter Branch and Bound-metoden ).

Heuristik

Problemets betydning har givet anledning til udviklingen af ​​mange problemspecifikke heuristikker , især top-til-top sekventielle farvealgoritmer ( DSATUR , cosinus, maya osv.). Det har også givet anledning til adskillige eksperimenter generelle omtrentlige metoder: meta-heuristik ( simuleret annealing , tabu-forskning ) eller endda genetisk algoritme .

Walisisk og Powell-algoritme

  1. Find graden af ​​hvert toppunkt.
  2. Bestil hjørnerne i faldende grader (i nogle tilfælde flere muligheder).
  3. Tildel en farve til det første toppunkt (A) på listen.
  4. Følg listen ved at tildele den samme farve til det første toppunkt (B), der ikke støder op til (A).
  5. Følg (hvis muligt) listen til det næste toppunkt (C), som ikke støder op til hverken A eller B.
  6. Fortsæt, indtil listen er komplet.
  7. Tag en anden farve til det første toppunkt (D), der endnu ikke er farvet på listen.
  8. Gentag operation 3 til 7.
  9. Fortsæt, indtil du har farvet alle toppe.

Bemærk, at denne metode kan føre til de værst mulige farvestoffer, for eksempel hvis grafen G har strukturen af ​​en krone med n hjørner , er dens kromatiske tal 2 (hvis n er jævn), mens walisisk-Powell i nogle tilfælde giver (ifølge rækkefølgen, hvorpå hjørnerne er arrangeret) en farve, der bruger n / 2 farver! DSATUR-heuristikken undgår dette problem og giver en dårligere farve i værste fald.

DSATUR

DSATUR er en heuristik, der består i at farve hjørnerne efter hinanden ved at stole på en foreløbig sortering af hjørnerne. Prioritet gives til hjørner af høj grad såvel som hjørner, hvis naboer allerede har opnået de mest forskellige farver.

Grådig algoritme

Vi assimilerer farverne til naturlige heltal i de følgende algoritmer. Vi giver os selv en graf .

For alt  :

  1. Vi ser på det sæt farver, der allerede er tildelt naboerne til
  2. Vi udleder det mindste naturlige tal, der ikke hører til dette sæt.
  3. Vi tilskriver denne farve

Således har vi opnå en farvning af , hvilke anvendelser i de fleste farver, med den grad af grafen

Algoritme korrektion

Den grådige algoritme returnerer en farve. Faktisk er alle hjørner farvet. Hvis to hjørner og er naboer, kan vi antage, at det er behandlet før . Algoritmen tildeler farven til , og derefter, når den behandles, vælger algoritmen en farve , der ikke hører til listen over farver, der allerede er brugt til naboer til . Så er forskellig fra .

Farvning bruger i de fleste farver. Faktisk, hvis dette ikke var tilfældet, ville vi have et toppunkt, der ville have en farve større end strengt end .

Så hans naboer ville allerede bruge forskellige farver. Dette topmøde har dog højst naboer, hvilket ville være absurd.

2-farvende algoritme

Vi betragter en graf med to farver.

For hver tilsluttet komponent i giver vi os selv et toppunkt, vi tildeler farven til det, og vi tildeler farven til dets naboer. For hver af sine naboer tildeles farven til sine ufarvede naboer og så videre: Vi krydser således bredden af ​​grafen ved at farve hjørnerne på den måde, der er angivet tidligere.

Algoritme korrektion

2-farvningsalgoritmen returnerer faktisk en farve, hvis inputgrafen er 2-farvende. Faktisk, hvis vi tager 2 nabo-hjørner, blev en af ​​hjørnerne først krydset. Det andet toppunkt farves derfor med den anden farve af algoritmen, og dens farve ændres ikke efterfølgende. Derudover udfører algoritmen en breddeovergange, så alle hjørnerne er farvede.

Wigdersons algoritme

Den Wigderson algoritme er en algoritme tidskompleksitet polynomium, hvilke farver med farve grafer 3-colorable.

Distribueret algoritme

Farvning er et klassisk problem med synkron distribueret beregning. Et bemærkelsesværdigt resultat er den nedre grænse for Nati Linial  : det tager skridt til at lave en 3-farvning af en cykluslængde (selv for en algoritme, der bruger tilfældighed), hvor er den itererede logaritme .

Welsh-Powell Algorithm Python Program

Celle til at køre Python-konsol
  1. #Welsh og Powell algoritme
  2. #importere

import matplotlib.pyplot som plt fra pylab import * fra tidsimport *

  1. #fra import af farver *

t1 = ur ()

  1. #ændre indeks i og j på en liste L

def udveksling (L, i, j):

   x=L[i]
   L[i]=L[j]
   L[j]=x
  1. #liste L i faldende rækkefølge

faldende def (L1, L2):

   for i in range(len(L1)):
       leader1 = L1[i]
       leader2 = i
       for j in range(i+1,len(L1)):            
           if L1[j] > leader1:
               leader1 = L1[j]
               leader2 = j
       echange(L1,i,leader2)
       echange(L2,i,leader2)
   return L2
  1. Topmøde: S
  2. S = [a, b, c, ...]
  3. Graf: G
  4. G = [[a, b], [c, a], [d, c] ...]
  5. Grad: D

def Grad (S, G):

   cpt=[0]*len(S)           
   for k in range(len(S)):
       for i in range(len(G)):
           for j in range(2):
               if G[i][j]==S[k]:
                   cpt[k]+=1
   D=decroissant(cpt,S)
   return D
  1. # hjørner ved siden af ​​hjørnet x

def tilstødende (G, x):

   A=[]                                               
   for i in range(len(G)):
       for j in range(2):
           if G[i][j]==x:
               A+=[G[i][1-j]]
   return A
  1. # ikke tilstødende top

def ikke-tilstødende (A, x):

   for i in range(len(A)):
       if x==A[i]:
           return False
   return True
  1. # L = [Sandt, sandt, ...]

def Ltrue (L):

   for i in range(len(L)):
       if L[i]==False:
           return False
   return True

"" "

  1. #farve

def farve ():

   C=[]
   for i in range(0,478,10):
       C[i]+=[COLORS[i]]
   return C

"" "

  1. #farve

def farve (lx, ly, farve):

   return plt.plot(lx,ly,couleur)  # coordonnée
 
  1. #Ikke farvelægning

def Non_colorier (Dejacolorier, a):

   for i in range(len(Dejacolorier)):
       if Dejacolorier[i]==a:
           return False
   return True
  1. #Først ikke farve

besejrede Premier_non_colorier (Deja_colorier, D):

   res=0
   for i in range(len(D)):
       if Non_colorier(Deja_colorier,D[i]):
           res=D[i]
           break
   return res
  1. #Plot-graf

def plot (G):

   for i in range(len(G)):
       x=array([G[i][0][0],G[i][1][0]])
       y=array([G[i][0][1],G[i][1][1]])
       print(plot(x,y))
  1. #Algoritmer

def algoritme1 (S, G):

   D=Degre(S,G)
   #tracer(G)
   #C=['bo','go','ro','yo']
   #plt.axis([-1, 7, -1, 7])    # [min(x),max(x),min(y),max(y)]
   leader_couleur=[adjacent(G,D[0])]
   Deja_colorier=[]
   cpt1=0
   cpt2=0
   #meme_couleur=C[cpt1]
   L=[True]*len(D)
   while not(len(Deja_colorier)==len(D)) :
       #meme_couleur=C[cpt1]
       #colorie([Premier_non_colorier(Deja_colorier,D)[0]],[Premier_non_colorier(Deja_colorier,D)[1]],meme_couleur) # coordonnée
       leader_couleur=[adjacent(G,Premier_non_colorier(Deja_colorier,D))]
       Deja_colorier.append(Premier_non_colorier(Deja_colorier,D))
       L=[True]*len(D)
       cpt1+=1
       cpt2=0
       for j in range(len(D)):
           if Non_colorier(Deja_colorier,D[j]) :
               for k in range(cpt2+1):
                   L[k]=non_adjacent(leader_couleur[k],D[j])
               if Ltrue(L):
                   #colorie([D[j][0]],[D[j][1]],meme_couleur)
                   Deja_colorier.append(D[j])   
                   cpt2+=1
                   leader_couleur.append(adjacent(G,D[j]))    
   return cpt1

def algoritme2 (S, G):

   D=Degre(S,G)
   tracer(G)
   C=['bo','go','ro','yo','cyano','lawn greeno','indian redo','maroono']
   plt.axis([-1, 7, -1, 7])    # [min(x),max(x),min(y),max(y)]
   leader_couleur=[adjacent(G,D[0])]
   Deja_colorier=[]
   cpt1=0
   cpt2=0
   meme_couleur=C[cpt1]
   L=[True]*len(D)
   while not(len(Deja_colorier)==len(D)) :
       meme_couleur=C[cpt1]
       colorie([Premier_non_colorier(Deja_colorier,D)[0]],[Premier_non_colorier(Deja_colorier,D)[1]],meme_couleur) # coordonnée
       leader_couleur=[adjacent(G,Premier_non_colorier(Deja_colorier,D))]
       Deja_colorier.append(Premier_non_colorier(Deja_colorier,D))
       L=[True]*len(D)
       cpt1+=1
       cpt2=0
       for j in range(len(D)):
           if Non_colorier(Deja_colorier,D[j]) :
               for k in range(cpt2+1):
                   L[k]=non_adjacent(leader_couleur[k],D[j])
               if Ltrue(L):
                   colorie([D[j][0]],[D[j][1]],meme_couleur)
                   Deja_colorier.append(D[j])   
                   cpt2+=1
                   leader_couleur.append(adjacent(G,D[j]))    
   return plt.show()
  1. #Algoritme alle mulige kombinationer af de første n cifre

def kombinationer (S):

   if len(S)==1:
       return [S]
   else:
       res = []
       for i in combinaisons(S[:-1]):
           for j in range(len(S)):
               res += [i[:j] + S[-1:] + i[j:]]
       return res

def new_algo1 (S, G):

   C=combinaisons(S)
   NbCouleurs=[]
   for i in range(len(C)):
       NbCouleurs+=[algorithme1(C[i],G)]
   return min(NbCouleurs)

def new_algo2 (S, G):

   C=combinaisons(S)
   NbCouleurs=[]
   for i in range(len(C)):
       NbCouleurs+=[algorithme1(C[i],G)]
   Indice_Gamma=NbCouleurs.index(min(NbCouleurs))
   return algorithme2(C[Indice_Gamma],G)

def Degre_bis (S, G):

   cpt=[0]*len(S)           
   for k in range(len(S)):
       for i in range(len(G)):
           for j in range(2):
               if G[i][j]==S[k]:
                   cpt[k]+=1
   return cpt

def descending_bis (cpt):

   for i in range(len(cpt)):
       leader1 = cpt[i]
       leader2 = i
       for j in range(i+1,len(cpt)):            
           if cpt[j] > leader1:
               leader1 = cpt[j]
               leader2 = j
       echange(cpt,i,leader2)
   return cpt

def copy_cpt (cpt):

   res=[]
   for x in cpt:
       res+=[x]
   return x
       
a, b, c, d, e, f, g = [0.0], [0.1], [1.1], [2.3], [3.0], [5.2], [6.3]


S = [a, b, c, d, e, f, g]


G = [[a, b], [a, c], [b, c], [b, d], [d, e], [d, f], [d, g], [f, g] ]


new_algo1 (S, G)


new_algo2 (S, G)


t2 = ur ()

Referencer

  1. (in) Mr. Kubale, Historie om graffarvning , i Kubale 2004
  2. van Lint og Wilson 2001 , kap. 33
  3. Claude Berge, Hypergrafier. Combinatorics of finite sets , Bordas, 1987
  4. (i) Neil Robertson , Paul Seymour og Robin Thomas , "  Hadwiger formodning for -fri grafer  " i combinatorica , 14 , 1993, 279-361
  5. (i) Tommy R. Jensen og Bjarne Toft , Graph Farvelægning Problemer , Wiley-Interscience Series i diskret matematik og optimering,, s.  150–152
  6. (i) Martin Gardner , Matematiske spil  " , Scientific American , bd.  203, nr .  4, , s.  180
  7. (in) Hugo Hadwiger , Überdeckung of euklidischen Raumes durch kongruente Mengen  " , Portugal. Matematik.  (in) , vol.  4,, s.  238-242
  8. Aubrey DNJ de Gray , "  Det kromatiske antal af planet er mindst 5  ", arXiv: 1804.02385 [matematik] ,( læs online , hørt 21. april 2018 )
  9. (in) Branko Grünbaum , A Problem in Graph Coloring-  " , Amer. Matematik. Månedligt , vol.  77,, s.  1088-1092
  10. (in) Vertex Coloring  " (adgang til 12. marts 2015 )
  11. David Zuckerman , “  Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number  ”, Theory of Computing , vol.  3, n o  1, , s.  103-128
  12. En bog om emnet: Leonid Barenboim og Michael Elkin , Distribueret graffarve: Fundamentals and Recent Developments , Morgan & Claypool Publishers, coll.  "Syntese forelæsninger om distribueret computingsteori",( ISBN  978-1-62705-018-0 )
  13. Det vandt Dijkstra-prisen for sin forfatter.
  14. Den originale artikel (i) Nathan Linial , Lokalitet i distribuerede grafalgoritmer  " , SIAM Journal on Computing , bind.  21, nr .  1,, s.  193-201.

Bibliografi

Se også

Vi håber, at de oplysninger, vi har indsamlet om Graffarvning, har været nyttige for dig. Hvis det er tilfældet, så glem ikke at anbefale os til dine venner og familie, og husk, at du altid kan kontakte os, hvis du har brug for os. Hvis du på trods af vores bestræbelser mener, at det, vi har leveret om _title, ikke er helt korrekt, eller at vi bør tilføje eller rette noget, vil vi være taknemmelige, hvis du vil give os besked. At give den bedste og mest omfattende information om Graffarvning og ethvert andet emne er essensen af denne hjemmeside; vi er drevet af den samme ånd, som inspirerede skaberne af Encyclopedia Project, og derfor håber vi, at det, du har fundet om Graffarvning på denne hjemmeside, har hjulpet dig med at udvide din viden.

Opiniones de nuestros usuarios

Birte Henriksen

Jeg kan godt lide webstedet, og artiklen om Graffarvning er det, jeg ledte efter

Erling Dahl

Jeg troede, at jeg allerede vidste alt om Graffarvning, men i denne artikel fandt jeg ud af, at nogle af de detaljer, som jeg troede var gode, ikke var så gode. Tak for oplysningerne., Det er altid godt at lære noget

Kristine Andresen

Det er længe siden, at jeg har set en artikel om Graffarvning skrevet på en så didaktisk måde. Jeg kan godt lide det