Graf homomorfism - Graph homomorphism

Inte att förväxla med graf homeomorfism .

Rita homomorfism från J5 till C5
En homomorfism från blomman snarkar J 5 in i cykeldiagrammet C 5 .
Det är också en indragning på underbilden på de centrala fem hörnpunkterna. Sålunda J 5 är i själva verket homomorphically ekvivalent med kärnan C 5 .

I det matematiska området grafteori är en grafhomomorfism en kartläggning mellan två grafer som respekterar deras struktur. Mer konkret är det en funktion mellan toppsatserna med två grafer som kartlägger intilliggande hörn till intilliggande hörn.

Homomorfismer generaliserar olika föreställningar om graffärgning och möjliggör uttryck för en viktig klass av problem med begränsningstillfredsställelse , såsom vissa schemaläggningsproblem eller frekventilldelningsproblem . Det faktum att homomorfismer kan komponeras leder till rika algebraiska strukturer: en förbeställning på grafer, ett distribuerande gitter och en kategori (en för oriktade grafer och en för riktade grafer). Den beräkningskomplexiteten för att hitta en homomorfism mellan givna grafer är oöverkomliga i allmänhet, men en hel del är känt om särskilda fall som är lösbara i polynomisk tid . Gränser mellan behandlingsbara och svåråtkomliga fall har varit ett aktivt forskningsområde.

Definitioner

I den här artikeln, om inte annat anges, är graferna ändliga, oriktade grafer med slingor tillåtna, men flera kanter (parallella kanter) tillåts inte. En grafhomomorfism f   från en graf G = ( V ( G ), E ( G )) till en graf H = ( V ( H ), E ( H )), skriven

f  : G → H

är en funktion från V ( G ) till V ( H ) som mappar slutpunkterna för varje kant i G till slutpunkterna för en kant i H . Formellt innebär { u , v } ∈ E ( G ) { f ( u ), f ( v )} ∈ E ( H ), för alla par av toppar u , v i V ( G ). Om det existerar någon homomorfism från G till H , då G sägs vara homomorfiska till H eller H -colorable . Detta betecknas ofta som bara:

G → H .

Ovanstående definition utvidgas till riktade grafer. Då, för en homomorfism f  : G → H , ( f ( u ), f ( v )) är en båge (riktad kant) för H när ( u , v ) är en båge av G .

Det finns en injektiv homomorfism från G till H (dvs en som aldrig kartor distinkta hörn till en spets) om och endast om G är en subgraf av H . Om en homomorfism f  : G → H är en bindning (en en-till-en-korrespondens mellan hörn i G och H ) vars inversa funktion också är en grafhomomorfism, så är f en grafisomorfism .

Täckande kartor är en speciell typ av homomorfismer som speglar definitionen och många egenskaper hos täckningskartor i topologi . De definieras som surjectiva homomorfismer (dvs något kartläggs till varje toppunkt) som också är lokalt bijektiva, det vill säga en bifogning i närheten av varje toppunkt. Ett exempel är det dubbla dubbla omslaget , bildat av ett diagram genom att dela upp varje toppunkt v i v 0 och v 1 och ersätta varje kant u , v med kanterna u 0 , v 1 och v 0 , u 1 . Funktionsmappningen v 0 och v 1 i omslaget till v i originalgrafen är en homomorfism och en täckningskarta.

Graph homeomorfi är ett annat begrepp, inte direkt relaterade till homomorfismer. Grovt sett kräver det injektivitet, men tillåter mappning av kanter till banor (inte bara mot kanter). Mindreåriga är en ännu mer avslappnad uppfattning.

Kärnor och dragningar

K 7 , den kompletta grafen med 7 hörn, är en kärna.
Huvudartikel: Core (grafteori)

Två diagram G och H är homomorphically ekvivalent om G → H och H → G . Kartorna är inte nödvändigtvis surjektiva eller injektiva. Till exempel är de fullständiga bipartitdiagrammen K 2,2 och K 3,3 homomorfiskt ekvivalenta: varje karta kan definieras som att ta vänster (resp. Höger) halva av domängrafen och mappa till bara ett toppunkt till vänster (resp. . höger) hälften av bilddiagrammet.

En tillbakadragning är en homomorfism r från en graf G till en subgraf H av G så att r ( v ) = v för varje vertex v av H . I detta fall subgraf H kallas en indragnings av G .

En kärna är ett diagram utan homomorfism till någon korrekt subgraf. På motsvarande sätt kan en kärna definieras som ett diagram som inte dras tillbaka till någon korrekt subgraf. Varje graf G är homomorphically ekvivalent med en unik kärna (upp till isomorfism), kallas kärnan av G . Detta gäller i allmänhet inte för oändliga diagram. Samma definitioner gäller dock för riktade grafer och en riktad graf motsvarar också en unik kärna. Varje graf och varje riktad graf innehåller sin kärna som en indragning och som en inducerad subgraf .

Till exempel alla komplett graf K n och alla udda cykler ( cykel grafer med udda längd) är kärnor. Varje 3-färgbar graf G som innehåller en triangel (det vill säga har hela grafen K 3 som en subgraf) är homomorf ekvivalent med K 3 . Detta beror på att, å ena sidan, en 3-färgning av G är samma som en homomorfism G → K 3 , såsom förklaras nedan. Å andra sidan, varje subgraf av G medger trivialt en homomorfism till G , vilket innebär K 3 → G . Detta innebär också att K 3 är kärnan av en sådan graf G . På samma sätt motsvarar varje graf i två delar som har minst en kant K 2 .

Anslutning till färgämnen

En k -färgning , för vissa heltal k , är en tilldelning av en av k- färger till varje toppunkt i en graf G så att slutpunkterna för varje kant får olika färger. De k -colorings av G motsvarar exakt homomorfismer från G till den fullständiga grafen K k . Indeed, det hörn av K k motsvarar de k färger och två färger är närliggande som hörn i K k om och endast om de är olika. Därför definierar en funktion en homomorfism till K k om och endast om den mappar intilliggande hörn av G till olika färger (dvs det är en k- färg). I synnerhet, G är k -colorable om och endast om det är K k -colorable.

Om det finns två homomorfismer G → H och H → K k , är deras sammansättning G → K k också en homomorfism. Med andra ord, om ett diagram H kan färgas med k färger, och det finns en homomorfism från G till H , kan G också vara k- färgad. Därför antyder G → H χ ( G ) ≤ χ ( H ), där χ betecknar det grafiska antalet i en graf (den minsta k för vilken den är k -färgbar).

Varianter

Allmänna homomorfismer kan också ses som en typ av färgning: om hörnpunkterna i en fast graf H är de tillgängliga färgerna och kanterna på H beskriver vilka färger som är kompatibla , då är en H- färgning av G en tilldelning av färger till hörn av G så att intilliggande hörn får kompatibla färger. Många begrepp om graffärgning passar in i detta mönster och kan uttryckas som grafhomomorfismer i olika graffamiljer. Cirkulära färgämnen kan definieras med hjälp av homomorfismer i cirkulära kompletta grafer , vilket förfinar det vanliga begreppet färgämnen. Fraktionerad färgning och b- färgning kan definieras med hjälp av homomorfismer i Kneser-grafer . T-färgämnen motsvarar homomorfism i vissa oändliga grafer. En orienterad färgning av en riktad graf är en homomorfism i vilken orienterad graf som helst . En L (2,1) -färgning är en homomorfism i komplementet till bandiagrammet som är lokalt injektivt, vilket betyder att det krävs att vara injektivt i närheten av varje toppunkt.

Orienteringar utan långa vägar

Huvudartikel: Gallai – Hasse – Roy – Vitaver teorem

En annan intressant koppling gäller orienteringar av grafer. En orientering av en icke riktad graf G är vilken riktad graf som helst som erhålls genom att välja en av de två möjliga orienteringarna för varje kant. Ett exempel på en orientering av hela grafen K k är den transitiva turneringen T → k med hörn 1,2,…, k och bågar från i till j när jag < j . En homomorfism mellan riktningarna för graferna G och H ger en homomorfism mellan de oriktade graferna G och H , helt enkelt genom att bortse från riktningarna. Å andra sidan, med tanke på en homomorfism G → H mellan oriktade grafer, kan varje orientering H → av H dras tillbaka till en orientering G → av G så att G → har en homomorfism till H → . Därför en graf G är k -colorable (har en homomorfism till K k ) om och endast om viss orientering av G har en homomorfism till T → k .

En folklore-sats säger att för alla k har en riktad graf G en homomorfism till T → k om och bara om den inte medger någon homomorfism från den riktade vägen P → k +1 . Här är P → n den riktade grafen med hörn 1, 2,…, n och kanter från i till i + 1, för i = 1, 2,…, n - 1. Därför är en graf k -färgad om och endast om den har en orientering som inte medger någon homomorfism från P → k +1 . Detta uttalande kan förstärkas något för att säga att en graf är k -färgad om och endast om någon orientering inte innehåller någon riktad längd k (ingen P → k +1 som subgraf). Detta är satsen Gallai – Hasse – Roy – Vitaver .

Anslutning till problem med tillfredsställelse

Exempel

Diagram H för icke-på varandra följande vardagar, isomorf till komplementdiagrammet för C 7 och till den cirkulära klicken K 7/2

Vissa schemaläggningsproblem kan modelleras som en fråga om hur man hittar grafhomomorfier. Som ett exempel kanske man vill tilldela workshopkurser till tidsluckor i en kalender så att två kurser som deltas av samma student inte är för nära varandra i tid. Kurserna utgör ett diagram G , med en kant mellan två kurser som någon vanlig student deltar i. Tidsluckorna bildar ett diagram H med en kant mellan två slitsar som är tillräckligt avlägsna i tiden. Till exempel, om man vill ha ett cykliskt veckovis schema, så att varje student får sina workshopkurser på icke-på varandra följande dagar, skulle H vara komplementdiagrammet för C 7 . En grafhomomorfism från G till H är då ett schema som tilldelar kurser till tidsluckor, som specificerat. För att lägga till ett krav som säger att t.ex. har ingen enskild elev kurser på både fredag och måndag, räcker det att ta bort motsvarande kanten från H .

Ett enkelt frekvensallokeringsproblem kan specificeras enligt följande: ett antal sändare i ett trådlöst nätverk måste välja en frekvenskanal som de ska överföra data till. För att undvika störningar bör sändare som är geografiskt nära använda kanaler med frekvenser som ligger långt ifrån varandra. Om detta tillstånd approximeras med en enda tröskel för att definiera 'geografiskt nära' och 'långt ifrån varandra', motsvarar ett giltigt kanalval igen en grafhomomorfism. Det ska gå från grafen för sändare G , med kanter mellan par som är geografiskt nära, till grafen för kanaler H , med kanter mellan kanaler som ligger långt ifrån varandra. Även denna modell är ganska förenklat, gör det erkänner en viss flexibilitet: sändare par som inte är nära men skulle kunna störa på grund av geografiska kan läggas till kanterna på G . De som inte kommunicerar samtidigt kan tas bort från den. På liknande sätt, kanalpar som ligger långt ifrån varandra, men uppvisar överton kan interferens avlägsnas från kanten uppsättningen av H .

I båda fallen visar dessa förenklade modeller många av de frågor som måste hanteras i praktiken. Problem med begränsningstillfredsställelse , som generaliserar problem med grafhomomorfism, kan uttrycka olika ytterligare typer av villkor (såsom individuella preferenser eller gränser för antalet sammanfallande uppdrag). Detta gör att modellerna kan göras mer realistiska och praktiska.

Formell vy

Grafer och riktade grafer kan ses som ett specialfall av den betydligt mer allmänna uppfattningen kallas relationsstrukturer (definierat som ett set med en tupel av förbindelserna på det). Riktade grafer är strukturer med en enda binär relation (angränsning) på domänen (toppunktuppsättningen). Enligt denna uppfattning är homomorfismer av sådana strukturer exakt grafhomorformer. I allmänhet är frågan om att hitta en homomorfism från en relationsstruktur till en annan ett problem med begränsningstillfredsställelse (CSP). Fallet med diagram ger ett konkret första steg som hjälper till att förstå mer komplicerade CSP. Många algoritmiska metoder för att hitta grafhomomorfismer, som backtracking , begränsningspropagering och lokal sökning , gäller alla CSP: er.

För graferna G och H motsvarar frågan om G har en homomorfism till H en CSP-instans med endast en typ av begränsning enligt följande. De variabler är det hörn av G och domänen för varje variabel är vertex uppsättning av H . En utvärdering är en funktion som tilldelar varje variabel ett element i domänen, så en funktion f från V ( G ) till V ( H ). Varje kant eller båge ( u , v ) på G motsvarar då begränsningen (( u , v ), E ( H )). Detta är en begränsning som uttrycker att utvärderingen bör kart bågen ( u , v ) till ett par ( f ( u ), f ( v )), som är i relationen E ( H ), dvs till en båge av H . En lösning på CSP är en utvärdering som respekterar alla begränsningar, det är så exakt en homomorfism från G till H .

Struktur av homomorfismer

Sammansättningar av homomorfismer är homomorfismer. I synnerhet är förhållandet → på grafer övergående (och reflexivt, triviellt), så det är en förbeställning på grafer. Låt ekvivalensklassen för ett diagram G under homomorf ekvivalens vara [ G ]. Likvärdighetsklassen kan också representeras av den unika kärnan i [ G ]. Relationen → är en delordning på dessa ekvivalensklasser; det definierar en poset .

Låt G < H betecknar att det finns en homomorfism från G till H , men ingen homomorfism från H till G . Relationen → är en tät ordning , vilket betyder att för alla (icke-riktade) grafer G , H så att G < H , finns det en graf K så att G < K < H (detta gäller förutom triviala fall G = K 0 eller K 1 ). Till exempel, mellan två kompletta grafer (förutom K 0 , K 1 ) finns det oändligt många cirkulära kompletta grafer , motsvarande rationella tal mellan naturliga tal.

Motsättningen av ekvivalensklasser av grafer under homomorfismer är ett distribuerande gitter , med sammanfogningen av [ G ] och [ H ] definierad som (ekvivalensklassen för) den ojämna föreningen [ G ∪ H ] och mötet mellan [ G ] och [ H ] definierad som tensorprodukten [ G × H ] (valet av graferna G och H som representerar ekvivalensklasserna [ G ] och [ H ] spelar ingen roll). De föreningsreducerbara elementen i detta galler är exakt anslutna grafer. Detta kan visas med hjälp av det faktum att en homomorfism kartlägger en ansluten graf i en ansluten komponent i målgrafen. De mötesreducerbara elementen i detta galler är exakt multiplikationsdiagrammen . Dessa är graferna K så att en produkt G × H endast har en homomorfism till K när en av G eller H också gör det. Att identifiera multiplikativa diagram ligger i hjärtat av Hedetniemis antaganden .

Grafhomomorfier bildar också en kategori med grafer som objekt och homomorfismer som pilar. Det ursprungliga objektet är det tomma diagrammet, medan terminalobjektet är diagrammet med ett toppunkt och en slinga vid det toppunktet. Den tensorprodukt av grafer är kategori-teoretisk produkt och exponentiell kurva är den exponentiella föremålet för denna kategori. Eftersom dessa två operationer alltid definieras är kategorin av grafer en kartesisk sluten kategori . Av samma anledning är gitteret av ekvivalensklasser av grafer under homomorfism i själva verket en Heyting-algebra .

För riktade grafer gäller samma definitioner. I synnerhet → är en partiell ordning på ekvivalensklasser av riktade grafer. Det skiljer sig från ordningen → på ekvivalensklasser av oriktade grafer, men innehåller det som en underordning. Detta beror på att varje icke riktad graf kan ses som en riktad graf där varje båge ( u , v ) visas tillsammans med sin inversa båge ( v , u ), och detta ändrar inte definitionen av homomorfism. Ordern → för riktade grafer är återigen ett distribuerande gitter och en Heyting-algebra, med kopplings- och mötesoperationer definierade som tidigare. Det är dock inte tätt. Det finns också en kategori med riktade grafer som objekt och homomorfier som pilar, vilket återigen är en kartesisk sluten kategori .

Ojämförliga diagram

Grötzsch-grafen, ojämförlig med K 3

Det finns många ojämförliga grafer med avseende på förbeställningen av homomorfism, det vill säga par av diagram som varken medger en homomorfism i den andra. Ett sätt att konstruera dem är att beakta den udda omkretsen av en graf G , längden på dess kortaste udda längdcykel. Den udda omkrets är, ekvivalent, den minsta udda antal g för vilken det finns en homomorfism från cyklisk graf på g vertex till G . Av detta skäl, om G → H , då den udda omkrets på G är större än eller lika med den udda omkrets av H .

Å andra sidan, om G → H , då den kromatiska antalet G är mindre än eller lika med den kromatiska antalet H . Därför, om G har strikt större udda omkrets än H och strikt större kromatiska tal än H , då är G och H ojämförliga. Till exempel är Grötzsch-grafen 4-kromatisk och triangelfri (den har omkrets 4 och udda omkrets 5), så den är ojämförlig med triangelgrafen K 3 .

Exempel på grafer med godtyckligt stora värden på udda omkrets och kromatiska antal är Kneser-grafer och generaliserade Mycielskians . En sekvens av sådana grafer, med samtidigt ökande värden för båda parametrarna, ger oändligt många ojämförliga diagram (en antikedja i homomorfismförbeställningen). Andra egenskaper, såsom densiteten hos homomorfismförbeställningen, kan bevisas med sådana familjer. Konstruktioner av grafer med stora värden för kromatiskt antal och omkrets, inte bara udda omkrets, är också möjliga, men mer komplicerade (se omkrets och graffärgning ).

Bland riktade grafer är det mycket lättare att hitta ojämförliga par. Tänk till exempel på de riktade cykeldiagrammen C → n , med hörn 1, 2, ..., n och kanter från i till i + 1 (för i = 1, 2,…, n - 1) och från n till 1. Där är en homomorfism från C → n till C → k ( n , k ≥ 3) om och endast om n är en multipel av k . I synnerhet är riktade cykeldiagram C → n med n prime alla ojämförliga.

Beräkningskomplexitet

I grafhomomorfi problemet, är en förekomst av ett par grafer ( G , H ) och en lösning är en homomorfism från G till H . Det allmänna beslutsproblemet , att fråga om det finns någon lösning, är NP-komplett . Att begränsa tillåtna fall ger dock upphov till en mängd olika problem, varav några är mycket lättare att lösa. Metoder som gäller vid begränsning av vänster sida G är mycket annorlunda än för höger sida H , men i varje fall är en dikotomi (en skarp gräns mellan enkla och svåra fall) känd eller tänkt.

Homomorfismer till en fast graf

Homomorfismproblemet med ett fast diagram H på höger sida av varje instans kallas också H- färgproblemet. När H är den kompletta grafen K k , är detta den graf k -coloring problem , som är lösbar i polynomisk tid för k = 0, 1, 2, och NP-komplett annars. I synnerhet, K 2 -colorability av en graf G är ekvivalent med G varelse tvådelad , som kan testas i linjär tid. Mer generellt, när H är en tvådelad graf, H är -colorability ekvivalent med K 2 -colorability (eller K 0 / K 1 -colorability när H är tom / kantlösa), därav lika lätt att avgöra. Pavol Hell och Jaroslav Nešetřil bevisade att för oriktade grafer, inget annat fall är förenligt:

Hell-Nešetřil-satsen (1990): H- färgproblemet finns i P när H är tvåparts och NP-komplett annars.

Detta är också känt som dikotomi-satsen för (icke-riktade) grafhomomorfismer, eftersom den delar upp H- färgproblem i NP-kompletta eller P-problem, utan mellanliggande fall. För riktade diagram är situationen mer komplicerad och i själva verket likvärdig med den mycket mer allmänna frågan om att karakterisera komplexiteten hos problem med begränsningstillfredsställelse . Det visar sig att H- färgproblem för riktade grafer är lika allmänna och lika olika som CSP med alla andra begränsningar. Formellt är ett (ändligt) begränsningsspråk (eller mall ) Γ en ändlig domän och en begränsad uppsättning relationer över denna domän. CSP ( Γ ) är problemet med begränsningstillfredsställelse där instanser endast får använda begränsningar i Γ .

Theorem (Feder, Vardi 1998): För varje begränsning språk Γ , problemet CSP ( Γ är) likvärdiga enligt minskningar polynom-time i viss H -coloring problem, för en del riktad graf H .

Intuitivt betyder detta att varje algoritmisk teknik eller komplexitetsresultat som gäller H- färgproblem för riktade grafer H gäller lika bra för allmänna CSP. I synnerhet kan man fråga om Hell-Nešetřil-satsen kan utvidgas till riktade grafer. Enligt ovanstående sats motsvarar detta Feder-Vardi-antagandet (aka CSP-antagande, dikotomi-antagande) om CSP-dikotomi, som säger att för varje begränsningsspråk Γ är CSP ( Γ ) NP-komplett eller i P. Denna antagande var bevisades 2017 oberoende av Dmitry Zhuk och Andrei Bulatov, vilket ledde till följande resultat:

Resultat (Bulatov 2017; Zhuk 2017): H- färgproblemet på riktade grafer, för en fast H , är antingen i P eller NP-komplett.

Homomorfismer från en fast familj av grafer

Homomorfismproblemet med en enda fast graf G på vänster sida av ingångsinstanser kan lösas med brute-force i tid | V ( H ) | O (| V ( G ) |) , så polynom i storleken på den ingående grafen H . Med andra ord är problemet trivialt i P för diagram G med begränsad storlek. Den intressanta frågan är då vilka andra egenskaper hos G , förutom storlek, som gör polynomalgoritmer möjliga.

Den avgörande egenskapen visar sig vara trebredd , ett mått på hur trädliknande grafen är. För ett diagram G med högst trebredd k och ett diagram H kan homomorfismproblemet lösas i tid | V ( H ) | O ( k ) med en standard dynamisk programmeringsmetod . I själva verket är det tillräckligt att anta att kärnan i G har högst tre bredd k . Detta gäller även om kärnan inte är känd.

Exponenten i | V ( H ) | O ( k ) -tidsalgoritmen kan inte sänkas markant: ingen algoritm med körtid | V ( H ) | o (tw ( G ) / log tw ( G )) existerar, förutsatt att den exponentiella tidshypotesen (ETH), även om ingångarna är begränsade till någon klass av grafer med obegränsad trebredd. ETH är ett obevisat antagande som liknar P ≠ NP , men starkare. Under samma antagande finns det i huvudsak inga andra egenskaper som kan användas för att få polynomiska tidsalgoritmer. Detta formaliseras enligt följande:

Sats ( Grohe ): För en beräknbar klass av grafer är homomorfismproblemet i fall med P om och endast om grafer i har kärnor med avgränsad trebredd (förutsatt att ETH).

Man kan fråga sig om problemet är minst lösbar i en tid godtyckligt mycket beroende av G , men med en fast polynom beroende på storleken på H . Svaret är återigen positivt om vi begränsar G till en klass av grafer med kärnor med avgränsad träbredd och negativ för varje annan klass. På språket för parametrerad komplexitet anges detta formellt att homomorfismproblemet som parametrerats av storleken (antalet kanter) av G uppvisar en dikotomi. Det kan fastställas med parametrar om grafer i har kärnor med avgränsad trebredd och W [1] -kompletterar annars.

Samma uttalanden gäller mer allmänt för problem med tillfredsställelse av tillfredsställelse (eller för relationsstrukturer, med andra ord). Det enda antagandet som behövs är att begränsningar endast kan innefatta ett begränsat antal variabler (alla relationer har en viss avgränsad aritet, 2 i fallet med grafer). Den relevanta parametern är då trebredden för den primära begränsningsdiagrammet .

Se även

Anteckningar

Referenser

Allmänna böcker och utställningar

I begränsad tillfredsställelse och universell algebra

Inom gitterteori och kategoriteori