Ensartet farve

Ensartet farvning  er tildelingen af ​​farver til hjørnerne af en urettet graf på en sådan måde, at:

Det vil sige, at opdeling af hjørnerne i forskellige farver er så ensartet som muligt. For eksempel vil det være en ensartet farve at give hvert hjørne en anden farve, men vil typisk bruge mange flere farver end nødvendigt for en optimal ensartet farve. En tilsvarende måde at definere en ensartet farve på er at indlejre en given graf som en undergraf i en Turan-graf med det samme sæt af hjørner. Der er to slags kromatiske tal forbundet med ensartet farvning [1] . Det ensartede kromatiske tal for en graf G  er det mindste tal k , således at grafen G har en ensartet farve med k farver. Imidlertid har grafen G muligvis ikke ensartede farver for nogle større sæt af farver. Den ensartede kromatiske tærskel for en graf G  er det mindste tal k , således at graf G har ensartede farver for et hvilket som helst antal farver større end eller lig med k [2] .

Hajnal-Szemeredy-sætningen , som blev formuleret som en formodning af Pal Erdős [3] og bevist af András Hajnal og Endre Szemeredy [4] , siger, at enhver graf med en maksimal grad har en ensartet farve med farver. Flere relaterede hypoteser forbliver åbne. Der findes også polynomiske tidsalgoritmer til at finde en farve, der svarer til denne grænse [5] , samt algoritmer til at finde optimale farvelægninger for specielle klasser af grafer, men et mere generelt problem med at bestemme, om en vilkårlig graf har en ensartet farvning med en given antal farver er NP-komplet .

Eksempler

Stjernen K 1,5 vist på figuren er en komplet todelt graf , og kan derfor farves med to farver. Den resulterende farvning har dog et toppunkt af én farve og fem toppunkter af en anden farve, og derfor er farvningen ikke ensartet. Det mindste antal farver i en ensartet farvning af denne graf er fire, som vist på figuren - det centrale toppunkt skal tilhøre en klasse med et enkelt toppunkt, så de andre fem toppunkter skal opdeles i mindst tre farver, så hver klasse indeholder højst to hjørner. Mere generelt bemærkede Meyer [6] , at enhver stjerne K 1, n kræver farver for ensartet farvning, og derfor kan det kromatiske tal på en graf højst afvige fra dens kromatiske ensartede tal med n /4 gange. Da K 1,5 har en maksimal grad på fem, er antallet af farver garanteret af Hajnal-Szemeredi-sætningen seks, hvilket opnås ved at tildele en anden farve til hvert toppunkt.

Et andet interessant fænomen viser en anden komplet todelt graf, . Denne graf har en ensartet 2-farve defineret af dens todelte. Den har dog ikke en ensartet (2 n  + 1)-farvning - enhver ensartet opdeling af knudepunkter i dette antal farver skal have præcis to spidser pr. farve, men de to dele af en todelt graf kan ikke parres, fordi de indeholde et ulige antal hjørner. Derfor er den ensartede kromatiske tærskel for denne graf , hvilket er meget større end dens ensartede kromatiske tal, som er to.

Hainal-Semeredis sætning

Brooks' teorem siger, at enhver forbundet graf med maksimal grad er -farverbar med to undtagelser ( komplette grafer og ulige cyklusser). Denne farvning kan dog generelt være langt fra ensartet. Pal Erdős [3] formodede, at en ensartet farvning er mulig med kun én komplementær farve - enhver graf med maksimal grad har en ensartet farve med farver. Etuiet er ligetil (enhver kombination af stier og løkker kan farves ensartet med tre-farvede gentagne mønstre, med små justeringer for lukkede løkker). Sagen blev afgjort af Corradi og Hainal [7] . Den komplette formodning blev bevist af Hajnal og Semeredi [4] og er nu kendt som Hajnal-Szemeredis sætning. Deres originale bevis var langt og kompliceret. Et enklere bevis blev givet af Kirsted og Kostochka [8] . En polynomisk tidsalgoritme til at finde ensartede farver med dette antal farver blev beskrevet af Kiersted og Kostochka. De tilskriver Marcelo Midlarz og Endre Szemeredi en anden, tidligere udviklet, upubliceret polynomiel tidsalgoritme. Kiersted og Kostochka annoncerede også en stærkere version af sætningen om, at der eksisterer en ensartet k -farvning, hvis graderne af to tilstødende hjørner højst summerer til , men beviset blev aldrig offentliggjort.

Meyer [6] formodede i form af Brooks' ensartede farvesætning, at enhver forbundet graf med maksimal grad har en ensartet farve med eller færre farver, bortset fra komplette grafer og ulige cyklusser. En stærkere version af formodningen siger, at hver sådan graf har en ensartet farve med nøjagtige farver, med den yderligere undtagelse af en komplet todelt graf , hvor begge dele har det samme ulige antal hjørner [1] .

Seymour [9] foreslog en styrkelse af Hajnal-Szemeredi-sætningen, som også inkluderer Diracs sætning om, at tætte grafer er Hamiltonske  - han formodede, at hvis et hvilket som helst toppunkt i en graf med n toppunkter har mindst naboer, så indeholder grafen som en undergraf graf dannet ved at forbinde toppunkter, der højst er k skridt væk i en n -cyklus. Tilfældet k  = 1 er Diracs egen sætning. Hajnal-Szemeredi-sætningen kan tilsidesættes af denne hypotese ved at anvende hypotesen for store værdier af k til komplementet af grafen og bruge kontinuerlige sekvenser af hjørner fra n -cyklussen som farveklasser . Seymours formodning er blevet bevist for grafer, hvor n er stor nok sammenlignet med k [10] . Beviset bruger nogle dybe midler, herunder selve Hajnal-Szemeredi-sætningen.

En anden generalisering af Haynal-Szemeredi-sætningen er Bollobash-Eldridge-Katlin-hypotesen (eller kort sagt BEC-hypotesen) [11] . Den siger, at hvis G 1 og G 2 er n -vertex- grafer med henholdsvis maksimal grad og , og hvis , så kan G 1 og G 2 pakkes. Det vil sige, G 1 og G 2 kan repræsenteres på det samme sæt af n hjørner uden fælles kanter. Hajnal-Szemeredi-sætningen er et specialtilfælde af formodningen, hvor G 2 er foreningen af ​​usammenhængende kliker . Catlin [12] giver en lignende, men stærkere tilstand på og under hvilken en sådan pakning garanteres at eksistere.

Særlige tilfælde af grafer

For ethvert træ med maksimal grad overstiger det ensartede kromatiske tal ikke

[6]

med worst case på en stjerne. De fleste træer har dog et meget mindre ensartet kromatisk tal - hvis et træ med n hjørner har , så har det en ensartet farve med kun tre farver [13] . Furmanchik [1] studerede det ensartede kromatiske antal produkter af grafer .

Beregningsmæssig kompleksitet

Problemet med at finde ensartede farver med så få farver som muligt (under Hainal-Semeredi-grænsen) blev også undersøgt. En direkte reduktion fra en graffarvning til en ensartet farve kan bevises ved at tilføje nok isolerede hjørner til grafen, hvilket viser, at test af, om en graf har en ensartet farve med et givet antal farver (større end to) er NP-komplet . Problemet bliver dog mere interessant, når det er begrænset til en speciel klasse af grafer eller i form af parameteriseret kompleksitet . Bodlander og Fomin [14] viste, at givet en graf G og et antal farver c , kan man kontrollere, om G kan være ensartet c -farvet i O( n O( t ) ) tid, hvor t er  træets bredde af G. Især kan ensartet farvning løses optimalt i polynomiel tid for træer (som det er kendt takket være Chen og Lee [15] ) og ydre planære grafer . Der er også en polynomisk tidsalgoritme til ensartet farvning af opdelte grafer [16] . Fellowes, Fomin, Lokshtanov et al. [17] beviste imidlertid, at når træbredden er en algoritmeparameter, er problemet W[1]-hårdt. Det er således usandsynligt, at der er en polynomisk tidsalgoritme, der er uafhængig af denne parameter, eller endda at afhængigheden af ​​parameteren kan sættes i parentes af eksponenten i køretidsformlen.

Ansøgninger

En af grundene til at overveje ensartet farvning blev foreslået af Meyer [6] i forbindelse med planlægningsproblemer . I denne applikation repræsenterer grafens hjørner et sæt opgaver, der skal udføres, og kanterne forbinder to opgaver, der ikke kan udføres på samme tid. Farvelægningen af ​​denne graf repræsenterer opdelingen af ​​opgaver i delmængder, der kan udføres samtidigt. Så svarer antallet af farver i farvelægningen til det antal trin, der kræves for at fuldføre opgaven fuldstændigt. I henhold til belastningsbalanceringskonventioner er det ønskeligt at udføre det samme eller næsten det samme antal opgaver i hvert trin, og denne afbalancering er præcis, hvad ensartet farvning giver . Furmanchik [1] nævnte en specifik anvendelse af denne type skemalægningsproblemer, nemlig fordelingen af ​​universitetskurser efter akademiske timer, således at kurserne fordeles ligeligt over de tilgængelige tidsvinduer, for at undgå at tildele uforenelige kursuspar til samme tidspunkt.

Hajnal-Szemeredi-sætningen er også blevet brugt til at begrænse variansen af ​​summer af stokastiske variable med afgrænset afhængighed [18] [19] . Hvis (som i tilstanden af ​​det lokale Lovas-lemma ) hver variabel højst afhænger af andre, kan ensartet farvelægning af afhængighedsgrafen bruges til at opdele variablerne i uafhængige delmængder, inden for hvilke Chernoff-grænser kan beregnes , hvilket vil give bedre grænser for variansen end hvis opdelt på en ikke-ensartet måde.

Noter

  1. ↑ 1 2 3 4 Furmańczyk, 2006 .
  2. ↑ Bemærk, at når k er større end antallet af hjørner i grafen, er der altid en ensartet farvning med k farver, hvor alle farveklasser har nul eller et toppunkt pr. klasse, således at enhver graf har en ensartet kromatisk tærskel.
  3. ↑ 12 Erdős , 1964 .
  4. ↑ 1 2 Hajnal, Szemerédi, 1970 .
  5. ↑ Kierstead, Kostochka, Mydlarz, Szemerédi, 2010 , s. 217-224.
  6. ↑ 1 2 3 4 Meyer, 1973 .
  7. ↑ Corrádi, Hajnal, 1963 .
  8. ↑ Kierstead, Kostochka, 2008 .
  9. ↑ Seymour, 1974 .
  10. ↑ Komlós, Sárközy, Szemerédi, 1998 .
  11. ↑ Bollobás, Eldridge, 1978 .
  12. ↑ Catlin, 1974 .
  13. ↑ Bollobás, Guy, 1983 .
  14. ↑ Bodlaender, Fomin, 2005 .
  15. ↑ Chen, Lih, 1994 .
  16. ↑ Chen, Ko, Lih, 1996 .
  17. ↑ Fellows, Fomin, Lokshtanov, 2007 .
  18. ↑ Pemmaraju, 2001 .
  19. ↑ Janson, Ruciński, 2002 .

Litteratur

Links