Grafisk homomorfi

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 14. oktober 2021; checks kræver 2 redigeringer .

En grafhomomorfi er en kortlægning mellem to grafer , der ikke bryder strukturen. Mere specifikt er det en kortlægning mellem et sæt af hjørner af to grafer, der kortlægger tilstødende hjørner til tilstødende.

Homomorfismer generaliserer forskellige forestillinger om graffarver og tillader udtryk for vigtige klasser af begrænsningstilfredshedsproblemer , såsom nogle planlægningsproblemer eller problemer med radiofrekvensallokering [1] . Det faktum, at homomorfismer kan bruges sekventielt, fører til rige algebraiske strukturer - forudbestilling på grafer, fordelingsgitter og kategorier (en for urettede grafer og en for rettede grafer) [2] . Den beregningsmæssige kompleksitet ved at finde en homomorfi mellem givne grafer er generelt uoverkommelig, men der kendes mange specielle tilfælde, når opgaven er gennemførlig i polynomisk tid . Grænserne mellem løselige og uoverstigelige sager ligger i et område med aktiv forskning [3] .

Definitioner

I denne artikel betyder grafer, medmindre andet er angivet, endelige urettede grafer med tilladte sløjfer , men flere (parallelle) kanter er ikke tilladt. En grafhomomorfi [4] [5] [6] : f fra graf til graf , som skrives som $G=(V(G),E(G))$ $H=(V(H),E(H))$

f:G\til H

er en funktion fra V ( G ) til V ( H ), der kortlægger endepunkterne for hver kant fra G til endepunkterne af en kant fra H. Formelt følger det af , for alle par af knudepunkter u , v fra V ( G ). Hvis der er nogen homomorfi fra G til H , så siges grafen G at være homomorf med grafen H , eller at den er H- farverbar . Dette omtales ofte som $\{u,v\}\in E(G)$ $\{f(u),f(v)\}\i E(H)$

G\to H

Definitionen ovenfor strækker sig til rettede grafer. Så for en homomorfi er en bue (rettet kant) af grafen H , når ( u , v ) er en bue af grafen G. $f:G\to H,(f(u),f(v))$

Der er en injektiv homomorfi fra G til H (det vil sige et kort, der aldrig kortlægger forskellige hjørner til en enkelt), hvis og kun hvis G er en undergraf af H . Hvis en homomorfi er en bijektion (en en-til-en overensstemmelse mellem hjørnerne af G og H ), hvis inverse funktion også er en grafhomomorfi, så er f en grafisomorfi [7] . $f:G\til H$

Dækkende kortlægninger er en almindelig type homomorfi, der afspejler definitionen og mange egenskaber for en dækning i topologi [8] . De er defineret som surjektive homomorfismer, der er lokalt bijektive, dvs. en bijektion i et kvarter af hvert vertex. Et eksempel er en dobbelt dækning af en todelt graf dannet ud fra en graf ved at opdele hvert toppunkt v i og og erstatte hver kant u , v med to kanter og . Funktionsmapping v 0 og v 1 til v af den originale graf er en homomorfi og en dækkende mapping. $v_{0}$ $v_{1}$ $u_{0},v_{1}$ ${\displaystyle v_{0},u_{1))$

Grafhomeomorfi er et separat begreb, der ikke er direkte relateret til homomorfi. Groft sagt kræver det injektivitet, men gør det muligt at kortlægge kanter til stier (i stedet for kun kanter). Graph minor forbliver et svagere koncept.

Kerner og tilbagetrækninger

To grafer G og H er homomorfisk ækvivalente if og [4] [5] [6] . $G\to H$ $H\to G$

En tilbagetrækning er en homomorfi r fra G til en undergraf H af G , således at r ( v ) = v for hvert toppunkt v af H. I dette tilfælde kaldes undergrafen H en tilbagetrækning af grafen G [9] .

En kerne er en graf, der ikke har en homomorfi til nogen egentlig undergraf. Tilsvarende kan en kerne defineres som en graf, der ikke er en tilbagetrækning for nogen egentlig undergraf [10] . Enhver graf G er homomorfisk ækvivalent med en unik kerne (op til isomorfi), som kaldes kernen af grafen G [11] [12] . Bemærk, at dette ikke er tilfældet for generelle uendelige grafer [13] . De samme definitioner gælder dog for rettet grafer, og en rettet graf svarer også til en enkelt kerne. Enhver urettet og rettet graf indeholder sin kerne både som en tilbagetrækning og som en genereret undergraf [9] .

For eksempel er alle komplette grafer K n og alle ulige cyklusser ( cyklusgrafer med ulige længder) kerner. Enhver 3-farverbar graf G , der indeholder en trekant (dvs. har en komplet graf K 3 som en undergraf), er homøomorfisk ækvivalent med K 3 . Dette skyldes på den ene side, at en 3-farvning af en graf G er det samme som en homomorfi , som forklaret nedenfor. På den anden side indrømmer enhver undergraf af G trivielt en homomorfi til G , hvoraf det følger, at . Dette betyder også, at K 3 er kernen af enhver sådan graf G . På samme måde svarer enhver todelt graf , der har mindst én kant, til K 2 [14] . $G\to K_{3}$ $K_{3}\to G$

Forholdet til farvelægningssider

En k -farvning for nogle heltal k er tildelingen af en af de k farver til hvert hjørne af grafen G , således at endespidserne af hver kant har forskellige farver. k -Farvninger af grafen G svarer nøjagtigt til homomorfier fra G til hele grafen K k [15] [16] . Desudensvarer hjørnerne af grafen K k til k farver, og to farver er tilstødende som hjørner på grafen K k , hvis og kun hvis de er forskellige. Derfor definerer funktionen en homomorfi i K k , hvis og kun hvis de tilstødende hjørner af grafen G er farvet i forskellige farver. Især en graf G er k -farverbar, hvis og kun hvis den er K k -farverbar [15] [16] .

Hvis der er to homomorfismer og , så er deres superposition også en homomorfi [17] . Med andre ord, hvis grafen H kan farves med k farver og der er en homomorfi G til H , så kan G også farves med k farver. Derfor følger det af , hvor betyder grafens kromatiske tal (det mindste antal farver k , som grafen kan farvelægges i) [18] . $G\to H$ ${\displaystyle H\to K_{k))$ ${\displaystyle G\to K_{k))$ $G\to H$ $\chi (G)\leqslant \chi (H)$ $\chi$

Indstillinger

Generelle homomorfier kan også betragtes som en slags farvning - hvis hjørnerne af en fast graf H er tilladte farver , og kanterne på grafen H beskriver hvilke farver der er kompatible , så er H- farvningen af grafen G tildelingen af farver til hjørnerne af grafen G , så tilstødende hjørner modtager kompatible farver. Mange begreber om graffarvning passer ind i dette skema og kan udtrykkes som grafhomomorfismer i forskellige graffamilier. Cyklusfarvninger kan defineres ved hjælp af homomorfismer til at cykle komplette grafer , hvilket forfiner den sædvanlige opfattelse af farvning [19] [20] . Brøk- og b - foldsfarvninger kan defineres ved hjælp af homomorfier til Kneser-grafer [21] [22] T-farver svarer til homomorfier til nogle uendelige grafer [23] . { En rettet farvning af en rettet graf er en homomorfi til enhver rettet graf [24] . L(2,1)-farven er en lokalt injektiv homomorfi i komplementet til en sti , hvilket betyder, at den skal være injektiv i et område af hvert hjørne [25] .

Orienteringer uden lange stier

En anden interessant sammenhæng vedrører orienteringen af grafer. En orientering af en urettet graf G er en hvilken som helst rettet graf opnået ved at vælge mellem to mulige orienteringer for hver kant. Et eksempel på orienteringen af en komplet graf K k er en transitiv turnering med hjørner 1,2,..., k og buer fra i til j , når i < j . En homomorfi mellem orienteringer af graferne G og H giver en homomorfi mellem urettede grafer G og H , hvis vi blot ignorerer orienteringerne. På den anden side, givet en homomorfi mellem urettede grafer, kan enhver orientering af H kortlægges til en orientering af grafen for G , så den har en homomorfi i . Derfor er en graf G k -farverbar (har en homomorfi i K k ), hvis og kun hvis en eller anden orientering af G har en homomorfi i [26] . ${\vec {T}}_{k}$ $G\to H$ ${\vec {H}}$ ${\vec {G}}$ ${\vec {G}}$ ${\vec {H}}$ ${\vec {T}}_{k}$

Folkloresætningen siger, at for enhver k har en rettet graf G en homomorfi i hvis og kun hvis den ikke indrømmer homomorfien fra [27] . Her er en orienteret sti med toppunkter 1, 2, …, n og buer fra i til i + 1 for i =1, 2, …, n − 1. Grafen er således k -farverbar, hvis og kun hvis den har orienteringen, som ikke indrømmer en homomorfi fra . Dette udsagn kan styrkes lidt for at sige, at en graf er k -farverbar, hvis og kun hvis en eller anden orientering ikke indeholder en rettet vej med længden k (ikke som en undergraf). Dette er Gallai-Hasse-Roy-Vitaver-sætningen . ${\vec {T}}_{k}$ ${\vec {P}}_{k+1}$ ${\vec {P}}_{n}$ ${\vec {P}}_{k+1}$ ${\vec {P}}_{k+1}$

Forholdet til problemer med begrænsningstilfredshed

Eksempler

Nogle planlægningsproblemer kan modelleres som et spørgsmål om at finde grafhomomorfismer [15] [28] . Som et eksempel kan man forsøge at planlægge øvelsessessioner, så to kurser, som den samme studerende deltager, ikke er for tæt i tid. Kurser danner en graf G , med kanter mellem to kurser, hvis de deltages af samme elev. Det mulige tidspunkt for at gennemføre kurser danner en graf H med kanter mellem to tidsvinduer, hvis afstanden i tid mellem dem er stor nok. For eksempel, hvis man ønsker at have et cyklisk ugeskema, således at hver elev kommer til træning hver anden dag, så vil kolonne H være komplementet til kolonne C 7 . En grafhomomorfi fra G til H er så tildelingen af kurser over tidsvinduer [15] . For at tilføje et krav, f.eks., at ingen elever har undervisning både fredag og mandag, er det nok at fjerne den ene kant fra grafen H .

Et simpelt frekvensfordelingsproblem kan formuleres som følger. Der er flere trådløse netværkssendere . Du skal på hver af dem vælge den frekvenskanal, hvorigennem den vil overføre data. For at undgå interferens skal sendere, der er geografisk tætte, have kanaler med tilstrækkeligt forskellige frekvenser. Hvis denne betingelse er begrænset til en simpel tærskel for begreberne "geografisk tæt" og "tilstrækkeligt langt væk", svarer det gyldige valg af kanaler igen til en grafhomomorfi. Her vil graf G være et sæt sendere med kanter imellem, hvis de er geografisk tæt på, og graf H vil være et sæt kanaler med kanter mellem kanalerne, hvis frekvenserne er tilstrækkeligt forskellige. Selvom denne model er meget forenklet, giver den en vis fleksibilitet - for et par sendere, der ikke er tæt på, men som kan forstyrre hinanden på grund af geografiske træk, kan der tilføjes en bue i G . Og buen mellem sendere, der ikke virker på samme tid, kan fjernes fra grafen. På samme måde kan en kant mellem et par kanaler, der er langt fra hinanden, men som har harmonisk interferens , fjernes fra H- grafen [29] .

I hvert tilfælde viser disse forenklede modeller mange funktioner, der bør udarbejdes i praksis [30] . Problemer med begrænsningstilfredshed , som generaliserer grafhomomorfiproblemer, kan udtrykke yderligere typer betingelser (såsom individuelle præferencer eller begrænsninger på antallet af matchende tildelinger). Dette gør modellerne mere realistiske og praktiske.

Formelt synspunkt

Styrede og rettede grafer kan opfattes som hyppige forekomster af et mere generelt koncept kaldet relationelle strukturer som defineres som et sæt med en tuple af relationer på). Styrede grafer er strukturer med én binær relation (tilgrænsende) på et domæne (et sæt af hjørner) [31] [3] . Fra dette synspunkt er homomorfier af sådanne strukturer nøjagtigt grafhomomorfier. I det generelle tilfælde er spørgsmålet om at finde en homomorfi fra en struktur til en anden et problem med begrænsningstilfredshed ( CSP) . Tilfældet med grafer giver et konkret første skridt, der hjælper med at forstå mere komplekse begrænsningstilfredshedsproblemer. Mange algoritmiske metoder til at finde grafhomomorfismer, såsom backtracking , constraint propagation , og lokal søgning er anvendelige til alle constraint satisfaction problemer [3] .

For graferne G og H svarer spørgsmålet, om grafen G har en homomorfi til grafen H , til et bestemt tilfælde af begrænsningstilfredshedsproblemet med kun én slags begrænsning [3] . I denne opgave vil variablerne være toppunkterne på grafen G , og rækkevidden af hver variabel vil være sættet af toppunkter på grafen H. Løsningen er en funktion, der tildeler et element fra området til hver variabel, således at funktionen f afbilder V ( G ) til V ( H ). Hver kant eller bue [32] ( u , v ) på grafen G svarer så til begrænsningen (( u , v ), E( H )). Denne begrænsning udtrykker, at løsningen skal afbilde buen ( u , v ) til parret ( f ( u ), f ( v ) ), som er relationen E ( H ), altså til buen af grafen H . Løsningen på problemet er en løsning, der opfylder alle begrænsningerne, det vil sige, det er præcis en homomorfi fra G til H .

Struktur af homomorfismer

Superpositioner af homomorfier er homomorfier [17] . Især en relation på grafer er transitiv (og, trivielt, refleksiv), så denne relation er en forudbestilling på grafer [33] . Vi vil betegne homomorfi -ækvivalensklassen for en graf G med [ G ]. En ækvivalensklasse kan repræsenteres af en enkelt kerne i [ G ]. Relationen er delvist ordnet på disse ækvivalensklasser. Den definerer et delvist ordnet sæt [34] . $\til$ $\til$

Lad G < H betyde, at der er en homomorfi fra G til H , men ingen homomorfi fra H til G. Relationen er en tæt rækkefølge , hvilket betyder, at for alle (urettede) grafer G , H sådan at G < H , eksisterer der en graf K sådan at G < K < H (dette gælder i alle tilfælde undtagen for de trivielle tilfælde eller ) [35] [36] [37] . For eksempel er der mellem to komplette grafer (bortset fra ) uendeligt mange cykliske komplette grafer svarende til rationelle tal [38] [39] . $\til$ $G=K_{0}$ $K_1$ ${\displaystyle K_{0},K_{1))$

Et delvist ordnet sæt af grafækvivalensklasser ved homomorfi er et distributivt gitter , med foreningen af [ G ] og [ H ] defineret som den (ækvivalensklasse) disjunkte union og skæringspunktet mellem [ G ] og [ H ] defineret som tensorprodukt (valget af graferne G og H som repræsentanter for ækvivalensklasserne [ G ] og [ H ] er ligegyldigt) [40] [41] . Elementerne i dette gitter, der er irreducerbare i foreningen er nøjagtigt forbundne grafer. Dette kan vises ved at bruge det faktum, at en homomorfi kortlægger en forbundet graf til en forbundet komponent af målgrafen [42] [43] . De skærings-irreducerbare elementer i dette gitter er nøjagtigt multiplikative grafer . Disse er grafer K , således at produktet kun har en homomorfi i K , hvis en af graferne G eller H har en sådan homomorfi. Opdagelsen af multiplikative grafer er kernen i Hedetniemis formodning [44] [45] . $[G\kop H]$ $[G\ gange H]$ $G\ gange H$

Grafhomomorfier danner også en kategori med grafer som objekter og homomorfier som pile [46] . Det oprindelige objekt er en tom graf, mens terminalobjektet er en graf med et toppunkt og en sløjfe ved det toppunkt. Tensorproduktet af grafer er et produkt i kategoriteori og en eksponentiel graf er et eksponentielt objekt for en kategori [45] [47] . Da disse to operationer altid er defineret, er kategorien af grafer en kartesisk lukket kategori . Af samme grunde er gitteret af grafækvivalensklasser ved homomorfismer i virkeligheden en Heyting-algebra [45] [47] .

For rettede grafer gælder de samme definitioner. Især er det delvist ordnet på ækvivalensklasserne af rettede grafer. Denne rækkefølge adskiller sig fra rækkefølgen på ækvivalensklasserne af urettede grafer, men indeholder den som en underrækkefølge. Dette skyldes, at enhver urettet graf kan opfattes som rettet, hvor en hvilken som helst bue ( u , v ) optræder sammen med en invers bue ( v , u ), og dette ændrer ikke på definitionen af en homomorfi. Rækkefølgen for rettede grafer er igen et distributivt gitter og en Heyting-algebra med unions- og skæringsoperationerne defineret som før. Denne rækkefølge er dog ikke stram. Der er også en kategori med rettede grafer som objekter og homomorfier som pile, som igen er en kartesisk lukket kategori [48] [47] . $\til$ $\til$ $\til$

Usammenlignelige grafer

Der er mange uforlignelige grafer i henhold til homomorfiers forudrækkefølge, det vil sige par af grafer, således at der ikke er homomorfier fra den ene til den anden [49] . En af måderne at konstruere sådanne grafer på er at overveje den ulige omkreds af grafen G , det vil sige længden af dens korteste cyklus med ulige længde. En ulige omkreds er tilsvarende det mindste ulige tal g , for hvilket der er en homomorfi fra en cyklusgraf med g spidser til G . Af denne grund, hvis , så er den ulige omkreds af grafen G større end eller lig med den ulige omkreds af grafen H [50] . $G\to H$

På den anden side, hvis , så er det kromatiske tal på grafen G mindre end eller lig med det kromatiske tal på grafen H . Derfor, hvis en graf G har en strengt taget større ulige omkreds end H og et strengt taget større kromatisk [49]uforligneligeHogG, så erHtal end [51] , så den er uforenelig med trekant K 3 . $G\to H$

Eksempler på grafer med vilkårligt store værdier af ulige omkreds og kromatisk tal er Kneser-grafer [52] og generaliserede Mychelskians [53] . En sekvens af sådanne grafer med en samtidig stigning i værdierne af begge parametre giver et uendeligt antal uforlignelige grafer ( en antikæde i forudgående rækkefølge af homomorfismer) [54] . Andre egenskaber, såsom tætheden af preorder af homomorfismer, kan bevises ved hjælp af sådanne familier [55] . Det er også muligt at bygge grafer med store værdier af kromatisk tal og omkreds, snarere end kun ulige omkreds, men vanskeligere (se Grafens omkreds og farvelægning ).

Det er meget nemmere at finde uforlignelige par blandt rettede grafer. Overvej f.eks. rettede cyklusgrafer med toppunkter 1, 2, …, n og kanter fra i til i + 1 (for i =1, 2, …, n − 1) og fra n til 1. Der er en homomorfi fra til kun når n er et multiplum af k . Især rettet cyklusgrafer med prime n er alle uforlignelige [56] . ${\vec {C}}_{n}$ ${\vec {C}}_{n}$ ${\vec {C}}_{k}(n,k\geqslant 3)$ ${\vec {C}}_{n}$

Beregningsmæssig kompleksitet

I grafhomomorfiproblemet består en instans af problemet af et par grafer ( G , H ), og løsningen er en homomorfi fra G til H. Det generelle løselighedsproblem , som spørger, om der er en løsning på dette problem, er NP-komplet [57] . Imidlertid fører grafbegrænsninger til en række forskellige problemer, hvoraf nogle er nemmere at løse. Metoderne, der anvender restriktioner på den venstre graf G , er meget forskellige fra de metoder, der anvendes på den højre graf H , men i hvert tilfælde er dikotomien (strenge grænser mellem simple og komplekse tilfælde) kendt eller antaget.

Homomorfier til en fast graf

Homomorfiproblemet med en fast graf H på højre side af hver instans kaldes H- farveproblemet. Når H er en komplet graf K k , er dette et graf - k -farveproblem, der kan løses i polynomisk tid for k =0, 1, 2 og ellers er NP-komplet [58] . Især er muligheden for en K 2 -farvning af en graf G ækvivalent med den todelte graf G , som kan verificeres i lineær tid. Mere generelt, når H er en todelt graf, er muligheden for H- farvning ækvivalent med muligheden for K 2 -farvning (eller K 0 / K 1 -farvbar, når H er tom eller har ingen kanter), og derfor lige så let at løse [59] . Pavol Hell og Jaroslav Neshetril beviste, at intet andet tilfælde er let for urettede grafer:

Hell-Neshetril-sætning (1990): Et H- farveproblem er i klasse P, hvis H er todelt og NP-hårdt ellers [60] [61] .

Sætningen er også kendt som dikotomisætningen for den (urettede) grafhomomorfi, da den opdeler H- farveproblemer i NP-komplette og klasse P-problemer uden mellemliggende tilfælde. For rettede grafer er situationen mere kompliceret og svarer faktisk til det mere generelle spørgsmål om at beskrive kompleksiteten af at opfylde begrænsninger [62] . Det viser sig, at H- farveproblemer for rettede grafer er lige så generelle og lige så forskellige som problemer med begrænsningstilfredshed med alle andre former for begrænsninger [63] [64] . Formelt set er et (finite) begrænsningssprog Γ et endeligt domæne og et endeligt sæt af relationer i det domæne. CSP( Γ ) er et problem med begrænsningstilfredsstillelse, hvor instanser kun må bruge begrænsninger fra Γ .

Sætning (Feder, Vardy 1998): For ethvert begrænsningssprog Γ er CSP( Γ ) ækvivalent efter polynomiel reduktion til et eller andet H- farveproblem for en eller anden rettet graf H [64] .

Intuitivt betyder dette, at enhver algoritmisk teknik eller kompleksitetsresultat, der kan anvendes på H- farveproblemer for rettede grafer H , også gælder for generelle begrænsningstilfredshedsproblemer. Især kan man spørge, om Hell-Neshetril-sætningen kan udvides til rettede grafer. Ved ovenstående sætning svarer dette til Feder-Vardi-formodningen om dikotomien af begrænsningstilfredshedsproblemer, som siger, at for ethvert begrænsningssprog Γ er CSP( Γ ) enten NP-komplet eller tilhører klassen P [57] .

Homomorfismer fra en fast familie af grafer

Homomorfiproblemet med én fast graf G på venstre side kan løses ved udtømmende søgning i tid | V ( H )| O(| V ( G )|) , det vil sige polynomium i størrelsen af inputgrafen H [65] . Med andre ord er problemet trivielt i P for grafer G af afgrænset størrelse. Et interessant spørgsmål er så, hvilke andre egenskaber ved grafen G udover størrelse gør polynomielle algoritmer mulige.

Nøgleegenskaben viser sig at være treewidth , et mål for, hvor ens en graf er et træ. For en graf G med højst træbredde k og en graf H kan homomorfiproblemet løses i tide | V ( H )| O( k ) ved standard dynamiske programmeringsmetoder . Faktisk er det tilstrækkeligt at antage, at kernen af G højst har træbredde k . Dette er sandt, selvom kernen ikke er kendt [66] [67] .

Indikator i algoritmen med køretid| V ( H )| O( k ) kan ikke reduceres væsentligt - der er ingen algoritme, der kører i tid | V ( H )| o(tw( G ) /log tw( G )), hvis den eksponentielle tidshypotese ( ETH) er sand, selvom inputtet er begrænset af en hvilken som helst klasse af grafer med ubegrænset træbredde [68] . ETH er en ubevist antagelse, der ligner P ≠ NP- antagelsen , men mere stringent. Under de samme forudsætninger er der ingen andre egenskaber, der kan bruges til at udlede polynomielle tidsalgoritmer. Dette formaliseres af sætningen:

Sætning (Martin Grohe): For en beregnelig klasse af grafer hører homomorfiproblemet for c til P, hvis og kun hvis graferne har kerner med afgrænset træbredde (i ETH-antagelsen) [67] .

{\mathcal {G}}

(G,H)

G\in {\mathcal {G}}

{\mathcal {G}}

Man kan spørge, om problemet kan løses med en vilkårlig høj afhængighed af G , men med en fast polynomisk afhængighed af størrelsen af grafen H. Svaret er ja, hvis vi begrænser grafen G til en klasse med kerner med afgrænset træbredde, og nej for alle andre klasser [67] . I sproget med parametriseret kompleksitet, siger denne erklæring formelt, at homomorfiproblemet med graf , parametriseret af størrelsen (antal kanter) af G , viser en dikotomi. Det kan bestemmes med faste parametre hvis graferne i klassen har kerner med afgrænset træbredde, og W[1]-komplet ellers. ${\mathcal {G}}$ ${\mathcal {G}}$

Det samme udsagn gælder for mere generelle begrænsningstilfredshedsproblemer (eller med andre ord for relationelle strukturer). Den eneste antagelse, der kræves, er, at begrænsninger kun kan involvere et begrænset antal variable. Parameteren er så træbredden af hovedbegrænsningsgrafen [68] .

Se også

Hypotese Sidorenko

Noter

↑ Hell, Nešetřil, 2004 , s. 27.
↑ Hell, Nešetřil, 2004 , s. 109.
↑ 1 2 3 4 Hell, Nešetřil, 2008 .
↑ 12 Cameron , 2006 .
↑ 1 2 Geňa, Tardif, 1997 .
↑ 1 2 Hell, Nešetřil, 2004 .
↑ Gena, Tardif, 1997 , observation 2.3.
↑ Godsil, Royle, 2001 , s. 115.
↑ 1 2 Hell, Nešetřil, 2004 , s. 19.
↑ Hell, Nešetřil, 2004 , Proposition 1.31.
↑ Cameron, 2006 , forslag 2.3.
↑ Hell, Nešetřil, 2004 , konsekvens 1.32.
↑ Hell, Nešetřil, 2004 , s. 34.
↑ Cameron, 2006 , s. 4 (Proposition 2.5).
↑ 1 2 3 4 Cameron, 2006 , s. en.
↑ 1 2 Hell, Nešetřil, 2004 , Proposition 1.7.
↑ 1 2 Hell, Nešetřil, 2004 , §1.7.
↑ Hell, Nešetřil, 2004 , konsekvens 1.8.
↑ Hell, Nešetřil, 2004 , §6.1.
↑ Gena, Tardif, 1997 , §4.4.
↑ Hell, Nešetřil, 2004 , §6.2.
↑ Gena, Tardif, 1997 , §4.5.
↑ Hell, Nešetřil, 2004 , §6.3.
↑ Hell, Nešetřil, 2004 , §6.4.
↑ * Fiala J., Kratochvíl J. Delvis omslag af grafer // Diskussioner Mathematicae Graph Theory. - 2002. - T. 22 , no. 1 . — S. 89–99 . - doi : 10.7151/dmgt.1159 .
↑ Hell, Nešetřil, 2004 , s. 13-14.
↑ Hell, Nešetřil, 2004 , Proposition 1.20.
↑ Hell, Nešetřil, 2004 , §1.8.
↑ Hell, Nešetřil, 2004 , s. 30-31.
↑ Hell, Nešetřil, 2004 , s. 31-32.
↑ Hell, Nešetřil, 2004 , s. 28. Bemærk, at relationelle strukturer i artiklen kaldes relationelle systemer .
↑ Husk, at kanterne på en rettet graf normalt kaldes buer.
↑ Hell, Nešetřil, 2004 , §3.1.
↑ Hell, Nešetřil, 2004 , sætning 3.1.
↑ Hell, Nešetřil, 2004 , sætning 3.30.
↑ Geňa, Tardif, 1997 , sætning 2.33.
↑ Welzl, 1982 , s. 29-41.
↑ Hell, Nešetřil, 2004 , s. 192.
↑ Gena, Tardif, 1997 , s. 127.
↑ Hell, Nešetřil, 2004 , Proposition 3.2, distributivitet er angivet i Proposition 2.4.
↑ Geňa, Tardif, 1997 , sætning 2.37.
↑ Kwuida, Lehtonen, 2011 , s. 251-265.
↑ Gray, 2014 , Lemma 3.7.
↑ Tardif, 2008 , s. 46-57.
↑ 1 2 3 Dwight, Sauer, 1996 , s. 125-139.
↑ Hell, Nešetřil, 2004 , s. 125.
↑ 1 2 3 Grå, 2014 .
↑ Brown, Morris, Shrimpton, Wensley, 2008 .
↑ 1 2 Hell, Nešetřil, 2004 , s. 7.
↑ Gena, Tardif, 1997 , observation 2.6.
↑ Weisstein, Eric W. Grötzsch Graf på Wolfram MathWorld -webstedet .
↑ Gena, Tardif, 1997 , forslag 3.14.
↑ Gyárfás, Jensen, Stiebitz, 2004 , s. 1-14.
↑ Hell, Nešetřil, 2004 , Proposition 3.4.
↑ Hell, Nešetřil, 2004 , s. 96.
↑ Hell, Nešetřil, 2004 , s. 35.
↑ 1 2 Bodirsky, 2007 , §1.3.
↑ Hell, Nešetřil, 2004 , §5.1.
↑ Hell, Nešetřil, 2004 , Proposition 5.1.
↑ Hell, Nešetřil, 2004 , §5.2.
↑ Hell, Nešetřil, 1990 , s. 92-110.
↑ Hell, Nešetřil, 2004 , §5.3.
↑ Hell, Nešetřil, 2004 , sætning 5.14.
↑ 1 2 Feder, Vardi, 1998 , s. 57-104.
↑ Cygan, Fomin, Golovnev et al., 2016 , s. 1643-1649
↑ Dalmau, Kolaitis, Vardi, 2002 , s. 310-326.
↑ 1 2 3 Grohe, 2007 .
↑ 12 Marx , 2010 , s. 85-112.

Litteratur

Welzl E. Farvefamilier er tætte // Teoret. Comput. sci. . - 1982. - T. 17 . — s. 29–41 . - doi : 10.1016/0304-3975(82)90129-3 .
Pavol Hell, Jaroslav Nesetzil. Om kompleksiteten af H-farvning // JCTB . - 1990. - T. 48 , no. 1 . — S. 92–110 . - doi : 10.1016/0095-8956(90)90132-J .
Gyárfás A., Jensen T., Stiebitz M. Om grafer med stærkt uafhængige farveklasser // J. Graph Theory . - 2004. - T. 46 , no. 1 . — S. 1–14 . - doi : 10.1002/jgt.10165 .

Leonard Kwuida, Erkko Lehtonen. Om Homomorphism Order of Labeled Posets // Order . - Springer, 2011. - T. 28 , no. 2 . — S. 251–265 . - doi : 10.1007/s11083-010-9169-x . - arXiv : 0911.0200 .
Tardif C. Hedetniemis formodning, 40 år senere // Graph Theory Notes of New York. - 2008. - T. 54 . — s. 46–57 .
Dwight D., Sauer N. Gitter, der opstår i kategoriale undersøgelser af Hedetniemis formodning // Diskret matematik. . - 1996. - T. 152 , no. 1-3 . — S. 125–139 . - doi : 10.1016/0012-365X(94)00298-W .
Daniel Marx. Kan du slå træbredden? // Theory of Computing . - 2010. - T. 6 . — S. 85–112 . - doi : 10.4086/toc.2010.v006a005 .
Cygan M., Fomin FV, Golovnev A., Kulikov AS, Mihajlin I., Pachocki J., Socała A. Snævre grænser for grafhomomorfi og subgrafisomorfi. - SIAM , 2016. - ISBN 978-1-611974-33-1 .
Victor Dalmau, Phokion G. Kolaitis, Moshe Y. Vardi. Constraint Satisfaction, Bounded Treewidth og Finite-Variable Logics. - 2002. - S. 310-326. - doi : 10.1007/3-540-46135-3_21 .
Martin Grohe. Kompleksiteten af homomorfi og problemer med begrænsningstilfredshed set fra den anden side // J. ACM . - 2007. - T. 54 , no. 1 . - doi : 10.1145/1206035.1206036 .
Tomás Feder, Moshe Y. Vardi . Den beregningsmæssige struktur af monoton monadisk SNP og begrænsningstilfredshed: En undersøgelse gennem datalog og gruppeteori // SIAM J. Comput. . - 1998. - T. 28 , no. 1 . — s. 57–104 . - doi : 10.1137/S0097539794266766 .

Generelle bøger

Peter Cameron. Graph Homomorphisms, Combinatorics Study Group Notes . – 2006.
Pavol Hell, Jaroslav Nesetzil. Grafer og Homomorfismer . - Oxford University Press, 2004. - V. 28 . — ISBN 0-19-852817-5 .
Geňa H., Tardif C. Grafhomomorfismer : struktur og symmetri // Grafsymmetri: Algebraiske metoder og anvendelser . - Springer, 1997. - S. 107-166. - doi : 10.1007/978-94-015-8937-6_4 .
Chris Godsil, Gordon Royle. 6. Homomorfismer // Algebraisk grafteori. - Springer-Verlag New York, 2001. - T. 207. - (Kandidattekster i matematik). — ISBN 978-1-4613-0163-9 . - doi : 10.1007/978-1-4613-0163-9 .

I universel algebra og underlagt begrænsninger

Bodirsky M. Graph Homomorphisms and Universal Algebra, Course Notes . – 2007.
Pavol Hell, Jaroslav Nesetzil. Farvelægning, begrænsningstilfredshed og kompleksitet // Computer Science Review. - 2008. - Vol. 2 , udgave. 2 . — S. 143–163 . - doi : 10.1016/j.cosrev.2008.10.003 .

I gitterteori og kategoriteori

Brown R., Morris I., Shrimpton J., Wensley CD Grafer over grafers morfismer // Electronic Journal of Combinatorics . - 2008. - T. 15 , no. 1 . - S. A1 .
Grå CT The Digraph Lattice . — 2014. ( AMSI Vacation Research Scholarships , studerendes forskningsrapport overvåget af Brian Davey og Jane Pitkethly, La Trobe University ).