Omomorfismul grafic

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 14 octombrie 2021; verificările necesită 2 modificări .

Un homomorfism de grafic este o mapare între două grafice care nu rupe structura. Mai precis, este o mapare între un set de vârfuri a două grafice care mapează vârfurile adiacente cu cele adiacente.

Omomorfismele generalizează diverse noțiuni de colorare a graficelor și permit exprimarea unor clase importante de probleme de satisfacție a constrângerilor , cum ar fi unele probleme de planificare sau probleme de alocare a frecvenței radio [1] . Faptul că homomorfismele pot fi folosite secvenţial duce la structuri algebrice bogate - preordonare pe grafuri, reţele distributive şi categorii (una pentru grafuri nedirecţionate şi una pentru grafuri direcţionate) [2] . Complexitatea de calcul a găsirii unui homomorfism între grafice date este în general prohibitivă, dar sunt cunoscute multe cazuri speciale când sarcina este fezabilă în timp polinomial . Granițele dintre cazurile rezolvabile și cele insurmontabile se află într-un domeniu de cercetare activă [3] .

Definiții

În acest articol, dacă nu se specifică altfel, graficele înseamnă grafice finite nedirecționate cu bucle permise , dar nu sunt permise margini multiple (paralele). Un homomorfism de graf [4] [5] [6] : f de la graf la graf , care se scrie ca $G=(V(G),E(G))$ $H=(V(H),E(H))$

f:G\la H

este o funcție de la V ( G ) la V ( H ) care mapează punctele de capăt ale fiecărei muchii de la G la punctele de capăt ale unei muchii din H . Formal, rezultă din , pentru toate perechile de vârfuri u , v din V ( G ). Dacă există un anumit homomorfism de la G la H , atunci graficul G se spune că este homomorf cu graficul H sau că este H- colorabil . Acest lucru este adesea denumit $\{u,v\}\in E(G)$ $\{f(u),f(v)\}\in E(H)$

G\la H

Definiția de mai sus se extinde la graficele direcționate. Atunci, pentru un homomorfism, este un arc (margine direcționată) al graficului H când ( u , v ) este un arc al graficului G. $f:G\la H,(f(u),f(v))$

Există un homomorfism injectiv de la G la H (adică o hartă care nu mapează niciodată vârfuri diferite la unul singur) dacă și numai dacă G este un subgraf al lui H . Dacă un homomorfism este o bijecție (o corespondență unu-la-unu între vârfurile lui G și H ) a cărei funcție inversă este și un homomorfism de graf, atunci f este un izomorfism de graf [7] . $f:G\la H$

Mapările de acoperire sunt un tip comun de homomorfism care reflectă definiția și multe proprietăți ale unei acoperiri în topologie [8] . Ele sunt definite ca homomorfisme surjective care sunt local bijective, adică o bijecție într-o vecinătate a fiecărui vârf. Un exemplu este o acoperire dublă cu un graf bipartit format dintr-un graf prin împărțirea fiecărui vârf v în și și înlocuirea fiecărei muchii u , v cu două muchii și . Maparea funcției v 0 și v 1 la v a graficului original este un homomorfism și o mapare de acoperire. $v_{0}$ $v_{1}$ $u_{0},v_{1}$ $v_{0},u_{1)$

Homeomorfismul grafic este un concept separat, care nu este direct legat de homomorfisme. În linii mari, necesită injectivitate, dar permite ca marginile să fie mapate la căi (mai degrabă decât margini). Minorii grafici rămân un concept mai slab.

Miezuri și retractări

Două grafice G și H sunt echivalente homomorf dacă și [4] [5] [6] . $G\la H$ $H\la G$

O retragere este un homomorfism r de la G la un subgraf H al lui G astfel încât r ( v )= v pentru fiecare vârf v al lui H . În acest caz, subgraful H se numește retractare a graficului G [9] .

Un nucleu este un graf care nu are un homomorfism la niciun subgraf propriu. În mod echivalent, un nucleu poate fi definit ca un graf care nu este un retract pentru niciun subgraf propriu [10] . Orice graf G este echivalent homomorf cu un nucleu unic (până la izomorfism), care se numește nucleul grafului G [11] [12] . Rețineți că acest lucru nu este valabil pentru graficele infinite generale [13] . Cu toate acestea, aceleași definiții se aplică graficelor direcționate, iar un graf direcționat este, de asemenea, echivalent cu un singur nucleu. Orice graf nedirecționat și direcționat conține nucleul său atât ca retract, cât și ca subgraf generat [9] .

De exemplu, toate graficele complete Kn și toate ciclurile impare (graficele ciclului de lungime impară) sunt nuclee. Orice grafic G cu 3 culori care conține un triunghi (adică are un grafic complet K 3 ca subgraf) este echivalent homeomorf cu K 3 . Acest lucru se datorează faptului că, pe de o parte, o 3-colorare a unui grafic G este aceeași cu un homomorfism , așa cum se explică mai jos. Pe de altă parte, orice subgraf al lui G admite trivial un homomorfism la G , de unde rezultă că . Aceasta înseamnă, de asemenea, că K 3 este nucleul oricărui astfel de graf G . În mod similar, orice graf bipartit care are cel puțin o muchie este echivalent cu K 2 [14] . $G\la K_{3}$ $K_{3}\la G$

Relația cu paginile de colorat

O k -colorare pentru un număr întreg k este alocarea uneia dintre cele k culori fiecărui vârf al graficului G , astfel încât vârfurile de capăt ale fiecărei muchii să aibă culori diferite. k -Colorările graficului G corespund exact homomorfismelor de la G la graficul complet K k [15] [16] . În plus, vârfurile graficului K k corespund k culori și două culori sunt adiacente ca vârfuri ale graficului K k dacă și numai dacă sunt diferite. Prin urmare, funcția definește un homomorfism în K k dacă și numai dacă vârfurile adiacente ale graficului G sunt colorate în culori diferite. În special, un grafic G este k -colorabil dacă și numai dacă este K k -colorabil [15] [16] .

Dacă există două homomorfisme și , atunci suprapunerea lor este și un homomorfism [17] . Cu alte cuvinte, dacă graficul H poate fi colorat cu k culori și există un homomorfism G în H , atunci G poate fi colorat și cu k culori. Prin urmare, rezultă din , unde înseamnă numărul cromatic al graficului (cel mai mic număr de culori k , în care graficul poate fi colorat) [18] . $G\la H$ $H\la K_{k)$ $G\la K_{k)$ $G\la H$ $\chi (G)\leqslant \chi (H)$ $\chi$

Opțiuni

Omomorfismele generale pot fi considerate și ca un fel de colorare - dacă vârfurile unui grafic fix H sunt culori permise , iar marginile graficului H descriu ce culori sunt compatibile , atunci colorarea H a graficului G este atribuirea de culori la vârfurile graficului G astfel încât vârfurile adiacente să primească culori compatibile. Multe noțiuni de colorare a graficelor se încadrează în această schemă și pot fi exprimate ca homomorfisme de grafic în diferite familii de grafice. Ciclurile de colorare pot fi definite folosind homomorfisme pentru a cicluri grafice complete , rafinând noțiunea obișnuită de colorare [19] [20] . Colorațiile fracționale și b - fold pot fi definite folosind homomorfisme la graficele Kneser [21] [22] Colorațiile T corespund homomorfismelor unor grafice infinite [23] . { O colorare direcționată a unui graf direcționat este un homomorfism la orice graf direcționat [24] . L(2,1)-coloring este un homomorfism local injectiv în complementul unui drum , ceea ce înseamnă că trebuie să fie injectiv într-o vecinătate a fiecărui vârf [25] .

Orientari fara trasee lungi

O altă legătură interesantă se referă la orientarea graficelor. O orientare a unui graf nedirecționat G este orice graf direcționat obținut prin alegerea dintre două orientări posibile pentru fiecare muchie. Un exemplu de orientare a unui graf complet K k este un turneu tranzitiv cu vârfurile 1,2,…, k și arce de la i la j când i < j . Un homomorfism între orientările graficelor G și H oferă un homomorfism între graficele nedirecționate G și H dacă pur și simplu ignorăm orientările. Pe de altă parte, având în vedere un homomorfism între grafice nedirecționate, orice orientare a lui H poate fi mapată la o orientare a graficului lui G , astfel încât să aibă un homomorfism în . Prin urmare, un grafic G este k -colorabil (are un homomorfism în K k ) dacă și numai dacă o anumită orientare a lui G are un homomorfism în [26] . ${\vec {T}}_{k}$ $G\la H$ ${\vec {H}}$ ${\vec {G}}$ ${\vec {G}}$ ${\vec {H}}$ ${\vec {T}}_{k}$

Teorema folclorului spune că pentru orice k un graf direcționat G are un homomorfism în dacă și numai dacă nu admite homomorfismul din [27] . Aici , este o cale orientată cu vârfurile 1, 2, …, n și arce de la i la i + 1 pentru i =1, 2, …, n − 1. Astfel, graficul este k -colorabil dacă și numai dacă are orientarea , care nu admite un homomorfism din . Această afirmație poate fi ușor întărită pentru a spune că un grafic este k -colorabil dacă și numai dacă o anumită orientare nu conține o cale direcționată de lungime k (nu ca subgraf). Aceasta este teorema Gallai-Hasse-Roy-Vitaver . ${\vec {T}}_{k}$ ${\vec {P}}_{k+1}$ ${\vec {P}}_{n}$ ${\vec {P}}_{k+1}$ ${\vec {P}}_{k+1}$

Relația cu problemele de satisfacție cu constrângeri

Exemple

Unele probleme de planificare pot fi modelate ca o chestiune de găsire a homomorfismelor de graf [15] [28] . De exemplu, s-ar putea încerca să programați sesiuni de practică, astfel încât două cursuri la care urmează același student să nu fie prea apropiate în timp. Cursurile formează un grafic G , cu muchii între două cursuri, dacă sunt frecventate de același student. Timpul posibil de desfășurare a cursurilor formează un grafic H cu muchii între două ferestre de timp, dacă distanța în timp dintre ele este suficient de mare. De exemplu, dacă cineva dorește să aibă un program săptămânal ciclic, astfel încât fiecare elev să vină să exerseze o dată la două zile, atunci coloana H ar fi complementul coloanei C 7 . Un homomorfism de grafic de la G la H este atunci alocarea cursurilor pe ferestre de timp [15] . Pentru a adăuga o cerință, să zicem că niciun elev nu are o clasă atât vineri, cât și luni, este suficient să eliminați o margine din graficul H .

O problemă simplă de distribuție a frecvenței poate fi formulată după cum urmează. Există mai multe transmițătoare de rețea fără fir . Trebuie să selectați pe fiecare dintre ele canalul de frecvență prin care va transmite date. Pentru a evita interferența , emițătoarele apropiate geografic trebuie să aibă canale cu frecvențe suficient de diferite. Dacă această condiție este limitată la un prag simplu pentru conceptele „aproape geografic” și „suficient de departe”, alegerea validă a canalelor corespunde din nou unui homomorfism de graf. Aici, graficul G va fi un set de transmițătoare cu margini între ele dacă sunt apropiate geografic, iar graficul H va fi un set de canale cu margini între canale dacă frecvențele sunt suficient de diferite. Deși acest model este foarte simplificat, permite o oarecare flexibilitate - pentru o pereche de transmițătoare care nu sunt apropiate, dar care pot interfera între ele din cauza caracteristicilor geografice, se poate adăuga un arc în G. Și arcul dintre emițătoare care nu funcționează în același timp poate fi eliminat din grafic. În mod similar, o margine între o pereche de canale care sunt îndepărtate, dar au interferență armonică poate fi îndepărtată din graficul H [29] .

În fiecare caz, aceste modele simplificate prezintă multe caracteristici care ar trebui elaborate în practică [30] . Problemele de satisfacție cu constrângeri , care generalizează problemele de homomorfism grafic, pot exprima tipuri suplimentare de condiții (cum ar fi preferințe individuale sau restricții privind numărul de atribuiri de potrivire). Acest lucru face modelele mai realiste și mai practice.

Punct de vedere formal

Graficele direcționate și direcționate pot fi considerate ca exemple frecvente ale unui concept mai general numit structuri relaționale care sunt definite ca o mulțime cu un tuplu de relații pe el). Graficele direcționate sunt structuri cu o relație binară (adiacență) pe un domeniu (un set de vârfuri) [31] [3] . Din acest punct de vedere, homomorfismele ale unor astfel de structuri sunt exact homomorfisme de graf. În cazul general, problema găsirii unui homomorfism de la o structură la alta este o problemă de satisfacție a constrângerilor ( CSP) . Cazul graficelor oferă un prim pas concret care ajută la înțelegerea problemelor mai complexe de satisfacție a constrângerilor. Multe metode algoritmice pentru găsirea homomorfismelor de graf, cum ar fi backtracking , propagarea constrângerii și căutarea locală sunt aplicabile tuturor problemelor de satisfacție a constrângerilor [3] .

Pentru graficele G și H , întrebarea dacă graficul G are un homomorfism cu graficul H corespunde unui caz particular al problemei de satisfacere a constrângerilor cu un singur fel de constrângere [3] . În această problemă , variabilele vor fi vârfurile graficului G , iar intervalul fiecărei variabile va fi mulțimea de vârfuri ale graficului H . Soluția este o funcție care atribuie un element din interval fiecărei variabile, astfel încât funcția f mapează V ( G ) la V ( H ). Fiecare muchie sau arc [32] ( u , v ) a graficului G corespunde atunci constrângerii (( u , v ), E( H )). Această constrângere exprimă că soluția trebuie să mapeze arcul ( u , v ) la perechea ( f ( u ), f ( v )), care este relația E ( H ), adică la arcul graficului H . Soluția problemei este o soluție care satisface toate constrângerile, adică este exact un homomorfism de la G la H .

Structura homomorfismelor

Suprapozițiile de homomorfisme sunt homomorfisme [17] . În special, o relație pe grafuri este tranzitivă (și, trivial, reflexivă), deci această relație este o preordonare pe grafuri [33] . Vom nota clasa de echivalență homomorfism a unui graf G cu [ G ]. O clasă de echivalență poate fi reprezentată printr-un singur nucleu în [ G ]. Relația este parțial ordonată pe aceste clase de echivalență. Ea definește o mulțime parțial ordonată [34] . $\la$ $\la$

Fie G < H să însemne că există un homomorfism de la G la H dar niciun homomorfism de la H la G . Relația este o ordine densă , ceea ce înseamnă că pentru toate graficele (nedirecționate) G , H astfel încât G < H , există un grafic K astfel încât G < K < H (acest lucru este valabil în toate cazurile, cu excepția cazurilor triviale sau ) [35] [36] [37] . De exemplu, între oricare două grafice complete (cu excepția ) există infinit de multe grafice complete ciclice care corespund numerelor raționale [38] [39] . $\la$ $G=K_{0)$ $K_1$ ${\displaystyle K_{0},K_{1))$

Un set parțial ordonat de clase de echivalență grafică prin homomorfism este o rețea distributivă , cu uniunea lui [ G ] și [ H ] definită ca uniunea disjunctă (clasa de echivalență) și intersecția lui [ G ] și [ H ] definite ca produs tensor (alegerea graficelor G și H ca reprezentanți ai claselor de echivalență [ G ] și [ H ] nu contează) [40] [41] . Elementele acestei rețele care sunt ireductibile în uniunea sunt grafuri exact conectate . Acest lucru poate fi demonstrat folosind faptul că un homomorfism mapează un graf conectat la o componentă conexă a graficului țintă [42] [43] . Elementele ireductibile la intersecție ale acestei rețele sunt exact grafice multiplicative . Acestea sunt grafice K astfel încât produsul are un homomorfism în K numai dacă unul dintre graficele G sau H are un astfel de homomorfism. Descoperirea graficelor multiplicative este miezul conjecturii lui Hedetniemi [44] [45] . $[G\cup H]$ $[G\time H]$ $G\ ori H$

Omomorfismele de grafic formează, de asemenea, o categorie cu graficele ca obiecte și homomorfismele ca săgeți [46] . Obiectul inițial este un grafic gol, în timp ce obiectul terminal este un grafic cu un vârf și o buclă la acel vârf. Produsul tensor al graficelor este un produs în teoria categoriilor și un grafic exponențial este un obiect exponențial pentru o categorie [45] [47] . Deoarece aceste două operații sunt întotdeauna definite, categoria graficelor este o categorie închisă carteziană . Din aceleași motive, rețeaua claselor de echivalență de graf prin homomorfisme este, de fapt, o algebră Heyting [45] [47] .

Pentru graficele direcționate se aplică aceleași definiții. În special, este parțial ordonat pe clasele de echivalență ale graficelor direcționate. Această ordine diferă de ordinea pe clasele de echivalență ale graficelor nedirecționate, dar o conține ca subordine. Acest lucru se datorează faptului că orice graf nedirecționat poate fi considerat direcționat, în care orice arc ( u , v ) apare împreună cu un arc invers ( v , u ), iar acest lucru nu schimbă definiția unui homomorfism. Ordinea graficelor direcționate este din nou o rețea distributivă și o algebră Heyting cu operațiile de unire și intersecție definite ca mai înainte. Cu toate acestea, această ordine nu este strictă. Există, de asemenea, o categorie cu grafuri direcționate ca obiecte și homomorfisme ca săgeți, care este din nou o categorie închisă carteziană [48] [47] . $\la$ $\la$ $\la$

Grafice incomparabile

Există multe grafuri incomparabile după ordinea prealabilă a homomorfismelor, adică perechi de grafuri astfel încât să nu existe homomorfisme de la unul la altul [49] . Una dintre modalitățile de a construi astfel de grafice este să luăm în considerare circumferința impară a graficului G , adică lungimea celui mai scurt ciclu de lungime impară al acestuia. O circumferință impară este, în mod echivalent, cel mai mic număr impar g pentru care există un homomorfism dintr -un grafic de ciclu cu g vârfuri la G . Din acest motiv, dacă , atunci circumferința impară a graficului G este mai mare sau egală cu circumferința impară a graficului H [50] . $G\la H$

Pe de altă parte, dacă , atunci numărul cromatic al graficului G este mai mic sau egal cu numărul cromatic al graficului H . Prin urmare, dacă un grafic G are o circumferință impară strict mai mare decât H și un număr cromatic strict mai mare decât [49]incomparabileHșiG, atunciH [51] , deci este incompatibil cu triunghiul K 3 . $G\la H$

Exemple de grafice cu valori arbitrar mari ale circumferinței impare și ale numărului cromatic sunt graficele Kneser [52] și Mychelskienii generalizați [53] . O succesiune de astfel de grafice cu o creștere simultană a valorilor ambilor parametri dă un număr infinit de grafice incomparabile ( un anticlanț în ordinea prealabilă a homomorfismelor) [54] . Alte proprietăți, cum ar fi densitatea preordinului de homomorfisme, pot fi dovedite folosind astfel de familii [55] . Construirea de grafice cu valori mari ale numărului cromatic și al circumferinței, mai degrabă decât doar circumferința impară, este de asemenea posibilă, dar mai dificilă (a se vedea circumferința și colorarea graficului ).

Este mult mai ușor să găsești perechi incomparabile printre graficele direcționate. De exemplu, luați în considerare graficele ciclului direcționat cu vârfuri 1, 2, …, n și muchii de la i la i + 1 (pentru i =1, 2, …, n − 1) și de la n la 1. Există un homomorfism de la la atunci și numai când n este un multiplu al lui k . În special, graficele ciclului direcționat cu prim n sunt toate incomparabile [56] . ${\vec {C}}_{n}$ ${\vec {C}}_{n}$ ${\vec {C}}_{k}(n,k\geqslant 3)$ ${\vec {C}}_{n}$

Complexitate computațională

În problema homomorfismului de graf, o instanță a problemei constă dintr-o pereche de grafuri ( G , H ), iar soluția este un homomorfism de la G la H. Problema generală de solubilitate , care întreabă dacă există o soluție la această problemă, este NP-complet [57] . Cu toate acestea, constrângerile grafice conduc la o serie de probleme diferite, dintre care unele sunt mai ușor de rezolvat. Metodele care folosesc restricții pe graficul din stânga G sunt foarte diferite de metodele folosite pe graficul din dreapta H , dar în fiecare caz dihotomia (limitele stricte între cazuri simple și complexe) este cunoscută sau asumată.

Omomorfisme la un graf fix

Problema homomorfismului cu un grafic fix H în partea dreaptă a fiecărei instanțe se numește problema de colorare a H. Când H este un grafic complet K k , aceasta este o problemă de colorare a graficului k care este rezolvabilă în timp polinomial pentru k =0, 1, 2 și este NP-complet în caz contrar [58] . În special, posibilitatea unei colorări K2 a unui grafic G este echivalentă cu graficul bipartit G , care poate fi verificat în timp liniar. Mai general, atunci când H este un graf bipartit, posibilitatea colorării H este echivalentă cu posibilitatea colorării K 2 (sau K 0 / K 1 -colorabil când H este gol sau nu are margini), și, prin urmare, la fel de ușor de rezolva [59] . Pavol Hell și Jaroslav Neshetril au demonstrat că niciun alt caz nu este ușor pentru graficele nedirecționate:

Teorema Hell-Neshetril (1990): O problemă de colorare H este în clasa P dacă H este bipartit și NP-hard în caz contrar [60] [61] .

Teorema este cunoscută și ca teorema de dihotomie pentru homomorfismul grafului (nedirecționat), deoarece împarte problemele de colorare H în probleme NP-complete și probleme de clasă P fără cazuri intermediare . Pentru graficele direcționate, situația este mai complicată și, de fapt, este echivalentă cu întrebarea mai generală de a descrie complexitatea satisfacerii constrângerilor [62] . Se dovedește că problemele de colorare H pentru graficele direcționate sunt la fel de generale și la fel de diverse ca și problemele de satisfacție a constrângerilor cu orice alte tipuri de constrângeri [63] [64] . Formal, un limbaj de constrângere (finit) Γ este un domeniu finit și un set finit de relații în acel domeniu. CSP( Γ ) este o problemă de satisfacție a constrângerilor în care instanțelor li se permite să utilizeze numai constrângeri din Γ .

Teorema (Feder, Vardy 1998): Pentru orice limbaj de constrângere Γ , CSP( Γ ) este echivalent după reducerea polinomială cu o problemă de H- colorare pentru un grafic dirijat H [64] .

Intuitiv, aceasta înseamnă că orice tehnică algoritmică sau rezultat de complexitate aplicabil problemelor de colorare H pentru graficele direcționate H se aplică și problemelor generale de satisfacție a constrângerilor. În special, s-ar putea întreba dacă teorema Hell-Neshetril poate fi extinsă la grafice direcționate. Prin teorema de mai sus, aceasta este echivalentă cu conjectura Feder-Vardi asupra dihotomiei problemelor de satisfacție a constrângerilor, care afirmă că pentru orice limbaj de constrângere Γ , CSP( Γ ) este fie NP-complet, fie aparține clasei P [57] .

Omomorfisme dintr-o familie fixă de grafice

Problema homomorfismului cu un grafic fix G din partea stângă poate fi rezolvată prin căutare exhaustivă în timp | V ( H )| O(| V ( G )|) , adică polinom în mărimea graficului de intrare H [65] . Cu alte cuvinte, problema este trivială în P pentru graficele G de mărime mărginită. O întrebare interesantă este atunci ce alte proprietăți ale graficului G în afară de dimensiune fac posibilă algoritmii polinomi.

Proprietatea cheie se dovedește a fi treewidth , o măsură a cât de asemănător este un grafic cu un arbore. Pentru un grafic G cu lățimea arborelui de cel mult k și un grafic H , problema homomorfismului poate fi rezolvată în timp | V ( H )| O( k ) prin metode standard de programare dinamică . De fapt, este suficient să presupunem că nucleul lui G are lățimea arborelui de cel mult k . Acest lucru este adevărat chiar dacă nucleul nu este cunoscut [66] [67] .

Indicator în algoritm cu timp de rulare| V ( H )| O( k ) nu poate fi redus semnificativ - nu există un algoritm care să ruleze în timp | V ( H )| o(tw( G ) /log tw( G )) dacă ipoteza timpului exponențial ( ETH) este adevărată, chiar dacă intrarea este limitată de orice clasă de grafice cu lățime nelimitată a arborelui [68] . ETH este o ipoteză nedovedită, similară cu ipoteza P ≠ NP , dar mai strictă. În aceleași ipoteze, nu există alte proprietăți care să poată fi utilizate pentru a deriva algoritmi de timp polinomial. Acest lucru este formalizat de teorema:

Teorema (Martin Grohe): Pentru o clasă calculabilă de grafice , problema de homomorfism pentru c aparține lui P dacă și numai dacă graficele au nuclee de lățime mărginită a arborelui (în ipoteza ETH) [67] .

{\mathcal {G}}

(G,H)

G\in {\mathcal {G}}

{\mathcal {G}}

Se poate întreba dacă problema este rezolvabilă cu o dependență arbitrar de mare de G , dar cu o dependență polinomială fixă de dimensiunea graficului H. Răspunsul este da dacă restricționăm graficul G la o clasă cu nuclee de lățime mărginită a arborelui și nu pentru toate celelalte clase [67] . În limbajul complexității parametrizate , această afirmație spune în mod formal că problema de homomorfism cu graph , parametrizată prin dimensiunea (numărul de muchii) lui G , arată o dihotomie. Este decidabil cu parametru fix dacă graficele din clasă au nuclee de lățime de arbore mărginită, iar W[1]-complete în caz contrar. ${\mathcal {G}}$ ${\mathcal {G}}$

Aceeași afirmație este valabilă pentru problemele de satisfacție cu constrângeri mai generale (sau, cu alte cuvinte, pentru structurile relaționale). Singura presupunere necesară este că constrângerile pot implica doar un număr limitat de variabile. Parametrul este atunci lățimea arborelui a graficului principal de constrângeri [68] .

Vezi și

Ipoteza Sidorenko

Note

↑ Iadul, Nešetřil, 2004 , p. 27.
↑ Iadul, Nešetřil, 2004 , p. 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 , Observația 2.3.
↑ Godsil, Royle, 2001 , p. 115.
↑ 1 2 Hell, Nešetřil, 2004 , p. 19.
↑ Hell, Nešetřil, 2004 , Propunerea 1.31.
↑ Cameron, 2006 , Propunerea 2.3.
↑ Iadul, Nešetřil, 2004 , Corolarul 1.32.
↑ Iadul, Nešetřil, 2004 , p. 34.
↑ Cameron, 2006 , p. 4 (Propunerea 2.5).
↑ 1 2 3 4 Cameron, 2006 , p. unu.
↑ 1 2 Hell, Nešetřil, 2004 , Propunerea 1.7.
↑ 1 2 Hell, Nešetřil, 2004 , §1.7.
↑ Iadul, Nešetřil, 2004 , Corolarul 1.8.
↑ Iadul, Nešetřil, 2004 , §6.1.
↑ Gena, Tardif, 1997 , §4.4.
↑ Iadul, Nešetřil, 2004 , §6.2.
↑ Gena, Tardif, 1997 , §4.5.
↑ Iadul, Nešetřil, 2004 , §6.3.
↑ Iadul, Nešetřil, 2004 , §6.4.
↑ * Fiala J., Kratochvíl J. Partial covers of graphs // Discuții Mathematicae Graph Theory. - 2002. - T. 22 , nr. 1 . — S. 89–99 . - doi : 10.7151/dmgt.1159 .
↑ Iadul, Nešetřil, 2004 , p. 13–14.
↑ Hell, Nešetřil, 2004 , Propunerea 1.20.
↑ Iadul, Nešetřil, 2004 , §1.8.
↑ Iadul, Nešetřil, 2004 , p. 30–31.
↑ Iadul, Nešetřil, 2004 , p. 31–32.
↑ Iadul, Nešetřil, 2004 , p. 28. Rețineți că structurile relaționale din articol sunt numite sisteme relaționale .
↑ Amintiți-vă că, de obicei, muchiile unui graf direcționat se numesc arce.
↑ Iadul, Nešetřil, 2004 , §3.1.
↑ Hell, Nešetřil, 2004 , Teorema 3.1.
↑ Iadul, Nešetřil, 2004 , Teorema 3.30.
↑ Geňa, Tardif, 1997 , Teorema 2.33.
↑ Welzl, 1982 , p. 29–41.
↑ Iadul, Nešetřil, 2004 , p. 192.
↑ Gena, Tardif, 1997 , p. 127.
↑ Hell, Nešetřil, 2004 , Propunerea 3.2, distributivitatea este menționată în Propunerea 2.4.
↑ Geňa, Tardif, 1997 , Teorema 2.37.
↑ Kwuida, Lehtonen, 2011 , p. 251–265.
↑ Gray, 2014 , Lema 3.7.
↑ Tardif, 2008 , p. 46–57.
↑ 1 2 3 Dwight, Sauer, 1996 , p. 125–139.
↑ Iadul, Nešetřil, 2004 , p. 125.
↑ 1 2 3 Gray, 2014 .
↑ Brown, Morris, Shrimpton, Wensley, 2008 .
↑ 1 2 Hell, Nešetřil, 2004 , p. 7.
↑ Gena, Tardif, 1997 , Observația 2.6.
↑ Weisstein, Eric W. Grötzsch Graph pe site- ul Wolfram MathWorld .
↑ Gena, Tardif, 1997 , Propunerea 3.14.
↑ Gyárfás, Jensen, Stiebitz, 2004 , p. 1–14.
↑ Hell, Nešetřil, 2004 , Propunerea 3.4.
↑ Iadul, Nešetřil, 2004 , p. 96.
↑ Iadul, Nešetřil, 2004 , p. 35.
↑ 1 2 Bodirsky, 2007 , §1.3.
↑ Iadul, Nešetřil, 2004 , §5.1.
↑ Hell, Nešetřil, 2004 , Propunerea 5.1.
↑ Iadul, Nešetřil, 2004 , §5.2.
↑ Iadul, Nešetřil, 1990 , p. 92–110.
↑ Iadul, Nešetřil, 2004 , §5.3.
↑ Iadul, Nešetřil, 2004 , Teorema 5.14.
↑ 1 2 Feder, Vardi, 1998 , p. 57–104.
↑ Cygan, Fomin, Golovnev et al., 2016 , p. 1643–1649
↑ Dalmau, Kolaitis, Vardi, 2002 , p. 310–326.
↑ 1 2 3 Grohe, 2007 .
↑ 12 Marx , 2010 , p. 85–112.

Literatură

Welzl E. Familiile de culoare sunt dense // Teoretă. Calculator. sci. . - 1982. - T. 17 . — p. 29–41 . - doi : 10.1016/0304-3975(82)90129-3 .
Pavol Hell, Jaroslav Nesetzil. Despre complexitatea colorării H // JCTB . - 1990. - T. 48 , nr. 1 . — S. 92–110 . - doi : 10.1016/0095-8956(90)90132-J .
Gyárfás A., Jensen T., Stiebitz M. On Graphs With Strongly Independent Color-Class // J. Teoria graficelor . - 2004. - T. 46 , nr. 1 . — S. 1–14 . - doi : 10.1002/jgt.10165 .

Leonard Kwuida, Erkko Lehtonen. Despre Ordinul Homomorfismului Posetelor Etichetate // Ordinea . - Springer, 2011. - T. 28 , nr. 2 . — S. 251–265 . - doi : 10.1007/s11083-010-9169-x . - arXiv : 0911.0200 .
Conjectura lui Tardif C. Hedetniemi, 40 de ani mai târziu // Graph Theory Notes of New York. - 2008. - T. 54 . — p. 46–57 .
Dwight D., Sauer N. Lattices aparing in categorial investigations of Hedetniemi's conjecture // Discrete Math. . - 1996. - T. 152 , nr. 1-3 . — S. 125–139 . - doi : 10.1016/0012-365X(94)00298-W .
Daniel Marx. Poți învinge Treewidth? // Teoria calculului . - 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. Tight bounds for graph homomorphism and subgraf isomorphism. - SIAM , 2016. - ISBN 978-1-611974-33-1 .
Victor Dalmau, Phokion G. Kolaitis, Moshe Y. Vardi. Satisfacția constrângerii, lățimea arborelui delimitată și logica cu variabile finite. - 2002. - S. 310-326. - doi : 10.1007/3-540-46135-3_21 .
Martin Grohe. Complexitatea homomorfismului și a problemelor de satisfacție a constrângerilor văzute din cealaltă parte // J. ACM . - 2007. - T. 54 , nr. 1 . - doi : 10.1145/1206035.1206036 .
Tomás Feder, Moshe Y. Vardi . Structura computațională a SNP monadic monoton și satisfacția constrângerilor: un studiu prin datalog și teoria grupurilor // SIAM J. Comput. . - 1998. - T. 28 , nr. 1 . — p. 57–104 . - doi : 10.1137/S0097539794266766 .

Cărți generale

Peter Cameron. Omomorfisme grafice, note grupului de studiu combinatorică . — 2006.
Pavol Hell, Jaroslav Nesetzil. Grafice și homomorfisme . - Oxford University Press, 2004. - V. 28 . — ISBN 0-19-852817-5 .
Geňa H., Tardif C. Omomorfisme de graf : structură și simetrie // Graph Symmetry: Algebraic Methods and Applications . - Springer, 1997. - S. 107-166. - doi : 10.1007/978-94-015-8937-6_4 .
Chris Godsil, Gordon Royle. 6. Omomorfisme // Teoria graficelor algebrice. - Springer-Verlag New York, 2001. - T. 207. - (Texte de absolvire în matematică). — ISBN 978-1-4613-0163-9 . - doi : 10.1007/978-1-4613-0163-9 .

În algebra universală și supus constrângerilor

Bodirsky M. Omomorfisme grafice și algebră universală, Note de curs . — 2007.
Pavol Hell, Jaroslav Nesetzil. Colorare, satisfacție cu constrângeri și complexitate // Computer Science Review. - 2008. - Vol. 2 , numărul. 2 . — S. 143–163 . - doi : 10.1016/j.cosrev.2008.10.003 .

În teoria rețelelor și teoria categoriilor

Brown R., Morris I., Shrimpton J., Wensley CD Graphs of morphisms of graphs // Electronic Journal of Combinatorics . - 2008. - T. 15 , nr. 1 . - S. A1 .
Grey CT The Digraph Lattice . — 2014. ( AMSI Vacation Research Scholarships , raport de cercetare al studenților supravegheat de Brian Davey și Jane Pitkethly, Universitatea La Trobe ).