Grafikonhomomorfizmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. október 14-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A gráfhomomorfizmus két gráf közötti leképezés , amely nem töri meg a struktúrát. Pontosabban, ez egy leképezés két gráf csúcsainak halmaza között, amely a szomszédos csúcsokat a szomszédos csúcsokra képezi le.

A homomorfizmusok a gráfszínezések különféle fogalmait általánosítják, és lehetővé teszik a kényszer-elégedettségi problémák fontos osztályainak kifejezését , mint például egyes ütemezési problémák vagy rádiófrekvencia-allokációs problémák [1] . Az a tény, hogy a homomorfizmusok szekvenciálisan használhatók, gazdag algebrai struktúrákhoz vezet – gráfokon előre rendezés , disztributív rács és kategóriák (egy irányítatlan és egy irányított gráfokhoz) [2] . Az adott gráfok közötti homomorfizmus megtalálásának számítási bonyolultsága általában túlzó, de sok olyan speciális eset ismert, amikor a feladat polinomiális időben kivitelezhető . A megoldható és áthidalhatatlan esetek közötti határvonalak az aktív kutatások területe [3] .

Definíciók

Ebben a cikkben, hacsak másképp nem jelezzük, a gráfok véges irányítatlan gráfokat jelentenek engedélyezett hurokkal , de több (párhuzamos) él nem megengedett. Egy gráfhomomorfizmus [4] [5] [6] : f gráfról gráfra , amelyet a következőképpen írunk: $G=(V(G),E(G))$ ${\megjelenítési stílus H=(V(H),E(H))}$

f:G\ to H

egy függvény V ( G ) - től V ( H ) - ig , amely leképezi az egyes élek végpontjait G - ből valamely H - ból származó él végpontjaira . Formálisan ebből következik , minden u , v csúcspár esetén V ( G ) . Ha van némi homomorfizmus G -től H -ig , akkor a G gráfot homomorfnak mondjuk a H gráfnak , vagy H - színezhetőnek . Ezt gyakran úgy emlegetik $\{u,v\}\in E(G)$ $\{f(u),f(v)\}\in E(H)$

G\to H

A fenti definíció kiterjed az irányított gráfokra is. Ekkor homomorfizmus esetén a H gráf íve (irányított éle), amikor ( u , v ) a G gráf íve . $f:G\to H,(f(u),f(v))$

Létezik injektív homomorfizmus G -től H -ig (vagyis olyan leképezés, amely soha nem képez le különböző csúcsokat egyetlen csúcsra), akkor és csak akkor, ha G a H részgráfja . Ha egy homomorfizmus egy bijekció (egy az egyhez megfeleltetés G és H csúcsai között ) , amelynek inverz függvénye egyben gráfhomomorfizmus is, akkor f gráfizomorfizmus [7] . $f:G\ to H$

A burkolatleképezések a homomorfizmus gyakori típusa, amely tükrözi a topológiában található borítás definícióját és számos tulajdonságát [8] . Ezeket szürjektív homomorfizmusokként határozzák meg, amelyek lokálisan bijektívek, azaz minden csúcs szomszédságában lévő bijekció. Példa erre a kettős borítás egy kétrészes gráfból , amelyet egy gráfból úgy alakítunk ki, hogy minden v csúcsot felosztunk és -re , és minden u , v élt két és élre cserélünk . Az eredeti gráf v 0 és v 1 függvényleképezése egy homomorfizmus és egy fedőleképezés . $v_{0}$ $v_{1}$ $u_{0},v_{1}$ ${\displaystyle v_{0},u_{1))$

A gráf homeomorfizmus egy külön fogalom, nem kapcsolódik közvetlenül a homomorfizmusokhoz. Durván fogalmazva, ez injektivitást igényel, de lehetővé teszi az élek leképezését útvonalakra (nem csak élekre). A kisebb grafikonok gyengébb fogalom marad.

Kernelek és visszahúzások

Két G és H gráf homomorfikusan ekvivalens , ha és [4] [5] [6] . $G\to H$ $H\to G$

A visszahúzás egy r homomorfizmus G - ből G egy H részgráfjára úgy, hogy r ( v ) = v H minden v csúcsára . Ebben az esetben a H részgráfot a G gráf visszahúzásának nevezzük [9] .

A kernel olyan gráf, amelynek nincs homomorfizmusa egyetlen megfelelő részgráfhoz sem. Ezzel egyenértékűen a kernelt úgy definiálhatjuk, mint egy gráfot, amely nem egy megfelelő részgráf visszahúzása [10] . Bármely G gráf homomorfikusan ekvivalens egy egyedi kernellel (az izomorfizmusig), amelyet a G gráf magjának nevezünk [ 11 ] [ 12] . Megjegyezzük, hogy ez nem igaz általános végtelen gráfokra [13] . Az irányított gráfokra azonban ugyanezek a definíciók vonatkoznak, és az irányított gráf egyetlen kernellel is egyenértékű. Minden irányítatlan és irányított gráf tartalmazza a kernelt visszavonásként és generált részgráfként is [9] .

Például az összes K n teljes gráf és minden páratlan ciklus ( páratlan hosszúságú ciklusgráf ) kernel. Bármely 3 színezhető G gráf , amely háromszöget tartalmaz (vagyis egy teljes gráf K 3 részgráfja), homeomorf módon egyenértékű K 3 -val . Ennek az az oka, hogy egyrészt a G gráf 3 színezése megegyezik a homomorfizmussal , amint azt alább kifejtjük. Másrészt G bármely részgráfja triviálisan elismeri G homomorfizmusát , amiből az következik, hogy . Ez azt is jelenti, hogy K 3 bármely ilyen G gráf magja . Hasonlóképpen minden olyan kétrészes gráf , amelynek legalább egy éle van, ekvivalens K 2 -vel [14] . $G\to K_{3}$ $K_{3}\to G$

Kapcsolat színező oldalakkal

A k -színezés valamilyen k egész számra a k szín közül egyet hozzárendel a G gráf minden csúcsáhozúgy, hogy az egyes élek végcsúcsai különböző színűek legyenek. k - A G gráf színei pontosan megfelelnek a G -től a K k teljes gráfig terjedő homomorfizmusoknak [15] [16] . Ráadásul a K k gráf csúcsai k színnek felelnek meg, és két szín akkor és csak akkor szomszédos a K k gráf csúcsaiként,ha különböznek egymástól. Ezért a függvény akkor és csak akkor határoz meg homomorfizmust K k -ben , ha a G gráf szomszédos csúcsai különböző színekkel vannak színezve. Konkrétan egy G gráf akkor és csak akkor k -színezhető, ha K k -színezhető [15] [16] .

Ha van két homomorfizmus és , akkor azok szuperpozíciója is homomorfizmus [17] . Más szóval, ha a H gráf kiszínezhető k színnel, és van G homomorfizmusa H -be , akkor G is színezhető k színnel. Ebből következik , hogy ahol a gráf kromatikus számát jelenti (a legkisebb számú színt , amelyben a gráf színezhető) [18] . $G\to H$ ${\displaystyle H\to K_{k))$ ${\displaystyle G\to K_{k))$ $G\to H$ $\chi (G)\leqslant \chi (H)$ $\chi$

Opciók

Az általános homomorfizmusok egyfajta színezésnek is tekinthetők - ha egy rögzített H gráf csúcsai megengedettek a színek , és a H gráf élei azt írják le, hogy mely színek kompatibilisek , akkor a G gráf H -színezése a hozzárendelése színeket a G gráf csúcsaihoz úgy, hogy a szomszédos csúcsok kompatibilis színeket kapjanak. A gráfszínezés számos fogalma illeszkedik ebbe a sémába, és gráfhomomorfizmusként fejezhető ki különböző gráfcsaládokba. A ciklusszínezések homomorfizmusok segítségével definiálhatók teljes gráfok ciklusára , finomítva a színezés szokásos fogalmát [ 19] [20] . A tört- és b - szeres színezések a Kneser-gráfok homomorfizmusaival határozhatók meg [21] [22] A T-színezések megfelelnek néhány végtelen gráf homomorfizmusának [23] . { Egy irányított gráf irányított színezése bármely irányított gráf homomorfizmusa [24] . Az L(2,1)-színezés egy lokálisan injektív homomorfizmus egy útvonal komplementerében , ami azt jelenti, hogy minden csúcs szomszédságában injektívnek kell lennie [25] .

Tájékozódás hosszú utak nélkül

Egy másik érdekes összefüggés a gráfok orientációjával kapcsolatos. Egy irányítatlan G gráf orientációja bármely irányított gráf, amelyet úgy kapunk, hogy minden élhez két lehetséges orientáció közül választunk. Példa a K k teljes gráf orientációjára egy tranzitív verseny , amelynek csúcsai 1,2,…, k és i -ből j - be ívelnek, amikor i < j . A G és H gráfok orientációi közötti homomorfizmus homomorfizmust ad az irányítatlan G és H gráfok között, ha egyszerűen figyelmen kívül hagyjuk az orientációkat. Másrészt, ha az irányítatlan gráfok között homomorfizmus van , H bármely orientációja leképezhető G gráfjának orientációjára , így ennek homomorfizmusa van -ben . Ezért egy G gráf k -színezhető ( K k -ben van homomorfizmusa), akkor és csak akkor, ha G bizonyos orientációja homomorfizmust tartalmaz a [26] -ban . ${\vec {T}}_{k}$ $G\to H$ ${\vec {H}}$ ${\vec {G}}$ ${\vec {G}}$ ${\vec {H}}$ ${\vec {T}}_{k}$

A folklórtétel azt mondja, hogy bármely k esetében egy irányított G gráfnak akkor és csak akkor van homomorfizmusa, ha nem ismeri el a [27] -ből származó homomorfizmust . Itt van egy orientált útvonal 1, 2, …, n csúcsokkal és i-ből i-ből i + 1 -be ívelve i =1, 2, …, n − 1 esetén. Így a gráf akkor és csak akkor k színezhető, ha van az orientáció, amely nem ismeri el a homomorfizmust a -ból . Ezt az állítást kissé megerősíthetjük azzal, hogy egy gráf akkor és csak akkor k színezhető, ha valamilyen orientáció nem tartalmaz k hosszúságú irányított utat (nem részgráfként). Ez a Gallai-Hasse-Roy-Vitaver tétel . ${\vec {T}}_{k}$ ${\vec {P}}_{k+1}$ ${\vec {P}}_{n}$ ${\vec {P}}_{k+1}$ ${\vec {P}}_{k+1}$

Kapcsolat a megkötéssel kapcsolatos elégedettségi problémákkal

Példák

Egyes ütemezési problémák modellezhetők gráfhomomorfizmusok keresésének kérdéseként [15] [28] . Példaként megkísérelhetjük úgy ütemezni a gyakorlatokat, hogy két kurzus, amelyen ugyanaz a hallgató vesz részt, időben ne legyen túl közel. A kurzusok egy G gráfot alkotnak , két kurzus közötti élekkel, ha ugyanaz a hallgató vesz részt. A kurzusok lebonyolításának lehetséges ideje egy H gráfot alkot két időablak közötti élekkel, ha a köztük lévő időtávolság elég nagy. Például, ha valaki ciklikus heti beosztást szeretne úgy, hogy minden tanuló kétnaponta jöjjön gyakorolni, akkor a H oszlop a C 7 oszlop kiegészítése . A G -től H -ig tartó gráfhomomorfizmus tehát a kurzusok időablakok szerinti hozzárendelése [15] . Ahhoz, hogy olyan követelményt adjunk hozzá, mondjuk, hogy egy diáknak sem legyen órája pénteken és hétfőn is, elég eltávolítani egy élt a H gráfból .

Egy egyszerű frekvenciaeloszlási probléma a következőképpen fogalmazható meg. Számos vezeték nélküli hálózati adó létezik . Mindegyiknél ki kell választani azt a frekvenciacsatornát, amelyen keresztül adatokat továbbít. Az interferencia elkerülése érdekében a földrajzilag közel lévő adóknak kellően eltérő frekvenciájú csatornákkal kell rendelkezniük. Ha ez a feltétel a „földrajzilag közel” és a „megfelelően távol” fogalmak egyszerű küszöbére korlátozódik, az érvényes csatornaválasztás ismét egy gráfhomomorfizmusnak felel meg. Itt a G gráf olyan adók halmaza lesz, amelyek között élek vannak, ha földrajzilag közel vannak, és a H gráf olyan csatornák halmaza, amelyek csatornái között élek, ha a frekvenciák kellően eltérőek. Bár ez a modell nagymértékben leegyszerűsített, némi rugalmasságot tesz lehetővé – egy olyan adópárhoz, amelyek nincsenek közel egymáshoz, de a földrajzi adottságok miatt interferálhatnak egymással, G -ben egy ívet lehet hozzáadni . Az egyidejűleg nem működő adók közötti ív pedig eltávolítható a grafikonról. Hasonlóképpen a H gráfból eltávolítható az egymástól távol eső, de harmonikus interferenciát mutató csatornapár közötti él [29] .

Ezek az egyszerűsített modellek minden esetben sok olyan jellemzőt mutatnak, amelyeket a gyakorlatban ki kellene dolgozni [30] . A gráf homomorfizmus problémáit általánosító kényszerkielégítési problémák további típusú feltételeket (például egyéni preferenciákat vagy az egyező hozzárendelések számának korlátozását) fejezhetnek ki. Ez valósághűbbé és praktikusabbá teszi a modelleket.

Formai nézőpont

Az irányított és irányított gráfok egy általánosabb, relációs struktúráknak nevezett fogalom gyakori példányainak tekinthetők amelyek halmazként vannak definiálva, rajta egy sor relációval). Az irányított gráfok egy bináris relációval (szomszédsággal) rendelkező struktúrák egy tartományon (csúcsok halmazán) [31] [3] . Ebből a szempontból az ilyen struktúrák homomorfizmusai pontosan gráfhomomorfizmusok. Általános esetben az egyik struktúrából a másikba való homomorfizmus megtalálásának kérdése egy kényszer - elégedettségi probléma ( CSP) . A grafikonok esete egy konkrét első lépést ad, amely segít megérteni a bonyolultabb kényszer-elégedettségi problémákat. A gráfhomomorfizmusok megtalálására szolgáló számos algoritmikus módszer, mint például a visszalépés , a kényszer terjedése és a helyi keresés , alkalmazható minden kényszerkielégítési problémára [3] .

A G és H gráfok esetében az a kérdés, hogy a G gráf homomorfizmussal rendelkezik-e a H gráfhoz , csak egyfajta megszorítással felel meg a megszorítások kielégítési problémájának egy adott esetének [3] . Ebben a feladatban a változók a G gráf csúcsai, az egyes változók tartománya pedig a H gráf csúcsainak halmaza lesz . A megoldás egy olyan függvény, amely minden változóhoz hozzárendel egy elemet a tartományból, így az f függvény V ( G ) -t V ( H )-re képezi le. Ekkor a G gráf minden éle vagy íve [32] ( u , v ) megfelel a kényszernek (( u , v ), E( H )). Ez a megszorítás azt fejezi ki, hogy a megoldásnak le kell képeznie az (u, v) ívet az ( f ( u ) , f ( v ) párra , amely az E ( H ) reláció, azaz a H gráf ívére . A feladat megoldása egy olyan megoldás, amely minden megkötést kielégít, vagyis pontosan homomorfizmus G -től H -ig .

A homomorfizmusok szerkezete

A homomorfizmusok szuperpozíciói homomorfizmusok [17] . Különösen a gráfokon lévő reláció tranzitív (és triviálisan reflexív), tehát ez a reláció előrendelés a gráfokon [33] . Egy G gráf homomorfizmus ekvivalencia osztályát [ G ] -vel fogjuk jelölni . Egy ekvivalenciaosztály egyetlen kernellel is reprezentálható [ G ]-ben. A reláció ezeken az ekvivalenciaosztályokon részben rendezett . Egy részlegesen rendezett halmazt határoz meg [34] . $\nak nek$ $\nak nek$

Jelentse G < H , hogy van homomorfizmus G -ből H -be, de nincs homomorfizmus H -ból G -be . A reláció egy sűrű sorrend , ami azt jelenti, hogy minden olyan (iránytalan) G , H gráfra , ahol G < H , létezik olyan K gráf , amelyre G < K < H (ez minden esetben érvényes, kivéve a triviális eseteket vagy ) [35] [36] [37] . Például bármely két teljes gráf között (kivéve ) végtelenül sok racionális számoknak megfelelő ciklikus teljes gráf található [38] [39] . $\nak nek$ $G=K_{0}$ $K_1$ ${\displaystyle K_{0},K_{1))$

A homomorfizmus által részben rendezett gráfekvivalencia-osztályok halmaza egy disztributív rács , ahol az [ [ G ] és [ H ] uniója (ekvivalenciaosztály) diszjunkt unióként van definiálva, és az [ G metszéspontja. ] és [ H ] tenzorszorzatként definiált (a G és H gráfok mint a [ G ] és [ H ] ekvivalenciaosztályok képviselőinek megválasztása nem számít) [40] [41] . Ennek a rácsnak az unióban irreducibilis elemei pontosan összefüggő gráfok. Ez azzal a ténnyel mutatható meg, hogy egy homomorfizmus egy összefüggő gráfot képez le a célgráf egy összefüggő komponensére [42] [43] . Ennek a rácsnak a metszésponttal irreducibilis elemei pontosan multiplikatív gráfok . Ezek olyan K gráfok, amelyekben a szorzat csak akkor rendelkezik homomorfizmussal K -ben, ha a G vagy H gráfok egyike rendelkezik ilyen homomorfizmussal. Hedetniemi sejtésének [44] [45] magja a multiplikatív gráfok felfedezése . $[G\cup H]$ $[G\times H]$ $G\time H$

A gráfhomomorfizmusok is egy kategóriát alkotnak, ahol a gráfok objektumok, a homomorfizmusok pedig nyilak [46] . A kezdeti objektum egy üres gráf, míg a végobjektum egy gráf, amelynek egy csúcsa és egy hurokja van. A gráfok tenzorszorzata egy szorzat a kategóriaelméletben , az exponenciális gráf pedig egy kategória exponenciális objektuma [45] [47] . Mivel ez a két művelet mindig definiálva van, a gráfok kategóriája egy Descartes-féle zárt kategória . Ugyanezen okokból kifolyólag a gráfekvivalencia osztályok homomorfizmusok szerinti rácsa valójában egy Heyting-algebra [45] [47] .

Az irányított gráfokra ugyanezek a meghatározások érvényesek. Különösen, részben rendezett az irányított gráfok ekvivalencia osztályaira. Ez a sorrend eltér az irányítatlan gráfok ekvivalencia osztályaira vonatkozó sorrendtől, de alrendként tartalmazza. Ugyanis minden irányítatlan gráf felfogható irányítottnak, amelyben bármely ív ( u , v ) egy inverz ívvel ( v , u ) együtt jelenik meg , és ez nem változtat a homomorfizmus definícióján. Az irányított gráfok sorrendje ismét egy eloszlási rács és egy Heyting-algebra, az egyesülési és metszésponti műveletekkel az előzőek szerint. Ez a sorrend azonban nem szoros. Létezik olyan kategória is, amelyben az irányított gráfok objektumok, a homomorfizmusok pedig a nyilak, ami ismét egy descartes-i zárt kategória [48] [47] . $\nak nek$ $\nak nek$ $\nak nek$

Összehasonlíthatatlan grafikonok

Sok összehasonlíthatatlan gráf létezik a homomorfizmusok előrendje szerint, vagyis olyan gráfpárok, amelyekben nincsenek homomorfizmusok egyiktől a másikig [49] . Az ilyen gráfok elkészítésének egyik módja a G gráf páratlan kerületének figyelembe vétele , azaz a legrövidebb páratlan hosszúságú ciklus hosszának figyelembe vétele. A páratlan kerület ennek megfelelően a legkisebb páratlan g szám , amelyre homomorfizmus van egy g csúcsú ciklusgráfból G - be . Emiatt, ha , akkor a G gráf páratlan kerülete nagyobb vagy egyenlő a H gráf páratlan kerületével [50] . $G\to H$

Másrészt, ha , akkor a G gráf kromatikus száma kisebb vagy egyenlő, mint a H gráf kromatikus száma . Ezért, ha egy G gráfnak szigorúan nagyobb a páratlan kerülete, mint H , és szigorúan nagyobb a kromatikus [49]összehasonlíthatatlanokHésG, akkorHszáma, mint [51] , tehát nem kompatibilis a háromszög K 3 . $G\to H$

Példák az önkényesen nagy páratlan kerületi és kromatikus számértékekkel rendelkező gráfokra a Kneser-gráfok [52] és az általánosított Mychelski-gráfok [53] . Az ilyen gráfok sorozata mindkét paraméter értékének egyidejű növekedésével végtelen számú összehasonlíthatatlan gráfot ad ( antilánc a homomorfizmusok előrendjében) [54] . Más tulajdonságok, mint például a homomorfizmusok előrendjének sűrűsége, igazolhatók ilyen családok segítségével [55] . A páratlan kerület helyett nagy kromatikus szám- és kerületi értékekkel rendelkező grafikonok készítése is lehetséges, de nehezebb (lásd: Grafikon kerülete és színezése ).

Az irányított gráfok között sokkal könnyebb összehasonlíthatatlan párokat találni. Vegyünk például irányított ciklusgráfokat 1, 2, …, n csúcsokkal és élekkel i -től i + 1-ig ( i =1, 2, …, n − 1 esetén) és n -től 1- ig. akkor és csak akkor, ha n k többszöröse . Különösen az n prímszámú irányított ciklusgráfok összehasonlíthatatlanok [56] . ${\vec {C}}_{n}$ ${\vec {C}}_{n}$ ${\vec {C}}_{k}(n,k\geqslant 3)$ ${\vec {C}}_{n}$

Számítási összetettség

A gráfhomomorfizmus feladatban a probléma egy példánya egy gráfpárból áll ( G , H ), a megoldás pedig egy G -től H -ig terjedő homomorfizmus. Az általános megoldhatósági probléma , amely azt kérdezi, hogy van-e megoldás erre a problémára, NP-teljes [57] . A gráf megszorítások azonban számos különböző problémához vezetnek, amelyek közül néhányat könnyebben meg lehet oldani. A bal oldali G gráf megszorításait használó módszerek nagyban különböznek a jobb H gráfon használt módszerektől , de minden esetben ismert vagy feltételezett a dichotómia (szigorú határok az egyszerű és összetett esetek között).

Homomorfizmusok egy rögzített gráfhoz

Az egyes példányok jobb oldalán lévő rögzített H gráf homomorfizmus problémáját H színezési problémának nevezzük. Ha H egy teljes K k gráf , ez egy k gráf színezési problémája , amely polinomiális időben megoldható k =0, 1, 2 esetén, és egyébként NP-teljes [58] . Konkrétan egy G gráf K 2 -színezésének lehetősége ekvivalens a kétrészes G gráféval , amely lineáris időben ellenőrizhető. Általánosabban fogalmazva, ha H egy kétrészes gráf, a H színezés lehetősége megegyezik a K 2 színezés lehetőségével (vagy K 0 / K 1 színezhető, ha H üres vagy nincs éle), és ezért ugyanolyan könnyű megoldani [59] . Pavol Hell és Jaroslav Neshetril bebizonyította, hogy az irányítatlan gráfok esetében nincs más eset könnyű:

Hell-Neshetril tétel (1990): Egy H -színezési probléma a P osztályban található, ha H kétrészes, egyébként pedig NP-kemény [60] [61] .

A tétel az (iránytalan) gráfhomomorfizmus dichotómia tételeként is ismert , mivel a H -színezési feladatokat NP-teljes és P osztályú feladatokra osztja fel közbülső esetek nélkül. Az irányított gráfok esetében a helyzet bonyolultabb, és valójában egyenértékű a megszorítások kielégítésének összetettségének leírásával kapcsolatos általánosabb kérdéssel [62] . Kiderült, hogy az irányított gráfok H -színezési problémái ugyanolyan általánosak és ugyanolyan változatosak, mint a megszorítások kielégítési problémái bármely más típusú megszorítással [63] [64] . Formálisan a Γ (véges) kényszernyelv egy véges tartomány és véges relációk halmaza ebben a tartományban. A CSP( Γ ) egy kényszerkielégítési probléma, ahol a példányok csak a Γ megszorításait használhatják .

Tétel (Feder, Vardy 1998): Bármely Γ kényszernyelv esetén a CSP( Γ ) polinomiális redukció után ekvivalens valamilyen H -színezési problémával valamilyen H irányított gráf esetében [64] .

Ez intuitív módon azt jelenti, hogy a H irányított gráfok H színezési problémáira alkalmazható bármely algoritmikus technika vagy összetettségi eredmény az általános kényszerkielégítési problémákra is vonatkozik. Konkrétan felmerülhet a kérdés, hogy a Hell-Neshetril tétel kiterjeszthető-e irányított gráfokra. A fenti tétel szerint ez ekvivalens a Feder-Vardi-sejtéssel a kényszerkielégítési problémák dichotómiájáról, amely szerint bármely Γ kényszernyelv esetén a CSP( Γ ) vagy NP-teljes, vagy a P osztályba tartozik [57] .

Homomorfizmusok egy rögzített gráfcsaládból

A homomorfizmus probléma egy rögzített G gráfbal a bal oldalon megoldható kimerítő kereséssel | V ( H )| O(| V ( G )|) , azaz polinom a H bemeneti gráf méretében [65] . Más szóval, a probléma triviális P-ben a korlátos méretű G gráfok esetében. Érdekes kérdés tehát, hogy a G gráfnak a méreten kívül milyen egyéb tulajdonságai tesznek lehetővé polinomiális algoritmusokat.

A kulcstulajdonság a treewidth , amely annak mértéke, hogy egy gráf mennyire hasonlít egy fához. Egy legfeljebb k faszélességű G gráf és egy H gráf esetén a homomorfizmus probléma időben megoldható | V ( H )| O( k ) szabványos dinamikus programozási módszerekkel . Valójában elegendő azt feltételezni, hogy a G magjának legfeljebb k faszélessége van . Ez akkor is igaz, ha a kernel nem ismert [66] [67] .

Indikátor az algoritmusban futási idővel| V ( H )| O( k ) nem csökkenthető jelentősen - nincs olyan algoritmus, amely időben futna | V ( H )| o(tw( G ) /log tw( G )) , ha az exponenciális időhipotézis ( ETH) igaz, még akkor is, ha a bemenetet a korlátlan faszélességű gráfok bármely osztálya korlátozza [68] . Az ETH egy nem bizonyított feltevés, hasonló a P ≠ NP feltételezéshez , de szigorúbb. Ugyanezen feltevések mellett nincs más tulajdonság, amely felhasználható polinomiális idő algoritmusok származtatására. Ezt a tétel formalizálja:

Tétel (Martin Grohe): A gráfok egy kiszámítható osztálya esetén a c homomorfizmus-probléma akkor és csak akkor tartozik P-hez, ha a gráfok korlátos faszélességű kernelekkel rendelkeznek (az ETH-feltevésben) [67] .

{\mathcal {G}}

{\megjelenítési stílus (G,H)}

G\in {\mathcal {G}}

{\mathcal {G}}

Feltehetjük a kérdést, hogy a probléma megoldható-e tetszőlegesen nagy G -függőséggel , de a H gráf méretétől fix polinomiális függéssel. A válasz igen, ha a G gráfot korlátozzuk egy korlátozott faszélességű kernelekkel rendelkező osztályra, és nem az összes többi osztályra [67] . A parametrizált komplexitás nyelvén ez az állítás formálisan azt mondja, hogy a gráf homomorfizmus-probléma, amelyet G méretével (éleinek számával) paraméterezünk, kettősséget mutat. Fix paraméterrel eldönthető [ , ha az osztály gráfjainak korlátos faszélességű kerneljei vannak, egyébként pedig W[1]-teljes . ${\mathcal {G}}$ ${\mathcal {G}}$

Ugyanez az állítás igaz az általánosabb kényszer-elégedettségi problémákra (vagy más szóval a relációs struktúrákra). Az egyetlen szükséges feltételezés az, hogy a megszorítások csak korlátozott számú változót érinthetnek. A paraméter ekkor a fő kényszergráf faszélessége [68] .

Lásd még

Hipotézis Sidorenko

Jegyzetek

↑ Pokol, Nešetřil, 2004 , p. 27.
↑ Pokol, Nešetřil, 2004 , p. 109.
↑ 1 2 3 4 Pokol, Nešetřil, 2008 .
↑ 12 Cameron , 2006 .
↑ 1 2 Geňa, Tardif, 1997 .
↑ 1 2 Pokol, Nešetřil, 2004 .
↑ Gena, Tardif, 1997 , 2.3. megfigyelés.
↑ Godsil, Royle, 2001 , p. 115.
↑ 1 2 Pokol, Nešetřil, 2004 , p. 19.
↑ Pokol, Nešetřil, 2004 , 1.31. tétel.
↑ Cameron, 2006 , 2.3. tétel.
↑ Pokol, Nešetřil, 2004 , Következmény 1.32.
↑ Pokol, Nešetřil, 2004 , p. 34.
↑ Cameron, 2006 , p. 4 (2.5. javaslat).
↑ 1 2 3 4 Cameron, 2006 , p. egy.
↑ 1 2 Pokol, Nešetřil, 2004 , 1.7. tétel.
↑ 1 2 Pokol, Nešetřil, 2004 , 1.7.
↑ Pokol, Nešetřil, 2004 , Következmény 1.8.
↑ Pokol, Nešetřil, 2004 , 6.1.
↑ Gena, Tardif, 1997, 4.4.
↑ Pokol, Nešetřil, 2004 , 6.2.
↑ Gena, Tardif, 1997, 4.5.
↑ Pokol, Nešetřil, 2004 , 6.3.
↑ Pokol, Nešetřil, 2004 , 6.4.
↑ * Fiala J., Kratochvíl J. Gráfok részleges borítói // Discussions Mathematicae Graph Theory. - 2002. - T. 22 , sz. 1 . — S. 89–99 . - doi : 10.7151/dmgt.1159 .
↑ Pokol, Nešetřil, 2004 , p. 13–14.
↑ Pokol, Nešetřil, 2004 , 1.20. tétel.
↑ Pokol, Nešetřil, 2004 , 1.8.
↑ Pokol, Nešetřil, 2004 , p. 30–31.
↑ Pokol, Nešetřil, 2004 , p. 31–32.
↑ Pokol, Nešetřil, 2004 , p. 28. Vegye figyelembe, hogy a cikkben szereplő relációs struktúrákat relációs rendszereknek nevezzük .
↑ Emlékezzünk vissza, hogy általában az irányított gráf éleit íveknek nevezzük.
↑ Pokol, Nešetřil, 2004 , 3.1.
↑ Pokol, Nešetřil, 2004 , 3.1. Tétel.
↑ Pokol, Nešetřil, 2004 , 3.30. Tétel.
↑ Geňa, Tardif, 1997 , 2.33. tétel.
↑ Welzl, 1982 , p. 29–41.
↑ Pokol, Nešetřil, 2004 , p. 192.
↑ Gena, Tardif, 1997 , p. 127.
↑ Hell, Nešetřil, 2004 , 3.2. állítás, a disztributivitás a 2.4. állításban található.
↑ Geňa, Tardif, 1997 , 2.37. tétel.
↑ Kwuida, Lehtonen, 2011 , p. 251–265.
↑ Szürke, 2014 , Lemma 3.7.
↑ Tardif, 2008 , p. 46–57.
↑ 1 2 3 Dwight, Sauer, 1996 , p. 125–139.
↑ Pokol, Nešetřil, 2004 , p. 125.
↑ 1 2 3 Szürke, 2014 .
↑ Brown, Morris, Shrimpton, Wensley, 2008 .
↑ 1 2 Pokol, Nešetřil, 2004 , p. 7.
↑ Gena, Tardif, 1997 , Megfigyelés 2.6.
↑ Weisstein, Eric W. Grötzsch grafikonja a Wolfram MathWorld webhelyén .
↑ Gena, Tardif, 1997 , 3.14. tétel.
↑ Gyárfás, Jensen, Stiebitz, 2004 , p. 1–14.
↑ Pokol, Nešetřil, 2004 , 3.4. tétel.
↑ Pokol, Nešetřil, 2004 , p. 96.
↑ Pokol, Nešetřil, 2004 , p. 35.
↑ 1 2 Bodirsky, 2007 , 1.3.
↑ Pokol, Nešetřil, 2004 , 5.1.
↑ Pokol, Nešetřil, 2004 , 5.1. tétel.
↑ Pokol, Nešetřil, 2004 , 5.2.
↑ Pokol, Nešetřil, 1990 , p. 92–110.
↑ Pokol, Nešetřil, 2004 , 5.3.
↑ Pokol, Nešetřil, 2004 , 5.14. Tétel.
↑ 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 .
↑ Marx 12. , 2010 , p. 85–112.

Irodalom

Welzl E. A színcsaládok sűrűek // Elmélet. Comput. sci. . - 1982. - T. 17 . – 29–41 . - doi : 10.1016/0304-3975(82)90129-3 .
Pavol Hell, Jaroslav Nesetzil. A H-színezés összetettségéről // JCTB . - 1990. - T. 48 , sz. 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-Classes // J. Graph Theory . - 2004. - T. 46 , sz. 1 . – S. 1–14 . - doi : 10.1002/jgt.10165 .

Leonard Kwuida, Erkko Lehtonen. A címkézett posetek homomorfizmusáról // Rend . - Springer, 2011. - T. 28 , sz. 2 . – S. 251–265 . - doi : 10.1007/s11083-010-9169-x . - arXiv : 0911.0200 .
Tardif C. Hedetniemi sejtése, 40 évvel később // Graph Theory Notes of New York. - 2008. - T. 54 . – 46–57 .
Dwight D., Sauer N. Hedetniemi sejtésének kategoriális vizsgálatában felmerülő rácsok // Discrete Math. . - 1996. - T. 152 , sz. 1-3 . – S. 125–139 . - doi : 10.1016/0012-365X(94)00298-W .
Daniel Marx. Meg tudod győzni a Treewidth-et? // A számítástechnika elmélete . - 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. Megszorítások kielégítése, korlátos faszélesség és véges-változós logika. - 2002. - S. 310-326. - doi : 10.1007/3-540-46135-3_21 .
Martin Grohe. A homomorfizmus és a kényszer-elégedettségi problémák összetettsége a másik oldalról nézve // J. ACM . - 2007. - T. 54 , sz. 1 . - doi : 10.1145/1206035.1206036 .
Tomás Feder, Moshe Y. Vardi . A monoton monadikus SNP számítási struktúrája és a megszorítások kielégítése: Tanulmány az adatlogon és a csoportelméleten keresztül // SIAM J. Comput. . - 1998. - T. 28 , sz. 1 . – 57–104 . - doi : 10.1137/S0097539794266766 .

Általános könyvek

Peter Cameron. Grafikonhomomorfizmusok, Kombinatorika Tanulmányi Csoport megjegyzései . – 2006.
Pavol Hell, Jaroslav Nesetzil. Grafikonok és homomorfizmusok . - Oxford University Press, 2004. - V. 28 . — ISBN 0-19-852817-5 .
Geňa H., Tardif C. Gráfhomomorfizmusok : szerkezet és szimmetria // 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. Homomorfizmusok // Algebrai gráfelmélet. - 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 .

Az univerzális algebrában és megszorításokkal

Bodirsky M. Graph Homomorphisms and Universal Algebra, Course Notes . – 2007.
Pavol Hell, Jaroslav Nesetzil. Színezés, korlátokkal való elégedettség és összetettség // Computer Science Review. - 2008. - 2. évf. , szám. 2 . – S. 143–163 . - doi : 10.1016/j.cosrev.2008.10.003 .

A rácselméletben és a kategóriaelméletben

Brown R., Morris I., Shrimpton J., Wensley CD Graphs of morphisms of graphs // Electronic Journal of Combinatorics . - 2008. - T. 15 , sz. 1 . - S. A1 .
Szürke CT The Digraph Lattice . — 2014. ( AMSI Vacation Research Scholarships , hallgatói kutatási jelentés, Brian Davey és Jane Pitkethly, La Trobe Egyetem felügyelete alatt ).