Graafinen homomorfismi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 14.10.2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Graafin homomorfismi on kahden graafin välinen kartoitus, joka ei riko rakennetta. Tarkemmin sanottuna se on kahden graafin kärkijoukon välinen kartoitus, joka kartoittaa viereiset pisteet vierekkäisiin.

Homomorfismit yleistävät erilaisia käsityksiä graafien värjäytymisestä ja mahdollistavat tärkeiden rajoitteiden tyytyväisyysongelmien luokkien ilmaisemisen , kuten jotkin ajoitusongelmat tai radiotaajuuksien allokointiongelmat [1] . Se, että homomorfismeja voidaan käyttää peräkkäin, johtaa rikkaisiin algebrallisiin rakenteisiin - graafien ennakkojärjestykseen, distributiiviseen hilaan ja kategorioihin (yksi suuntaamattomille ja toinen suunnatuille graafiille) [2] . Laskennallinen monimutkaisuus homomorfismin löytämisessä annettujen graafien välillä on yleensä kohtuutonta, mutta tunnetaan monia erikoistapauksia, joissa tehtävä on toteutettavissa polynomiajassa . Ratkaisettavien ja ylitsepääsemättömien tapausten väliset rajat ovat aktiivisen tutkimuksen alueella [3] .

Määritelmät

Ellei toisin mainita, tässä artikkelissa graafit tarkoittavat rajallisia suuntaamattomia graafia , joissa on sallittuja silmukoita , mutta useat (rinnakkaiset) reunat eivät ole sallittuja. Graafin homomorfismi [4] [5] [6] : f graafista graafiin , joka kirjoitetaan $G=(V(G),E(G))$ ${\näyttötyyli H=(V(H),E(H))}$

f:G\ to H

on V ( G ) - V ( H ) -funktio, joka kuvaa kunkin G :n reunan päätepisteet jonkin H :n reunan päätepisteisiin . Muodollisesti se seuraa kohdasta , kaikille kärkipareille u , v V :stä ( G ). Jos G :stä H :hen on homomorfia , niin graafin G sanotaan olevan homomorfinen graafin H kanssa tai että se on H -värittävä . Tätä kutsutaan usein nimellä $\{u,v\}\in E(G)$ ${\näyttötyyli \{f(u),f(v)\}\in E(H)}$

G\to H

Yllä oleva määritelmä ulottuu suunnattuihin graafisiin. Sitten homomorfismille on graafin H kaari (suunnattu reuna), kun ( u , v ) on graafin G kaari. $f:G\to H,(f(u),f(v))$

On olemassa injektiivinen homomorfismi G :stä H :hen (toisin sanoen kartta, joka ei koskaan yhdistä eri pisteitä yhteen) jos ja vain jos G on H : n aligraafi . Jos homomorfismi on bijektio (yksi yhteen vastaavuus G :n ja H :n kärkien välillä ) , jonka käänteisfunktio on myös graafihomomorfismi, niin f on graafi-isomorfismi [7] . $f:G\ to H$

Peitekartoitukset ovat yleinen homomorfismin tyyppi, joka kuvastaa topologian peitteen määritelmää ja monia ominaisuuksia [8] . Ne määritellään surjektiivisiksi homomorfismeiksi, jotka ovat paikallisesti bijektiivisiä, eli bijektiota jokaisen kärjen naapurustossa . Esimerkki on kaksiosainen graafi , joka on muodostettu graafista jakamalla jokainen kärki v ja korvaamalla jokainen reuna u , v kahdella reunalla ja . Alkuperäisen graafin funktiokuvaus v 0 ja v 1 - v on homomorfismi ja peittävä kuvaus. $v_{0}$ $v_{1}$ $u_{0},v_{1}$ ${\displaystyle v_{0},u_{1))$

Graafinen homeomorfismi on erillinen käsite, joka ei liity suoraan homomorfismiin. Karkeasti sanottuna se vaatii injektiokykyä, mutta mahdollistaa reunojen yhdistämisen poluille (eikä vain reunoille). Graafi-alamerkit ovat edelleen heikompi käsite.

Ytimet ja retracts

Kaksi kuvaajaa G ja H ovat homomorfisesti ekvivalentteja if ja [4] [5] [6] . $G\to H$ $H\to G$

Veto on homomorfismi r G : stä G :n aligraafiin H siten, että r ( v )= v jokaisella H : n kärjellä v . Tässä tapauksessa osagraafia H kutsutaan graafin G vetäytykseksi [9] .

Ydin on graafi, jolla ei ole homomorfismia minkään oikean aligraafin kanssa. Vastaavasti ydin voidaan määritellä graafiksi, joka ei ole minkään oikean aligraafin peruutus [10] . Mikä tahansa graafi G vastaa homomorfisesti ainutlaatuista ydintä (isomorfismiin asti), jota kutsutaan graafin G ytimeksi [11] [12] . Huomaa, että tämä ei pidä paikkaansa yleisten äärettömien graafien kohdalla [13] . Samat määritelmät koskevat kuitenkin suunnattuja graafia, ja suunnattu graafi vastaa myös yhtä ydintä. Mikä tahansa suuntaamaton ja suunnattu graafi sisältää ytimensä sekä retractina että generoituna osagraafina [9] .

Esimerkiksi kaikki täydelliset graafit K n ja kaikki parittomat syklit ( parittoman pituiset syklikaaviot) ovat ytimiä . Mikä tahansa 3-värinen graafi G , joka sisältää kolmion (eli jonka aligraafina on täydellinen graafi K 3 ), vastaa homeomorfisesti K 3 . Tämä johtuu siitä, että toisaalta graafin G 3-värjäys on sama kuin homomorfismi , kuten alla selitetään. Toisaalta mikä tahansa G:n aligraafi myöntää triviaalisti homomorfismin G :lle , mistä seuraa, että . Tämä tarkoittaa myös, että K 3 on minkä tahansa sellaisen graafin G ydin . Vastaavasti mikä tahansa kaksiosainen graafi , jossa on vähintään yksi reuna, vastaa K 2 :ta [14] . $G\to K_{3}$ $K_{3}\to G$

Suhde värityssivuihin

K -väritys jollekin kokonaisluvulle k on yhden k väristä osoittamista graafin G kullekin kärjelle siten, että kunkin reunan päätypisteillä on eri värit . k -Kävijän G värit vastaavat täsmälleen homomorfismeja G :stä täydelliseen graafiin K k [15] [16] . Lisäksi graafin K k kärjet vastaavat k väriä ja kaksi väriä ovat vierekkäin graafin K k pisteinä silloin ja vain, jos ne ovat erilaisia. Siksi funktio määrittelee homomorfismin K k :ssä silloin ja vain, jos graafin G vierekkäiset kärjet on värjätty eri väreillä. Erityisesti graafi G on k -väritettävä silloin ja vain jos se on K k -väritettävä [15] [16] .

Jos on kaksi homomorfismia ja , niin niiden superpositio on myös homomorfismi [17] . Toisin sanoen, jos graafi H voidaan värjätä k värillä ja on homomorfismi G :stä H , niin G voidaan myös värjätä k värillä. Tästä seuraa , että , jossa tarkoittaa graafin kromaattista lukua (pienin määrä värejä k , jolla graafi voidaan värittää) [18] . $G\to H$ ${\displaystyle H\to K_{k))$ ${\displaystyle G\to K_{k))$ $G\to H$ ${\näyttötyyli \chi (G)\leqslant \chi (H)}$ $\chi$

Vaihtoehdot

Yleisiä homomorfismeja voidaan pitää myös eräänlaisena värjäyksenä - jos kiinteän graafin H kärjet ovat sallittuja värejä ja graafin H reunat kuvaavat, mitkä värit ovat yhteensopivia , niin graafin G H -väritys on osoitus värit graafin G kärkipisteisiin niin , että viereiset kärjet saavat yhteensopivat värit . Monet graafin värityksen käsitteet sopivat tähän kaavioon ja voidaan ilmaista graafin homomorfismina eri kaavioperheissä. Jaksovärjäykset voidaan määritellä käyttämällä homomorfismeja täydellisten graafien kiertoon , jalostaa tavallista värityksen käsitettä [19] [20] . Murto- ja b - kertaiset värjäykset voidaan määritellä käyttämällä homomorfismeja Kneser -graafiin [21] [22] T-värjäykset vastaavat joidenkin äärettömien graafien homomorfismeja [23] . { Suunnatun graafin suunnattu väritys on homomorfismi minkä tahansa suunnatun graafin kanssa [24] . L(2,1)-väritys on paikallisesti injektiivinen homomorfismi polun komplementissa , mikä tarkoittaa, että sen täytyy olla injektiivinen jokaisen kärjen naapurustossa [25] .

Suuntaukset ilman pitkiä polkuja

Toinen mielenkiintoinen yhteys liittyy graafien orientaatioon . Suuntaamattoman graafin G orientaatio on mikä tahansa suunnattu graafi, joka saadaan valitsemalla kullekin reunalle kahdesta mahdollisesta orientaatiosta. Esimerkki täydellisen graafin K k orientaatiosta on transitiivinen turnaus , jonka kärjet ovat 1,2,…, k ja kaaret i :stä j :hen, kun i < j . Homomorfismi graafien G ja H orientaatioiden välillä antaa homomorfismin suuntaamattomien graafien G ja H välillä , jos jätämme orientaatiot huomiotta. Toisaalta, koska suuntaamattomien graafien välillä on homomorfismi, mikä tahansa H:n suunta voidaan kuvata G:n graafin orientaatioon , joten sillä on homomorfismi . Siksi graafi G on k -väritettävä (sillä on homomorfismi K k :ssä ) jos ja vain jos jollakin G :n orientaatiolla on homomorfismi kohdassa [26] . ${\vec {T}}_{k}$ $G\to H$ ${\vec {H}}$ ${\vec {G}}$ ${\vec {G}}$ ${\vec {H}}$ ${\vec {T}}_{k}$

Kansanperinteen lause sanoo, että mille tahansa k :lle suunnatulla graafilla G on homomorfismi silloin ja vain, jos se ei hyväksy homomorfismia kohdasta [27] . Tässä on suunnattu polku, jonka kärjet 1, 2, …, n ja kaaria i :stä i + 1: een, kun i =1, 2, …, n − 1. Siten graafi on k -väritettävä, jos ja vain jos sillä on orientaatio , joka ei myönnä homomorfismia . Tätä väitettä voidaan hieman vahvistaa sanomalla, että graafi on k -väritettävä, jos ja vain jos jokin orientaatio ei sisällä suunnattua polkua, jonka pituus on k (ei aligraafina). Tämä on Gallai-Hasse-Roy-Vitaver-lause . ${\vec {T}}_{k}$ ${\vec {P}}_{k+1}$ ${\vec {P}}_{n}$ ${\vec {P}}_{k+1}$ ${\vec {P}}_{k+1}$

Suhde rajoitteiden tyytyväisyysongelmiin

Esimerkkejä

Joitakin ajoitusongelmia voidaan mallintaa graafisen homomorfismien löytämisenä [15] [28] . Esimerkkinä voidaan yrittää ajoittaa harjoitukset niin, että saman opiskelijan kaksi kurssia eivät ole liian lähellä toisiaan. Kurssit muodostavat graafin G , jossa on reunat kahden kurssin välillä, jos niille osallistuu sama opiskelija. Ratojen mahdollinen suoritusaika muodostaa graafin H , jossa on reunat kahden aikaikkunan väliin, jos niiden välinen aikaetäisyys on riittävän suuri. Jos esimerkiksi halutaan syklinen viikkoaikataulu siten, että jokainen opiskelija tulee harjoittelemaan joka toinen päivä, sarake H täydentää saraketta C 7 . Graafinen homomorfismi G :stä H :hen on sitten kurssien jako aikaikkunoissa [15] . Jos haluat lisätä vaatimuksen esimerkiksi, että kenelläkään oppilaalla ei ole luokkaa perjantaina ja maanantaina, riittää, että graafista H poistetaan yksi reuna .

Yksinkertainen taajuusjakaumaongelma voidaan muotoilla seuraavasti. Langattomia verkkolähettimiä on useita . Sinun on valittava jokaisesta niistä taajuuskanava, jonka kautta se lähettää tietoja. Häiriöiden välttämiseksi maantieteellisesti lähellä olevissa lähettimissä on oltava kanavia, joiden taajuudet ovat riittävän erilaisia. Jos tämä ehto rajoittuu yksinkertaiseen kynnykseen käsitteille "maantieteellisesti lähellä" ja "riittävän kaukana", pätevä kanavavalinta vastaa jälleen graafin homomorfismia. Tässä graafi G on joukko lähettimiä, joiden välissä on reunat, jos ne ovat maantieteellisesti lähellä, ja graafi H on joukko kanavia, joiden reunat ovat kanavien välillä, jos taajuudet ovat riittävän erilaisia. Vaikka tämä malli on huomattavasti yksinkertaistettu, se sallii jonkin verran joustavuutta - lähetinparille, jotka eivät ole lähellä, mutta voivat häiritä toisiaan maantieteellisten ominaisuuksien vuoksi, voidaan lisätä kaari G :ssä . Ja kaari lähettimien välillä, jotka eivät toimi samaan aikaan, voidaan poistaa kaaviosta. Vastaavasti H -graafista voidaan poistaa reuna kaukana toisistaan olevien, mutta harmonisia häiriöitä aiheuttavien kanavaparien välillä [29] .

Kussakin tapauksessa näissä yksinkertaistetuissa malleissa on monia piirteitä, jotka tulisi kehittää käytännössä [30] . Rajoitustyytyväisyysongelmat , jotka yleistävät graafin homomorfismiongelmia, voivat ilmaista lisäehtoja (kuten yksilöllisiä mieltymyksiä tai rajoituksia vastaavien tehtävien lukumäärälle). Tämä tekee malleista realistisempia ja käytännöllisempiä.

Muodollinen näkökulma

Suunnatut ja suunnatut graafit voidaan ajatella yleisemmän käsitteen, jota kutsutaan relaatiorakenteiksi jotka määritellään joukoksi, jossa on useita relaatioita), esiintymisinä. Suunnatut graafit ovat rakenteita, joissa on yksi binäärirelaatio (viereisyys) alueella (joukko pisteitä) [31] [3] . Tästä näkökulmasta tällaisten rakenteiden homomorfismit ovat täsmälleen graafihomomorfismeja. Yleisessä tapauksessa kysymys homomorfismin löytämisestä rakenteesta toiseen on rajoitustyytyväisyysongelma ( CSP) . Kaavioiden tapaus tarjoaa konkreettisen ensimmäisen askeleen, joka auttaa ymmärtämään monimutkaisempia rajoitustyytyväisyysongelmia. Monet algoritmiset menetelmät graafin homomorfismien löytämiseksi, kuten backtracking , rajoitteen leviäminen ja paikallinen haku , ovat sovellettavissa kaikkiin rajoitusten tyydytysongelmiin [3] .

Graafille G ja H kysymys siitä, onko graafilla G homomorfismi graafin H kanssa, vastaa rajoitteiden tyydytysongelman erityistapausta, jossa on vain yksi rajoitus [3] . Tässä tehtävässä muuttujat ovat graafin G kärjet ja kunkin muuttujan alue on graafin H kärkijoukko . Ratkaisu on funktio, joka osoittaa jokaiselle muuttujalle alkion alueelta siten, että funktio f kuvaa V ( G ) arvoon V ( H ). Kukin graafin G reuna tai kaari [32] ( u , v ) vastaa sitten rajoitusta (( u , v ), E( H )). Tämä rajoitus ilmaisee, että ratkaisun on kartoitettava kaari ( u , v ) pariin ( f ( u ), f ( v )), joka on relaatio E ( H ), eli graafin H kaareen . Ongelman ratkaisu on ratkaisu, joka täyttää kaikki rajoitukset, eli se on täsmälleen homomorfismi G :stä H :hen .

Homomorfismien rakenne

Homomorfismien superpositiot ovat homomorfismeja [17] . Erityisesti relaatio graafissa on transitiivinen (ja triviaalisti refleksiivinen), joten tämä relaatio on ennakkotilaus graafissa [33] . Merkitsemme graafin G homomorfismiekvivalenssiluokkaa [ G ]:lla. Ekvivalenssiluokka voidaan esittää yhdellä ytimellä [ G ]:ssä. Relaatio on osittain järjestetty näille ekvivalenssiluokille. Se määrittelee osittain järjestetyn joukon [34] . $\to$ $\to$

Olkoon G < H , että G:stä H:hen on homomorfismi, mutta ei homomorfismia H : sta G :hen . Relaatio on tiheä järjestys , mikä tarkoittaa, että kaikille (suuntaamattomille) grafeille G , H , joissa G < H , on olemassa graafi K , jossa G < K < H (tämä pätee kaikissa tapauksissa paitsi triviaalisissa tapauksissa tai ) [35] [36] [37] . Esimerkiksi minkä tahansa kahden täydellisen graafin välillä (paitsi ) on äärettömän monta syklistä täydellistä kuvaajaa , jotka vastaavat rationaalilukuja [38] [39] . $\to$ ${\displaystyle G=K_{0))$ $K_1$ ${\displaystyle K_{0},K_{1))$

Homomorfismin mukaan osittain järjestetty graafisen ekvivalenssiluokkien joukko on distributiivinen hila , jossa [ G ] ja [ H ] liitto määritellään (ekvivalenssiluokka) disjunktiliitoksi ja [ G ] leikkauspiste. ] ja [ H ] määritelty tensorituloksi (graafien G ja H valinnalla ekvivalenssiluokkien [ G ] ja [ H ] edustajiksi ei ole merkitystä) [40] [41] . Tämän hilan elementit, jotka ovat redusoitumattomia liitossa , ovat täsmälleen kytkettyjä graafia. Tämä voidaan osoittaa käyttämällä sitä tosiasiaa, että homomorfismi kartoittaa yhdistetyn graafin kohdegraafin yhdistettyyn komponenttiin [42] [43] . Tämän hilan leikkauspisteen redusoitumattomat elementit ovat täsmälleen kertovia kuvaajia . Nämä ovat graafeja K siten, että tulolla on homomorfismi K :ssä vain, jos jollakin graafista G tai H on tällainen homomorfismi. Multiplikatiivisten graafien löytäminen on Hedetniemen arvelun ydin [44] [45] . $[G\cup H]$ $[G\times H]$ $G\ kertaa H$

Graafisten homomorfismit muodostavat myös kategorian , jossa graafit ovat esineitä ja homomorfismit nuolet [46] . Alkuobjekti on tyhjä graafi, kun taas pääteobjekti on graafi, jossa on yksi kärki ja yksi silmukka kyseisessä kärjessä. Graafeiden tensoritulo on luokkateorian tulo ja eksponentiaalinen graafi on luokan eksponentiaalinen objekti [45] [47] . Koska nämä kaksi operaatiota on aina määritelty, graafien luokka on suorakulmainen suljettu luokka . Samoista syistä homomorfismien graafien ekvivalenssiluokkien hila on itse asiassa Heyting-algebra [45] [47] .

Suunnattujen graafien kohdalla pätevät samat määritelmät. Erityisesti se on osittain järjestetty suunnattujen graafien ekvivalenssiluokkiin. Tämä järjestys eroaa suuntaamattomien graafien ekvivalenssiluokkien järjestyksestä, mutta sisältää sen alijärjestyksenä. Tämä johtuu siitä, että mikä tahansa suuntaamaton graafi voidaan ajatella suunnatuksi, jossa mikä tahansa kaari ( u , v ) esiintyy yhdessä käänteiskaaren ( v , u ) kanssa, eikä tämä muuta homomorfismin määritelmää. Suunnattujen graafien järjestys on jälleen distributiivinen hila ja Heyting-algebra, jonka liitos- ja leikkausoperaatiot on määritelty kuten aiemmin. Tämä järjestys ei kuitenkaan ole tiukka. On myös luokka, jossa on suunnatut graafit objekteina ja homomorfismit nuolina, mikä on jälleen karteesinen suljettu luokka [48] [47] . $\to$ $\to$ $\to$

Vertaansa vailla olevat kaaviot

On olemassa monia vertaansa vailla olevia graafisia homomorfismien esijärjestyksen mukaan, eli graafipareja siten, ettei homomorfismeja ole toistensa välillä [49] . Yksi tapa rakentaa tällaisia graafia on ottaa huomioon graafin G pariton ympärysmitta , eli sen lyhimmän parittoman pituisen syklin pituus. Pariton ympärysmitta on vastaavasti pienin pariton luku g , jolle on olemassa homomorfismi sykligraafista, jossa on g pistettä G :hen . Tästä syystä, jos , niin graafin G pariton ympärysmitta on suurempi tai yhtä suuri kuin graafin H pariton ympärysmitta [50] . $G\to H$

Toisaalta, jos , niin graafin G kromaattinen luku on pienempi tai yhtä suuri kuin graafin H kromaattinen luku . Siksi, jos graafilla G on ehdottomasti suurempi pariton ympärysmitta kuin H ja tiukasti suurempi kromaattinen luku kuin H , niin G ja H ovat vertaansa vailla [49], jonka ympärysmitta on 4 51[)5ympärysmittaparitonja ] , joten se on yhteensopimaton kolmio K 3 . $G\to H$

Esimerkkejä kaavioista, joissa on mielivaltaisen suuret parittoman ympärysmitan ja kromaattisen luvun arvot, ovat Kneser-graafit [52] ja yleistyneet Mychelskilaiset [53] . Tällaisten kaavioiden sarja, jossa molempien parametrien arvot kasvavat samanaikaisesti, antaa äärettömän määrän vertaansa vailla olevia kaavioita ( antiketju homomorfismien esijärjestyksessä) [54] . Muita ominaisuuksia, kuten homomorfismien esijärjestyksen tiheys , voidaan todistaa käyttämällä tällaisia perheitä [55] . On myös mahdollista rakentaa kaavioita, joissa on suuret kromaattisen luvun ja ympärysmitan arvot, ei vain pariton ympärysmitta, mutta vaikeampaa (katso Graafin ympärysmitta ja väritys ).

Suunnattujen graafien joukosta on paljon helpompi löytää vertaansa vailla olevia pareja. Tarkastellaan esimerkiksi suunnattuja syklikaavioita , joiden kärjet 1, 2, …, n ja reunat i :stä i + 1:een ( i =1, 2, …, n − 1) ja n :stä 1:een. On olemassa homomorfismi välillä - silloin ja vain kun n on k :n kerrannainen . Erityisesti suunnatut syklikaaviot , joiden alkuluku on n , ovat kaikki vertaansa vailla [56] . ${\vec {C}}_{n}$ ${\vec {C}}_{n}$ ${\vec {C}}_{k}(n,k\geqslant 3)$ ${\vec {C}}_{n}$

Laskennallinen monimutkaisuus

Graafihomomorfismitehtävässä ongelman esiintymä koostuu graafiparista ( G , H ), ja ratkaisu on homomorfismi G : stä H :hen. Yleinen ratkaistavuusongelma , joka kysyy, onko tähän ongelmaan ratkaisu, on NP-täydellinen [57] . Graafiset rajoitukset johtavat kuitenkin useisiin erilaisiin ongelmiin, joista osa on helpompi ratkaista. Vasemman graafin G rajoituksia käyttävät menetelmät ovat hyvin erilaisia kuin oikean graafin H menetelmät , mutta jokaisessa tapauksessa kaksijakoisuus (tiukat rajat yksinkertaisten ja monimutkaisten tapausten välillä) tunnetaan tai oletetaan.

Homomorfismit kiinteään graafiin

Homomorfismiongelmaa kiinteällä graafilla H kunkin esiintymän oikealla puolella kutsutaan H -väritysongelmaksi. Kun H on täydellinen graafi K k , tämä on graafin k -väritysongelma , joka on ratkaistavissa polynomiajassa k = 0, 1, 2 ja on muuten NP-täydellinen [58] . Erityisesti graafin G K 2 -värjäyksen mahdollisuus vastaa kaksiosaista graafia G , joka voidaan todentaa lineaarisessa ajassa. Yleisemmin ottaen, kun H on kaksiosainen graafi, H -värjäyksen mahdollisuus vastaa K 2 -värjäyksen mahdollisuutta (tai K 0 / K 1 -väritettävä, kun H on tyhjä tai siinä ei ole reunoja), ja näin ollen yhtä helppoa ratkaise [59] . Pavol Hell ja Jaroslav Neshetril osoittivat, ettei mikään muu tapaus ole helppo suuntaamattomille kaavioille:

Hell-Neshetril-lause (1990): H - väritysongelma on luokassa P, jos H on kaksiosainen ja NP-kova muuten [60] [61] .

Lause tunnetaan myös (ohjaamattoman) graafihomomorfismin dikotomialauseena , koska se jakaa H -väritysongelmat NP täydellisiin ja luokan P ongelmiin ilman välitapauksia . Suunnattujen graafien kohdalla tilanne on monimutkaisempi ja itse asiassa vastaa yleisempää kysymystä, joka koskee rajoitusten täyttämisen monimutkaisuuden kuvaamista [62] . Osoittautuu, että suunnattujen graafien H -väritysongelmat ovat yhtä yleisiä ja yhtä erilaisia kuin rajoitteiden tyytyväisyysongelmat minkä tahansa muun rajoituksen kanssa [63] [64] . Muodollisesti (äärellinen) rajoituskieli Γ on äärellinen alue ja äärellinen joukko suhteita siinä. CSP( Γ ) on rajoitteiden tyytyväisyysongelma, jossa ilmentymät saavat käyttää vain Γ :n rajoituksia .

Lause (Feder, Vardy 1998): Jokaiselle rajoituskielelle Γ CSP( Γ ) on polynomipelkistyksen jälkeen ekvivalentti johonkin H -väritysongelmaan jollekin suunnatulle graafille H [64] .

Intuitiivisesti tämä tarkoittaa, että mikä tahansa algoritmitekniikka tai monimutkaisuustulos, joka soveltuu suunnattujen graafien H H -väritysongelmiin, pätee myös yleisiin rajoitusten tyydytysongelmiin. Erityisesti voidaan kysyä, voidaanko Helvetin-Neshetrilin lausetta laajentaa suunnattuihin graafisiin. Yllä olevan lauseen mukaan tämä vastaa Feder-Vardin arvelua rajoitteiden tyytyväisyysongelmien dikotomiasta, jossa todetaan, että mille tahansa rajoituskielelle Γ CSP( Γ ) on joko NP-täydellinen tai kuuluu luokkaan P [57] .

Homomorfismit kiinteästä kaavioperheestä

Homomorfismiongelma yhden kiinteän graafin G kanssa vasemmalla voidaan ratkaista tyhjentävällä haulla ajassa | V ( H )| O(| V ( G )|) , eli polynomi syötegraafin H koossa [65] . Toisin sanoen, ongelma on triviaali P:ssä graafisille G , joiden koko on rajoitettu. Mielenkiintoinen kysymys on sitten, mitkä muut graafin G ominaisuudet koon lisäksi mahdollistavat polynomialgoritmit.

Avainominaisuus osoittautuu puunleveydeksi , mitta siitä, kuinka samanlainen graafi on puun kanssa. Graafille G , jonka puunleveys on enintään k , ja graafille H homomorfismiongelma voidaan ratkaista ajassa | V ( H )| O( k ) vakiodynaamisilla ohjelmointimenetelmillä . Itse asiassa riittää oletus, että G :n ytimellä on puunleveys enintään k . Tämä on totta, vaikka ydintä ei tunneta [66] [67] .

Algoritmin ilmaisin, jossa on ajoaika| V ( H )| O( k ) -arvoa ei voida merkittävästi pienentää - ei ole algoritmia, joka toimii ajassa | V ( H )| o(tw( G ) /log tw( G )) , jos eksponentiaalinen aikahypoteesi ( ETH) on totta, vaikka syötettä rajoittaisi mikä tahansa rajattoman puuleveyden graafiluokka [68] . ETH on todistamaton oletus, samanlainen kuin P ≠ NP -oletus , mutta tiukempi. Samoilla oletuksilla ei ole muita ominaisuuksia, joita voitaisiin käyttää polynomiaikaisten algoritmien johtamiseen. Tämä formalisoidaan lauseella:

Lause (Martin Grohe): Laskettavissa olevalle graafiluokalle c :n homomorfismitehtävä kuuluu P:lle, jos ja vain jos graafien ytimet ovat puun leveydeltään rajoitettuja (ETH-oletuksessa) [67] .

{\mathcal {G}}

{\näyttötyyli (G,H)}

G\in {\mathcal {G}}

{\mathcal {G}}

Voidaan kysyä, onko ongelma ratkaistavissa mielivaltaisen suurella riippuvuudella G , mutta kiinteällä polynomiriippuvuudella graafin H koosta. Vastaus on kyllä, jos rajoitamme graafin G luokkaan, jonka ytimet ovat puuleveydeltään rajoitettuja, ja ei kaikkiin muihin luokkiin [67] . Parametrisoidun monimutkaisuuden kielellä tämä lausunto sanoo muodollisesti, että graafin homomorfismiongelma , joka parametroidaan G :n koon (särmien lukumäärän) mukaan , osoittaa kaksijakoisuutta. Kiinteäparametrinen on päätettävissä , jos luokan graafien ytimet ovat puuleveydeltään rajoitettuja, ja muuten W[1]-täydellinen ${\mathcal {G}}$ ${\mathcal {G}}$

Sama väite pätee yleisempiin rajoitustyytyväisyysongelmiin (tai toisin sanoen relaatiorakenteisiin). Ainoa vaadittu oletus on, että rajoitukset voivat sisältää vain rajoitetun määrän muuttujia. Parametri on tällöin päärajoitusgraafin puunleveys [ [68] .

Katso myös

Hypoteesi Sidorenko

Muistiinpanot

↑ Helvetti, Nešetřil, 2004 , s. 27.
↑ Helvetti, Nešetřil, 2004 , s. 109.
↑ 1 2 3 4 Helvetti, Nešetřil, 2008 .
↑ 12 Cameron , 2006 .
↑ 1 2 Geňa, Tardif, 1997 .
↑ 1 2 Helvetti, Nešetřil, 2004 .
↑ Gena, Tardif, 1997 , Havainto 2.3.
↑ Godsil, Royle, 2001 , s. 115.
↑ 1 2 Hell, Nešetřil, 2004 , s. 19.
↑ Helvetti, Nešetřil, 2004 , Ehdotus 1.31.
↑ Cameron, 2006 , Ehdotus 2.3.
↑ Helvetti, Nešetřil, 2004 , Seuraus 1.32.
↑ Helvetti, Nešetřil, 2004 , s. 34.
↑ Cameron, 2006 , s. 4 (ehdotus 2.5).
↑ 1 2 3 4 Cameron, 2006 , s. yksi.
↑ 1 2 Helvetti, Nešetřil, 2004 , Ehdotus 1.7.
↑ 1 2 Hell, Nešetřil, 2004 , §1.7.
↑ Helvetti, Nešetřil, 2004 , Seuraus 1.8.
↑ Helvetti, Nešetřil, 2004 , §6.1.
↑ Gena, Tardif, 1997 , §4.4.
↑ Helvetti, Nešetřil, 2004 , §6.2.
↑ Gena, Tardif, 1997 , §4.5.
↑ Helvetti, Nešetřil, 2004 , §6.3.
↑ Helvetti, Nešetřil, 2004 , §6.4.
↑ * Fiala J., Kratochvíl J. Graafisten osittaiset kannet // Discussions Mathematicae Graph Theory. - 2002. - T. 22 , no. 1 . — S. 89–99 . - doi : 10.7151/dmgt.1159 .
↑ Helvetti, Nešetřil, 2004 , s. 13–14.
↑ Helvetti, Nešetřil, 2004 , Ehdotus 1.20.
↑ Helvetti, Nešetřil, 2004 , §1.8.
↑ Helvetti, Nešetřil, 2004 , s. 30–31.
↑ Helvetti, Nešetřil, 2004 , s. 31–32.
↑ Helvetti, Nešetřil, 2004 , s. 28. Huomaa, että artikkelin relaatiorakenteita kutsutaan relaatiojärjestelmiksi .
↑ Muista, että yleensä suunnatun graafin reunoja kutsutaan kaareiksi.
↑ Helvetti, Nešetřil, 2004 , §3.1.
↑ Helvetti, Nešetřil, 2004 , Lause 3.1.
↑ Helvetti, Nešetřil, 2004 , Lause 3.30.
↑ Geňa, Tardif, 1997 , Lause 2.33.
↑ Welzl, 1982 , s. 29–41.
↑ Helvetti, Nešetřil, 2004 , s. 192.
↑ Gena, Tardif, 1997 , s. 127.
↑ Hell, Nešetřil, 2004, lause 3.2, distributiivisuus on esitetty lauseessa 2.4.
↑ Geňa, Tardif, 1997 , Lause 2.37.
↑ Kwuida, Lehtonen, 2011 , s. 251-265.
↑ Harmaa, 2014 , Lemma 3.7.
↑ Tardif, 2008 , s. 46–57.
↑ 1 2 3 Dwight, Sauer, 1996 , s. 125–139.
↑ Helvetti, Nešetřil, 2004 , s. 125.
↑ 1 2 3 Harmaa, 2014 .
↑ Brown, Morris, Shrimpton, Wensley, 2008 .
↑ 1 2 Hell, Nešetřil, 2004 , s. 7.
↑ Gena, Tardif, 1997 , Havainto 2.6.
↑ Weisstein , Eric W. Grötzsch Graph Wolfram MathWorld -verkkosivustolla .
↑ Gena, Tardif, 1997 , Proposition 3.14.
↑ Gyárfás, Jensen, Stiebitz, 2004 , s. 1–14.
↑ Helvetti, Nešetřil, 2004 , Ehdotus 3.4.
↑ Helvetti, Nešetřil, 2004 , s. 96.
↑ Helvetti, Nešetřil, 2004 , s. 35.
↑ 1 2 Bodirsky, 2007 , §1.3.
↑ Helvetti, Nešetřil, 2004 , §5.1.
↑ Helvetti, Nešetřil, 2004 , Ehdotus 5.1.
↑ Helvetti, Nešetřil, 2004 , §5.2.
↑ Helvetti, Nešetřil, 1990 , s. 92–110.
↑ Helvetti, Nešetřil, 2004 , §5.3.
↑ Helvetti, Nešetřil, 2004 , Lause 5.14.
↑ 1 2 Feder, Vardi, 1998 , s. 57–104.
↑ Cygan, Fomin, Golovnev et ai., 2016 , s. 1643-1649
↑ Dalmau, Kolaitis, Vardi, 2002 , s. 310–326.
↑ 1 2 3 Grohe, 2007 .
↑ 12. Marx , 2010 , s. 85–112.

Kirjallisuus

Welzl E. Väriperheet ovat tiheitä // Teoria. Comput. sci. . - 1982. - T. 17 . — s. 29–41 . - doi : 10.1016/0304-3975(82)90129-3 .
Pavol Hell, Jaroslav Nesetzil. H-värityksen monimutkaisuudesta // 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. Graafeista, joilla on vahvasti riippumattomia väriluokkia // J. Graph Theory . - 2004. - T. 46 , no. 1 . - S. 1-14 . - doi : 10.1002/jgt.10165 .

Leonard Kwuida, Erkko Lehtonen. Merkittyjen posettien homomorfismijärjestyksestä // Järjestys . - Springer, 2011. - T. 28 , no. 2 . — S. 251–265 . - doi : 10.1007/s11083-010-9169-x . - arXiv : 0911.0200 .
Tardif C. Hedetniemen arvelu, 40 vuotta myöhemmin // Graph Theory Notes of New York. - 2008. - T. 54 . — s. 46–57 .
Dwight D., Sauer N. Hilat, jotka syntyvät Hedetniemen arvelun kategorisissa tutkimuksissa // Discrete Math. . - 1996. - T. 152 , no. 1-3 . — S. 125–139 . - doi : 10.1016/0012-365X(94)00298-W .
Daniel Marx. Voitko Treewidthin? // Laskennan teoria . - 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. Rajoitustyytyväisyys, rajattu puunleveys ja äärellisen muuttujan logiikka. - 2002. - S. 310-326. - doi : 10.1007/3-540-46135-3_21 .
Martin Grohe. Homomorfismin ja rajoitteiden tyytyväisyysongelmien monimutkaisuus nähtynä toiselta puolelta // J. ACM . - 2007. - T. 54 , no. 1 . - doi : 10.1145/1206035.1206036 .
Tomás Feder, Moshe Y. Vardi . Monotonisen monadisen SNP:n laskennallinen rakenne ja rajoitteiden tyytyväisyys: tutkimus datalogin ja ryhmäteorian kautta // SIAM J. Comput. . - 1998. - T. 28 , no. 1 . — s. 57–104 . - doi : 10.1137/S0097539794266766 .

Yleiset kirjat

Peter Cameron. Kaaviohomomorfismit, kombinatoriikan opiskeluryhmän huomautukset . – 2006.
Pavol Hell, Jaroslav Nesetzil. Kaaviot ja homomorfismit . - Oxford University Press, 2004. - V. 28 . — ISBN 0-19-852817-5 .
Geňa H., Tardif C. Graafisten homomorfismit: rakenne ja symmetria // 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. Homomorfismit // Algebrallinen graafiteoria. - Springer-Verlag New York, 2001. - T. 207. - (Matematiikan tutkinnon tekstit). — ISBN 978-1-4613-0163-9 . - doi : 10.1007/978-1-4613-0163-9 .

Yleisalgebrassa ja rajoitusten alainen

Bodirsky M. Graph Homomorfismit ja yleisalgebra, Kurssin muistiinpanot . – 2007.
Pavol Hell, Jaroslav Nesetzil. Väritys, rajoitusten tyytyväisyys ja monimutkaisuus // Computer Science Review. - 2008. - Osa 2 , numero. 2 . — S. 143–163 . - doi : 10.1016/j.cosrev.2008.10.003 .

Hilateoriassa ja kategoriateoriassa

Brown R., Morris I., Shrimpton J., Wensley CD Graphs of morphisms of graphs // Electronic Journal of Combinatorics . - 2008. - T. 15 , no. 1 . - S. A1 .
Harmaa CT Digraph Lattice . — 2014. ( AMSI Vacation Research Scholarships , opiskelijatutkimusraportti, jota ohjasivat Brian Davey ja Jane Pitkethly, La Trobe University ).