Homomorfismus grafu

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 14. října 2021; kontroly vyžadují 2 úpravy .

Homomorfismus grafu je zobrazení mezi dvěma grafy , které nenarušuje strukturu. Přesněji se jedná o mapování mezi sadou vrcholů dvou grafů, které mapuje sousední vrcholy na sousední.

Homomorfismy zobecňují různé představy o zbarvení grafů a umožňují vyjádření důležitých tříd problémů s uspokojením omezení , jako jsou některé problémy s plánováním nebo problémy s přidělováním rádiových frekvencí [1] . Skutečnost, že homomorfismy mohou být použity sekvenčně, vede k bohatým algebraickým strukturám - předřazení na grafech, distributivní mřížce a kategoriích (jedna pro neorientované grafy a jedna pro orientované grafy) [2] . Výpočetní složitost nalezení homomorfismu mezi danými grafy je obecně neúnosná, ale je známo mnoho speciálních případů, kdy je úloha proveditelná v polynomiálním čase . Hranice mezi řešitelnými a nepřekonatelnými případy jsou v oblasti aktivního výzkumu [3] .

Definice

Pokud není v tomto článku uvedeno jinak, grafy znamenají konečné neorientované grafy s povolenými smyčkami , ale více (paralelních) hran není povoleno. Homomorfismus grafu [4] [5] [6] : f z grafu do grafu , který se zapisuje jako $G=(V(G),E(G))$ $H=(V(H),E(H))$

f:G\to H

je funkce od V ( G ) do V ( H ) , která mapuje koncové body každé hrany z G do koncových bodů některé hrany z H . Formálně to vyplývá z , pro všechny dvojice vrcholů u , v z V ( G ). Pokud existuje nějaký homomorfismus od G do H , pak se o grafu G říká, že je homomorfní s grafem H nebo že je H- barvitelný . To je často označováno jako $\{u,v\}\in E(G)$ $\{f(u),f(v)\}\in E(H)$

G\to H

Výše uvedená definice se vztahuje na orientované grafy. Pak pro homomorfismus je oblouk (orientovaná hrana) grafu H , když ( u , v ) je oblouk grafu G. $f:G\to H,(f(u),f(v))$

Existuje injektivní homomorfismus od G do H (tj. mapa, která nikdy nemapuje různé vrcholy na jeden jediný) právě tehdy, když G je podgraf H . Je-li homomorfismus bijekce ( korespondence jedna ku jedné mezi vrcholy G a H ) , jejíž inverzní funkce je také homomorfismus grafu, pak f je izomorfismus grafu [7] . $f:G\to H$

Zobrazení pokrytí jsou běžným typem homomorfismu, který odráží definici a mnoho vlastností pokrytí v topologii [8] . Jsou definovány jako surjektivní homomorfismy, které jsou lokálně bijektivní, tj. bijekce v okolí každého vrcholu. Příkladem je dvojité krytí bipartitním grafem vytvořeným z grafu rozdělením každého vrcholu v na a a nahrazením každé hrany u , v dvěma hranami a . Funkce zobrazení v 0 a v 1 až v původního grafu je homomorfismus a krycí zobrazení. $v_{0}$ $v_{1}$ $u_{0},v_{1}$ ${\displaystyle v_{0},u_{1))$

Homeomorfismus grafu je samostatný koncept, který přímo nesouvisí s homomorfismy. Zhruba řečeno, vyžaduje injektivitu, ale umožňuje mapování hran na cesty (spíše než jen hrany). Slabším pojmem zůstávají nezletilí .

Jádra a stažení

Dva grafy G a H jsou homomorfně ekvivalentní , jestliže a [4] [5] [6] . $G\to H$ $H\to G$

Retrakce je homomorfismus r z G do podgrafu H G tak, že r ( v ) = v pro každý vrchol v H . V tomto případě se podgraf H nazývá retrakt grafu G [9] .

Jádro je graf, který nemá homomorfismus k žádnému správnému podgrafu. Ekvivalentně může být jádro definováno jako graf, který není retract pro žádný správný podgraf [10] . Libovolný graf G je homomorfně ekvivalentní jedinečnému jádru (až do izomorfismu), které se nazývá jádro grafu G [11] [12] . Všimněte si, že to neplatí pro obecné nekonečné grafy [13] . Stejné definice však platí pro orientované grafy a orientovaný graf je také ekvivalentní jedinému jádru. Jakýkoli neorientovaný a řízený graf obsahuje své jádro jak jako stažení, tak jako vygenerovaný podgraf [9] .

Například všechny úplné grafy Kn a všechny liché cykly ( grafy cyklů liché délky) jsou jádra. Nějaký 3-barevný graf G , který obsahuje trojúhelník (to je, má kompletní graf K 3 jako podgraf) je homeomorphically ekvivalentní k K 3 . Je to proto, že na jedné straně je 3-barevné zbarvení grafu G stejné jako homomorfismus , jak je vysvětleno níže. Na druhé straně každý podgraf G triviálně připouští homomorfismus k G , z čehož plyne, že . To také znamená, že K 3 je jádrem každého takového grafu G . Podobně každý bipartitní graf , který má alespoň jednu hranu, je ekvivalentní K 2 [14] . $G\to K_{3}$ $K_{3}\to G$

Vztah s omalovánkami

K -zabarvení pro nějaké celé číslo k je přiřazení jedné z k barev každému vrcholu grafu G tak, že koncové vrcholy každé hrany mají různé barvy. k -Zabarvení grafu G přesně odpovídá homomorfismům od G po úplný graf K k [15] [16] . Navíc vrcholy grafu K k odpovídají k barvám a dvě barvy sousedí jako vrcholy grafu K k právě tehdy, jsou-li různé. Funkce tedy definuje homomorfismus v K k právě tehdy, když jsou sousední vrcholy grafu G obarveny různými barvami. Konkrétně graf G je k - obarvitelnýprávě tehdy, když je Kk - obarvitelný [15] [16] .

Pokud existují dva homomorfismy a , pak jejich superpozice je také homomorfismem [17] . Jinými slovy, pokud graf H může být obarven k barvami a existuje homomorfismus G do H , pak G může být také obarven k barvami. Vyplývá to tedy z , kde znamená chromatické číslo grafu (nejmenší počet barev k , ve kterých lze graf vybarvit) [18] . $G\to H$ ${\displaystyle H\to K_{k))$ ${\displaystyle G\to K_{k))$ $G\to H$ $\chi (G)\leqslant \chi (H)$ $\chi$

Možnosti

Obecné homomorfismy lze také považovat za druh zbarvení - pokud vrcholy pevného grafu H mají povolené barvy a okraje grafu H popisují, které barvy jsou kompatibilní , pak je zabarvení grafu G přiřazeno barvy k vrcholům grafu G tak, aby sousední vrcholy obdržely kompatibilní barvy. Mnoho pojmů zbarvení grafů zapadá do tohoto schématu a lze je vyjádřit jako homomorfismy grafů do různých rodin grafů. Zbarvení cyklu lze definovat pomocí homomorfismů pro cyklování kompletních grafů , čímž se zjemní obvyklá představa o zbarvení [19] [20] . Zlomkové a b - násobné zbarvení lze definovat pomocí homomorfismů ke Kneserovým grafům [21] [22] T-zabarvení odpovídá homomorfismům k některým nekonečným grafům [23] . { Orientované zbarvení orientovaného grafu je homomorfismus k libovolnému orientovanému grafu [24] . L(2,1)-coloring je lokálně injektivní homomorfismus v doplňku cesty , což znamená, že musí být injektivní v okolí každého vrcholu [25] .

Orientace bez dlouhých cest

Další zajímavá souvislost se týká orientace grafů. Orientace neorientovaného grafu G je jakýkoli orientovaný graf získaný výběrem ze dvou možných orientací pro každou hranu. Příkladem orientace úplného grafu K k je tranzitivní turnaj s vrcholy 1,2,…, k a oblouky od i do j , když i < j . Homomorfismus mezi orientacemi grafů G a H dává homomorfismus mezi neorientovanými grafy G a H , pokud orientace jednoduše ignorujeme. Na druhou stranu, vzhledem k homomorfismu mezi neorientovanými grafy, jakákoliv orientace H může být mapována na orientaci grafu G , takže má homomorfismus v . Proto je graf G k -obarvitelný (má homomorfismus v K k ) právě tehdy, když některá orientace G má homomorfismus v [26] . ${\vec {T}}_{k}$ $G\to H$ ${\vec {H}}$ ${\vec {G}}$ ${\vec {G}}$ ${\vec {H}}$ ${\vec {T}}_{k}$

Folklórní teorém říká, že pro libovolné k má směrovaný graf G homomorfismus právě tehdy, když nepřipouští homomorfismus z [27] . Zde je orientovaná cesta s vrcholy 1, 2, …, n a oblouky od i do i + 1 pro i =1, 2, …, n − 1. Graf je tedy k - obarvitelný právě tehdy, když má orientace , která nepřipouští homomorfismus z . Toto tvrzení lze mírně posílit tím, že graf je k -obarvitelný právě tehdy, když některá orientace neobsahuje směrovanou cestu délky k (ne jako podgraf). Toto je Gallai-Hasse-Roy-Vitaverova věta . ${\vec {T}}_{k}$ ${\vec {P}}_{k+1}$ ${\vec {P}}_{n}$ ${\vec {P}}_{k+1}$ ${\vec {P}}_{k+1}$

Vztah k problémům s uspokojením omezení

Příklady

Některé problémy plánování lze modelovat jako otázku hledání homomorfismů grafů [15] [28] . Jako příklad lze zkusit naplánovat cvičení tak, aby dva kurzy navštěvované stejným studentem nebyly časově příliš blízko. Kurzy tvoří graf G s hranami mezi dvěma kurzy, pokud je navštěvuje stejný student. Možný čas vedení kursů tvoří graf H s hranami mezi dvěma časovými okny, pokud je časová vzdálenost mezi nimi dostatečně velká. Například, pokud chceme mít cyklický týdenní rozvrh tak, aby každý student chodil cvičit každý druhý den, pak by sloupec H byl doplňkem sloupce C 7 . Homomorfismus grafu z G do H je pak přiřazení průběhů v časových oknech [15] . Chcete-li přidat požadavek, řekněme, že žádný student nemá hodinu v pátek i v pondělí, stačí odstranit jednu hranu z grafu H .

Jednoduchý problém rozdělení frekvence lze formulovat následovně. Existuje několik bezdrátových síťových vysílačů . Na každém z nich musíte vybrat frekvenční kanál, přes který bude přenášet data. Aby se zabránilo rušení , geograficky blízké vysílače musí mít kanály s dostatečně odlišnými frekvencemi. Pokud je tato podmínka omezena na jednoduchý práh pro pojmy „geograficky blízko“ a „dostatečně daleko“, platná volba kanálů opět odpovídá homomorfismu grafu. Zde bude graf G množina vysílačů s hranami mezi nimi, pokud jsou geograficky blízko, a graf H bude množina kanálů s hranami mezi kanály, pokud jsou frekvence dostatečně odlišné. I když je tento model značně zjednodušený, umožňuje určitou flexibilitu – pro dvojici vysílačů, které nejsou blízko, ale mohou se vzájemně rušit kvůli geografickým vlastnostem, lze přidat oblouk v G . A oblouk mezi vysílači, které nefungují současně, lze z grafu odstranit. Podobně lze z H grafu odstranit hranu mezi dvojicí kanálů, které jsou daleko od sebe, ale mají harmonickou interferenci [29] .

V každém případě tyto zjednodušené modely vykazují mnoho funkcí, které by měly být v praxi vypracovány [30] . Problémy uspokojení omezení , které zobecňují problémy s homomorfismem grafů, mohou vyjadřovat další typy podmínek (jako jsou individuální preference nebo omezení počtu odpovídajících přiřazení). Díky tomu jsou modely realističtější a praktičtější.

Formální hledisko

Nasměrované a orientované grafy lze považovat za časté příklady obecnějšího konceptu zvaného relační struktury které jsou definovány jako množina s n-ticí relací). Orientované grafy jsou struktury s jednou binární relací (sousedností) na doméně (množině vrcholů) [31] [3] . Z tohoto pohledu jsou homomorfismy takových struktur přesně grafové homomorfismy. V obecném případě je otázka nalezení homomorfismu z jedné struktury do druhé problémem uspokojení omezení ( CSP) . Případ grafů poskytuje konkrétní první krok, který pomáhá porozumět složitějším problémům uspokojení omezení. Mnoho algoritmických metod pro hledání homomorfismů grafů, jako je backtracking , šíření omezení a lokální vyhledávání , lze použít na všechny problémy se splněním omezení [3] .

Pro grafy G a H odpovídá otázka, zda má graf G homomorfismus ke grafu H konkrétnímu případu problému uspokojení omezení pouze s jedním druhem omezení [3] . V tomto problému budou proměnné vrcholy grafu G a rozsah každé proměnné bude množina vrcholů grafu H. Řešením je funkce, která každé proměnné přiřadí prvek z rozsahu, takže funkce f mapuje V ( G ) na V ( H ). Každá hrana nebo oblouk [32] ( u , v ) grafu G pak odpovídá omezení (( u , v ), E( H )). Toto omezení vyjadřuje, že řešení musí namapovat oblouk ( u , v ) na dvojici ( f ( u ), f ( v )), což je vztah E ( H ), tedy k oblouku grafu H . Řešením problému je řešení, které splňuje všechna omezení, to znamená, že jde přesně o homomorfismus z G do H .

Struktura homomorfismů

Superpozice homomorfismů jsou homomorfismy [17] . Konkrétně relace na grafech je tranzitivní (a triviálně reflexivní), takže tato relace je předřadí na grafech [33] . Třídu ekvivalence homomorfismu grafu G budeme označovat [ G ]. Třída ekvivalence může být reprezentována jedním jádrem v [ G ]. Vztah je částečně uspořádán na těchto třídách ekvivalence. Definuje částečně uspořádanou množinu [34] . $\na$ $\na$

Nechť G < H znamená, že existuje homomorfismus z G do H , ale žádný homomorfismus z H do G . Relace je hustého řádu , což znamená, že pro všechny (neorientované) grafy G , H takové, že G < H existuje graf K takový, že G < K < H (to platí ve všech případech kromě triviálních případů nebo ) [35] [36] [37] . Například mezi libovolnými dvěma úplnými grafy (kromě ) je nekonečně mnoho cyklických úplných grafů odpovídajících racionálním číslům [38] [39] . $\na$ ${\displaystyle G=K_{0))$ $K_1$ ${\displaystyle K_{0},K_{1))$

Částečně uspořádaná množina tříd ekvivalence grafů podle homomorfismu je distributivní svaz , se sjednocením [ G ] a [ H ] definovaným jako (třída ekvivalence) disjunktním sjednocením a průnikem [ G ] a [ H ] definovaný jako tenzorový součin (na volbě grafů G a H jako zástupců tříd ekvivalence [ G ] a [ H ] nezáleží) [40] [41] . Prvky této mřížky, které jsou ve svazku neredukovatelné , jsou přesně spojené grafy. To lze ukázat pomocí skutečnosti, že homomorfismus mapuje souvislý graf na souvislou komponentu cílového grafu [42] [43] . Průnikově neredukovatelné prvky této mřížky jsou přesně multiplikativní grafy . Jedná se o grafy K takové, že součin má homomorfismus v K pouze tehdy, pokud jeden z grafů G nebo H takový homomorfismus má. Objev multiplikativních grafů je jádrem Hedetniemiho domněnky [44] [45] . $[G\cup H]$ $[G\times H]$ $G\krát H$

Homomorfismy grafů také tvoří kategorii s grafy jako objekty a homomorfismy jako šipkami [46] . Počáteční objekt je prázdný graf, zatímco koncový objekt je graf s jedním vrcholem a jednou smyčkou v tomto vrcholu. Tenzorový součin grafů je součin v teorii kategorií a exponenciální graf je exponenciální objekt pro kategorii [45] [47] . Protože tyto dvě operace jsou vždy definovány, kategorie grafů je kartézská uzavřená kategorie . Ze stejných důvodů je mřížka tříd grafové ekvivalence podle homomorfismů ve skutečnosti Heytingova algebra [45] [47] .

Pro orientované grafy platí stejné definice. Zejména je částečně uspořádán na třídách ekvivalence orientovaných grafů. Toto pořadí se liší od pořadí na třídách ekvivalence neorientovaných grafů, ale obsahuje jej jako podřád. Je to proto, že každý neorientovaný graf může být považován za směrovaný, ve kterém se jakýkoli oblouk ( u , v ) objeví spolu s inverzním obloukem ( v , u ), a to nemění definici homomorfismu. Pořadí pro orientované grafy je opět distributivní svaz a Heytingova algebra se sjednocovacími a průnikovými operacemi definovanými jako dříve. Toto pořadí však není těsné. Existuje také kategorie s orientovanými grafy jako objekty a homomorfismy jako šipkami, což je opět kartézská uzavřená kategorie [48] [47] . $\na$ $\na$ $\na$

Nesrovnatelné grafy

Existuje mnoho nesrovnatelných grafů podle předřadí homomorfismů, tedy dvojic grafů, u kterých neexistují žádné homomorfismy z jednoho do druhého [49] . Jedním ze způsobů, jak sestavit takové grafy, je uvažovat lichý obvod grafu G , tedy délku jeho nejkratšího cyklu liché délky. Lichý obvod je ekvivalentně nejmenší liché číslo g , pro které existuje homomorfismus z grafu cyklu s g vrcholy do G . Z tohoto důvodu, jestliže , pak je lichý obvod grafu G větší nebo roven lichému obvodu grafu H [50] . $G\to H$

Na druhou stranu, je-li , pak je chromatické číslo grafu G menší nebo rovno chromatickému číslu grafu H . Pokud má tedy graf G striktně větší lichý obvod než H a striktně větší chromatické [49]nesrovnatelnéHaG, pakHčíslo než [51] , takže je nekompatibilní s grafem trojúhelník K3 . _ $G\to H$

Příklady grafů s lichými hodnotami obvodu a chromatického čísla jsou Kneserovy grafy [52] a zobecněné mychelské [53] . Posloupnost takových grafů při současném zvýšení hodnot obou parametrů dává nekonečné množství nesrovnatelných grafů ( antiřetězec v předřadí homomorfismů) [54] . Další vlastnosti, jako je hustota předřadí homomorfismů, lze dokázat pomocí takových rodin [55] . Sestavení grafů s velkými hodnotami chromatického čísla a obvodu, spíše než jen s lichým obvodem, je také možné, ale obtížnější (viz Obvod a vybarvení grafu ).

Mezi orientovanými grafy je mnohem snazší najít nesrovnatelné dvojice. Uvažujme například grafy orientovaného cyklu s vrcholy 1, 2, …, n a hranami od i do i + 1 (pro i =1, 2, …, n − 1) a od n do 1. Existuje homomorfismus od do tehdy a pouze tehdy, když n je násobkem k . Zejména grafy orientovaného cyklu s prvočíslem n jsou všechny nesrovnatelné [56] . ${\vec {C}}_{n}$ ${\vec {C}}_{n}$ ${\vec {C}}_{k}(n,k\geqslant 3)$ ${\vec {C}}_{n}$

Výpočetní složitost

V problému homomorfismu grafu se instance problému skládá z dvojice grafů ( G , H ) a řešením je homomorfismus z G do H. Obecný problém řešitelnosti , který se ptá, zda existuje řešení tohoto problému, je NP-úplný [57] . Omezení grafů však vedou k řadě různých problémů, z nichž některé je snazší vyřešit. Metody, které používají omezení na levém grafu G , se velmi liší od metod používaných na pravém grafu H , ale v každém případě je známa nebo předpokládána dichotomie (přísné hranice mezi jednoduchými a komplexními případy).

Homomorfismy k pevnému grafu

Problém homomorfismu s pevným grafem H na pravé straně každé instance se nazývá problém H -barvování. Když H je úplný graf K k , jedná se o problém zabarvení grafu k , který je řešitelný v polynomiálním čase pro k =0, 1, 2 a jinak je NP-úplný [58] . Zejména možnost K2 - zabarvení grafu G je ekvivalentní bipartitnímu grafu G , což lze ověřit v lineárním čase. Obecněji, když H je bipartitní graf, možnost H- zabarvení je ekvivalentní možnosti K2 -zabarvení (nebo K 0 / K1 - zabarvitelné , když je H prázdné nebo nemá žádné okraje), a proto je stejně snadné vyřešit [59] . Pavol Hell a Jaroslav Neshetril dokázali, že žádný jiný případ není pro neorientované grafy snadný:

Hell-Neshetril teorém (1990): Problém zbarvení H je ve třídě P, pokud je H bipartitní a NP-tvrdé jinak [60] [61] .

Věta je také známá jako dichotomická věta pro (nenasměrovaný) homomorfismus grafu, protože rozděluje problémy s H- barvením na NP-úplné a problémy třídy P bez přechodných případů. U orientovaných grafů je situace složitější a ve skutečnosti je ekvivalentní obecnější otázce popisu složitosti uspokojování omezení [62] . Ukazuje se, že problémy s H- barvením pro orientované grafy jsou stejně obecné a stejně rozmanité jako problémy s uspokojením omezení s jinými druhy omezení [63] [64] . Formálně je (konečný) jazyk omezení Γ konečnou doménou a konečnou množinou relací v této oblasti. CSP( Γ ) je problém uspokojování omezení, kde je instancím povoleno používat pouze omezení z Γ .

Věta (Feder, Vardy 1998): Pro jakýkoli omezující jazyk Γ je CSP( Γ ) po polynomiální redukci ekvivalentní k nějakému problému H- barvení pro nějaký orientovaný graf H [64] .

Intuitivně to znamená, že jakákoliv algoritmická technika nebo výsledek složitosti aplikovatelný na H- barvicí problémy pro orientované grafy H platí také pro obecné problémy s uspokojením omezení. Zejména bychom se mohli ptát, zda lze Hell-Neshetrilův teorém rozšířit na orientované grafy. Podle výše uvedené věty je to ekvivalentní Feder-Vardiho domněnce o dichotomii problémů s omezením, která říká, že pro jakýkoli jazyk omezení Γ je CSP( Γ ) buď NP-úplný, nebo patří do třídy P [57] .

Homomorfismy z pevné rodiny grafů

Problém homomorfismu s jedním pevným grafem G na levé straně lze vyřešit vyčerpávajícím hledáním v čase | V ( H )| O(| V ( G )|) , tedy polynom ve velikosti vstupního grafu H [65] . Jinými slovy, problém je v P pro grafy G omezené velikosti triviální. Zajímavou otázkou pak je, jaké další vlastnosti grafu G kromě velikosti umožňují polynomiální algoritmy.

Ukázalo se, že klíčovou vlastností je treewidth , míra podobnosti grafu se stromem. Pro graf G se šířkou stromu nejvýše k a graf H lze problém homomorfismu vyřešit v čase | V ( H )| O( k ) standardními metodami dynamického programování . Ve skutečnosti stačí předpokládat, že jádro G má šířku stromu nejvýše k . To platí i v případě, že jádro není známé [66] [67] .

Indikátor v algoritmu s dobou běhu| V ( H )| O( k ) nelze výrazně snížit - neexistuje algoritmus, který běží v čase | V ( H )| o(tw( G ) /log tw( G )) , pokud je exponenciální časová hypotéza ( ETH) pravdivá, i když je vstup omezen libovolnou třídou grafů neomezené šířky stromu [68] . ETH je neprokázaný předpoklad, podobný předpokladu P ≠ NP , ale přísnější. Za stejných předpokladů neexistují žádné další vlastnosti, které lze použít k odvození polynomiálních časových algoritmů. To je formalizováno větou:

Věta (Martin Grohe): Pro vyčíslitelnou třídu grafů patří problém homomorfismu pro c do P právě tehdy, když grafy mají jádra s omezenou šířkou stromu (v předpokladu ETH) [67] .

{\mathcal {G}}

(G,H)

G\in {\mathcal {G}}

{\mathcal {G}}

Lze se ptát, zda je problém řešitelný s libovolně vysokou závislostí na G , ale s pevnou polynomickou závislostí na velikosti grafu H. Odpověď zní ano, pokud omezíme graf G na třídu s jádry s omezenou šířkou stromu, a ne na všechny ostatní třídy [67] . V jazyce parametrizované složitosti toto tvrzení formálně říká, že problém homomorfismu s grafem , parametrizovaný velikostí (počtem hran) G , ukazuje dichotomii. Je rozhoditelné s pevnými parametry , pokud grafy ve třídě mají jádra s omezenou šířkou stromu, a jinak W[1]-complete . ${\mathcal {G}}$ ${\mathcal {G}}$

Totéž platí pro obecnější problémy s uspokojením omezení (nebo jinými slovy pro relační struktury). Jediným požadovaným předpokladem je, že omezení mohou zahrnovat pouze omezený počet proměnných. Parametr je pak treewidth grafu hlavního omezení [68] .

Viz také

Hypotéza Sidorenko

Poznámky

↑ Peklo, Nešetřil, 2004 , str. 27.
↑ Peklo, Nešetřil, 2004 , str. 109.
↑ 1 2 3 4 Peklo, Nešetřil, 2008 .
↑ 12 Cameron , 2006 .
↑ 1 2 Geňa, Tardif, 1997 .
↑ 1 2 Peklo, Nešetřil, 2004 .
↑ Gena, Tardif, 1997 , Pozorování 2.3.
↑ Godsil, Royle, 2001 , str. 115.
↑ 1 2 Peklo, Nešetřil, 2004 , str. 19.
↑ Peklo, Nešetřil, 2004 , Tvrzení 1.31.
↑ Cameron, 2006 , Propozice 2.3.
↑ Peklo, Nešetřil, 2004 , Důsledek 1.32.
↑ Peklo, Nešetřil, 2004 , str. 34.
↑ Cameron, 2006 , str. 4 (Návrh 2.5).
↑ 1 2 3 4 Cameron, 2006 , str. jeden.
↑ 1 2 Peklo, Nešetřil, 2004 , Tvrzení 1.7.
↑ 1 2 Peklo, Nešetřil, 2004 , §1.7.
↑ Peklo, Nešetřil, 2004 , Důsledek 1.8.
↑ Peklo, Nešetřil, 2004 , §6.1.
↑ Gena, Tardif, 1997 , §4.4.
↑ Peklo, Nešetřil, 2004 , §6.2.
↑ Gena, Tardif, 1997 , §4.5.
↑ Peklo, Nešetřil, 2004 , §6.3.
↑ Peklo, Nešetřil, 2004 , §6.4.
↑ * Fiala J., Kratochvíl J. Částečné kryty grafů // Diskuze Mathematicae Graph Theory. - 2002. - T. 22 , no. 1 . — S. 89–99 . - doi : 10.7151/dmgt.1159 .
↑ Peklo, Nešetřil, 2004 , str. 13–14.
↑ Peklo, Nešetřil, 2004 , Tvrzení 1.20.
↑ Peklo, Nešetřil, 2004 , §1.8.
↑ Peklo, Nešetřil, 2004 , str. 30–31.
↑ Peklo, Nešetřil, 2004 , str. 31–32.
↑ Peklo, Nešetřil, 2004 , str. 28. Všimněte si, že relační struktury v článku se nazývají relační systémy .
↑ Připomeňme, že hrany orientovaného grafu se obvykle nazývají oblouky.
↑ Peklo, Nešetřil, 2004 , §3.1.
↑ Peklo, Nešetřil, 2004 , Věta 3.1.
↑ Peklo, Nešetřil, 2004 , Věta 3.30.
↑ Geňa, Tardif, 1997 , Věta 2.33.
↑ Welzl, 1982 , str. 29–41.
↑ Peklo, Nešetřil, 2004 , str. 192.
↑ Gena, Tardif, 1997 , str. 127.
↑ Hell, Nešetřil, 2004 , Tvrzení 3.2, distributivita je uvedena v Tvrzení 2.4.
↑ Geňa, Tardif, 1997 , Věta 2.37.
↑ Kwuida, Lehtonen, 2011 , str. 251–265.
↑ Gray, 2014 , Lemma 3.7.
↑ Tardif, 2008 , str. 46–57.
↑ 1 2 3 Dwight, Sauer, 1996 , str. 125–139.
↑ Peklo, Nešetřil, 2004 , str. 125.
↑ 1 2 3 Šedá, 2014 .
↑ Brown, Morris, Shrimpton, Wensley, 2008 .
↑ 1 2 Peklo, Nešetřil, 2004 , str. 7.
↑ Gena, Tardif, 1997 , Pozorování 2.6.
↑ Weisstein, Eric W. Grötzsch Graf na webu Wolfram MathWorld .
↑ Gena, Tardif, 1997 , Propozice 3.14.
↑ Gyárfás, Jensen, Stiebitz, 2004 , str. 1–14.
↑ Peklo, Nešetřil, 2004 , Tvrzení 3.4.
↑ Peklo, Nešetřil, 2004 , str. 96.
↑ Peklo, Nešetřil, 2004 , str. 35.
↑ 1 2 Bodirsky, 2007 , §1.3.
↑ Peklo, Nešetřil, 2004 , §5.1.
↑ Peklo, Nešetřil, 2004 , Tvrzení 5.1.
↑ Peklo, Nešetřil, 2004 , §5.2.
↑ Peklo, Nešetřil, 1990 , str. 92–110.
↑ Peklo, Nešetřil, 2004 , §5.3.
↑ Peklo, Nešetřil, 2004 , Věta 5.14.
↑ 1 2 Feder, Vardi, 1998 , str. 57–104.
↑ Cygan, Fomin, Golovnev a kol., 2016 , str. 1643–1649
↑ Dalmau, Kolaitis, Vardi, 2002 , str. 310–326.
↑ 1 2 3 Grohe, 2007 .
↑ 12 Marx , 2010 , s. 85–112.

Literatura

Welzl E. Barevné rodiny jsou husté // Teorie. Počítat. sci. . - 1982. - T. 17 . — s. 29–41 . - doi : 10.1016/0304-3975(82)90129-3 .
Pavol Hell, Jaroslav Nesetzil. O složitosti H-barvení // 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. O grafech se silně nezávislými barevnými třídami // J. Graph Theory . - 2004. - T. 46 , no. 1 . — S. 1–14 . - doi : 10.1002/jgt.10165 .

Leonard Kwuida, Erkko Lehtonen. On the 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. Hedetniemiho domněnka, o 40 let později // Graph Theory Notes of New York. - 2008. - T. 54 . — s. 46–57 .
Dwight D., Sauer N. Lattices vznikající při kategoriálních vyšetřováních Hedetniemiho domněnky // Diskrétní matematika. . - 1996. - T. 152 , no. 1-3 . — S. 125–139 . - doi : 10.1016/0012-365X(94)00298-W .
Daniel Marx. Dokážete porazit Treewidth? // Teorie výpočetní techniky . - 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 subgraph isomorphism. - SIAM , 2016. - ISBN 978-1-611974-33-1 .
Victor Dalmau, Phokion G. Kolaitis, Moshe Y. Vardi. Spokojenost s omezením, omezená šířka stromu a logika konečných proměnných. - 2002. - S. 310-326. - doi : 10.1007/3-540-46135-3_21 .
Martin Grohe. Složitost homomorfismu a problémy uspokojení omezení z druhé strany // J. ACM . - 2007. - T. 54 , č. 1 . - doi : 10.1145/1206035.1206036 .
Tomás Feder, Moshe Y. Vardi . Výpočetní struktura monotónního monadického SNP a uspokojování omezení: Studie prostřednictvím datalogu a teorie grup // SIAM J. Comput. . - 1998. - T. 28 , no. 1 . — s. 57–104 . - doi : 10.1137/S0097539794266766 .

Obecné knihy

Peter Cameron. Graf homomorfismů, poznámky studijní skupiny kombinatoriky . — 2006.
Pavol Hell, Jaroslav Nesetzil. Grafy a homomorfismy . - Oxford University Press, 2004. - V. 28 . — ISBN 0-19-852817-5 .
Geňa H., Tardif C. Grafové homomorfismy: struktura a symetrie // 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. Homomorfismy // Teorie algebraických grafů. - Springer-Verlag New York, 2001. - T. 207. - (Graduate Texts in Mathematics). — ISBN 978-1-4613-0163-9 . - doi : 10.1007/978-1-4613-0163-9 .

V univerzální algebře a podléhající omezením

Bodirsky M. Graf homomorfismů a univerzální algebry, poznámky ke kurzu . — 2007.
Pavol Hell, Jaroslav Nesetzil. Barvení, uspokojení omezení a složitost // Recenze informatiky. - 2008. - Vol. 2 , vydání. 2 . — S. 143–163 . - doi : 10.1016/j.cosrev.2008.10.003 .

V teorii svazů a teorii kategorií

Brown R., Morris I., Shrimpton J., Wensley CD Grafy morfismů grafů // Electronic Journal of Combinatorics . - 2008. - T. 15 , no. 1 . - S. A1 .
Šedá CT The Digraph Lattice . — 2014. ( AMSI Vacation Research Scholarships , studentská výzkumná zpráva pod dohledem Briana Daveyho a Jane Pitkethly, La Trobe University ).