Länklös inbäddning

I topologisk grafteori , en matematisk disciplin, är en länklös inbäddning av en oriktad graf en inbäddning av grafen i tredimensionell euklidisk rymd på ett sådant sätt att inga två cykler av grafen är sammanlänkade. En platt inbäddning är en inbäddning med egenskapen att varje cykel är gränsen för en topologisk skiva vars inre är skild från grafen. En länklöst inbäddningsbar graf är en graf som har en länklös eller platt inbäddning; dessa grafer bildar en tredimensionell analog till de plana graferna . Kompletterande är en egenlänkad graf en graf som inte har en länkfri inbäddning.

Platta inbäddningar är automatiskt länkfria, men inte vice versa. Den kompletta grafen K 6 , Petersen -grafen och de andra fem graferna i Petersen-familjen har inte länklösa inbäddningar. Varje underordnad graf i en länklöst inbäddningsbar graf är återigen länklöst inbäddningsbar, liksom varje graf som kan nås från en länklöst inbäddningsbar graf med en Y-Δ-transform . De länklöst inbäddningsbara graferna har Petersen-familjens grafer som sina förbjudna mindreåriga , och inkluderar de plana graferna och apexgraferna . De kan kännas igen, och en platt inbäddning kan konstrueras för dem, i O ( n 2 ) .

Definitioner

Två länkade kurvor som bildar en Hopf-länk .

När cirkeln mappas till tredimensionell euklidisk rymd av en injektiv funktion (en kontinuerlig funktion som inte mappar två olika punkter i cirkeln till samma punkt i rymden), är dess bild en sluten kurva . Två disjunkta stängda kurvor som båda ligger på samma plan är olänkade , och mer generellt sägs ett par disjunkta slutna kurvor vara osammanhängande när det finns en kontinuerlig deformation av rymden som flyttar dem båda till samma plan, utan att någon av kurvorna går igenom den andra eller genom sig själv. Om det inte finns någon sådan kontinuerlig rörelse, sägs de två kurvorna vara sammanlänkade . Till exempel är Hopf-länken bildad av två cirklar som var och en passerar genom skivan som spänns av den andra. Det är det enklaste exemplet på ett par länkade kurvor, men det är möjligt för kurvor att länkas på andra mer komplicerade sätt. Om två kurvor inte är sammanlänkade, är det möjligt att hitta en topologisk skiva i rymden, med den första kurvan som sin gräns och disjunkt från den andra kurvan. Omvänt, om en sådan skiva existerar, är kurvorna nödvändigtvis olänkade.

Länkningstalet för två slutna kurvor i det tredimensionella rummet är en topologisk invariant av kurvorna: det är ett tal, definierat från kurvorna på något av flera ekvivalenta sätt, som inte ändras om kurvorna flyttas kontinuerligt utan att passera genom varje Övrig. Den version av länknumret som används för att definiera länklösa inbäddningar av grafer hittas genom att projicera inbäddningen på planet och räkna antalet korsningar av den projicerade inbäddningen där den första kurvan passerar över den andra, modulo 2. Projektionen måste vara "regelbundet", vilket betyder att inga två hörn skjuter ut till samma punkt, ingen hörn skjuter ut mot det inre av en kant, och vid varje punkt av projektionen där projektionerna av två kanter skär varandra, korsar de tvärs ; med denna begränsning leder vilka två projektioner som helst till samma länknummer. Länkningsnumret för bortkopplingen är noll, och därför, om ett par kurvor har ett länknummer som inte är noll, måste de två kurvorna länkas. Det finns dock exempel på kurvor som är länkade men som har noll länknummer, som Whitehead-länken .

En inbäddning av en graf i det tredimensionella rummet består av en mappning från grafens hörn till punkter i rymden och från grafens kanter till kurvor i rymden, så att varje ändpunkt av varje kant avbildas till en ändpunkt av motsvarande kurva, och så att kurvorna för två olika kanter inte skär varandra förutom vid en gemensam ändpunkt av kanterna. Vilken finit graf som helst har ett ändligt (men kanske exponentiellt) antal distinkta enkla cykler , och om grafen är inbäddad i tredimensionellt utrymme bildar var och en av dessa cykler en enkel sluten kurva. Man kan beräkna länknumret för varje disjunkt par av kurvor som bildas på detta sätt; om alla par av cykler har noll länknummer, sägs inbäddningen vara länkfri.

I vissa fall kan en graf vara inbäddad i rymden på ett sådant sätt att man för varje cykel i grafen kan hitta en skiva avgränsad av den cykeln som inte korsar någon annan egenskap i grafen. I detta fall måste cykeln kopplas bort från alla andra cykler som är åtskilda från den i grafen. Inbäddningen sägs vara platt om varje cykel avgränsar en skiva på detta sätt. En platt inbäddning är nödvändigtvis länkfri, men det kan finnas länklösa inbäddningar som inte är platt: till exempel, om G är en graf som bildas av två disjunkta cykler, och den är inbäddad för att bilda Whitehead-länken, då är inbäddningen länklös men inte platt .

En graf sägs vara inneboende länkad om, oavsett hur den är inbäddad, inbäddningen alltid är länkad. Även om länklösa och platta inbäddningar inte är samma, är graferna som har länklösa inbäddningar desamma som graferna som har platta inbäddningar.

Exempel och motexempel

Familjen Petersen .

Som Sachs (1983) visade är var och en av de sju graferna i Petersen-familjen inneboende sammanlänkade: oavsett hur var och en av dessa grafer är inbäddade i rymden, har de två cykler som är kopplade till varandra. Dessa grafer inkluderar den fullständiga grafen K 6 , Petersen - grafen , den graf som bildas genom att ta bort en kant från den fullständiga tvådelade grafen K 4,4 och den fullständiga tredelade grafen K 3,3,1 .

Varje plan graf har en platt och länkfri inbäddning: bädda helt enkelt in grafen i ett plan och bädda in planet i rymden. Om en graf är plan är detta det enda sättet att bädda in den plant och länklöst i rymden: varje platt inbäddning kan kontinuerligt deformeras för att ligga på ett plant plan. Och omvänt, alla icke-planära länklösa grafer har flera länklösa inbäddningar.

En apexgraf . Om den plana delen av grafen är inbäddad på ett platt plan i rymden, och spetsen är placerad ovanför planet och ansluten till den med raka linjesegment, blir den resulterande inbäddningen platt.

En apexgraf , som bildas genom att lägga till en enda vertex till en plan graf, har också en platt och länklös inbäddning: bädda in den plana delen av grafen på ett plan, placera spetsen ovanför planet och rita kanterna från spetsen till dess grannar som linjesegment. Varje stängd kurva inom planet avgränsar en skiva under planet som inte passerar genom någon annan graffunktion, och varje sluten kurva genom spetsen avgränsar en skiva ovanför planet som inte passerar genom någon annan graffunktion.

Om en graf har en länklös eller platt inbäddning, modifiera grafen genom att dela upp eller ta bort dess kanter, lägga till eller ta bort flera kanter mellan samma par av punkter och utföra Y-Δ-transformationer som ersätter en grad-tre vertex med en triangel som förbinder dess tre grannar eller den omvända bevarar alla planhet och länklöshet. I synnerhet i en kubisk plan graf (en där alla hörn har exakt tre grannar, såsom kuben) är det möjligt att göra dubbletter av vilken oberoende uppsättning hörn som helst genom att utföra Y-Δ-transformeringar, lägga till flera kopior av den resulterande triangeln kanter, och sedan utföra de omvända Δ-Y-transformerna.

Karakterisering och igenkänning

Om en graf G har en länklös eller platt inbäddning, så har varje mindre av G (en graf som bildas genom sammandragning av kanter och radering av kanter och hörn) också en länklös eller platt inbäddning. Borttagningar kan inte förstöra planheten hos en inbäddning, och en sammandragning kan utföras genom att lämna en ändpunkt av den sammandragna kanten på plats och omdirigera alla kanter som faller in i den andra ändpunkten längs banan för den sammandragna kanten. Därför, enligt Robertson-Seymour-satsen , har de länklöst inbäddningsbara graferna en förbjuden grafkarakterisering som de grafer som inte innehåller någon av en ändlig uppsättning av mindretal.

Uppsättningen av förbjudna minderåriga för de länklöst inbäddningsbara graferna identifierades av Sachs (1983) : de sju graferna för Petersen-familjen är alla små och minimala grafer som är inneboende länkade. Sachs kunde dock inte bevisa att dessa var de enda minimala länkade graferna, och detta åstadkoms till slut av Robertson, Seymour & Thomas (1995) .

Den förbjudna mindre karaktäriseringen av länklösa grafer leder till en polynomisk tidsalgoritm för deras igenkänning, men inte för att faktiskt konstruera en inbäddning. Kawarabayashi, Kreutzer & Mohar (2010) beskrev en linjär tidsalgoritm som testar om en graf är länklöst inbäddningsbar och i så fall konstruerar en platt inbäddning av grafen. Deras algoritm hittar stora plana subgrafer inom den givna grafen så att, om en länklös inbäddning finns, måste den respektera subgrafens plana inbäddning. Genom att upprepade gånger förenkla grafen närhelst en sådan subgraf hittas, reducerar de problemet till ett problem där den återstående grafen har avgränsat trädbredden , vid vilken punkt det kan lösas genom dynamisk programmering .

Problemet med att effektivt testa om en given inbäddning är platt eller länklös ställdes av Robertson, Seymour & Thomas (1993a) . Det förblir olöst, och är likvärdigt i komplexitet med unknotting problem , problemet med att testa om en enda kurva i rymden är oknutad. Att testa oknoddhet (och därför även testa länklöshet hos en inbäddning) är känt för att vara i NP men är inte känt för att vara NP-komplett .

Besläktade familjer av grafer

Colin de Verdières grafinvariant är ett heltal som definieras för vilken graf som helst som använder algebraisk grafteori . Graferna med Colin de Verdière-grafen invariant högst μ, för varje fast konstant μ, bildar en mindre sluten familj, och de första av dessa är välkända: graferna med μ ≤ 1 är de linjära skogarna (osammanhängande föreningar av vägar), graferna med μ ≤ 2 är de yttre plana graferna , och graferna med μ ≤ 3 är de plana graferna . Som Robertson, Seymour & Thomas (1993a) gissade och Lovász & Schrijver (1998) bevisade, är graferna med μ ≤ 4 exakt de länklöst inbäddningsbara graferna.

En länkfri apexgraf som inte är YΔY-reducerbar.

De plana graferna och apexgraferna är länklöst inbäddade, liksom graferna som erhålls av Y-A-transformeringar från dessa grafer. YΔY -reducerbara grafer är de grafer som kan reduceras till en enda vertex genom Y-Δ-transformationer, avlägsnande av isolerade hörn och grad-1-hörn, och komprimering av grad-två hörn; de är också mindre stängda och inkluderar alla plana grafer. Det finns dock länklösa grafer som inte är YΔY-reducerbara, till exempel apexgrafen som bildas genom att ansluta en apex vertex till varje grad-tre vertex av en rombisk dodekaeder . Det finns också länklösa grafer som inte kan omvandlas till en apex-graf med Y-Δ-transformationer, avlägsnande av isolerade hörn och grad-1-hörn, och komprimering av grad-två-hörn: till exempel har krongrafen med tio vertex en länkfri inbäddning , men kan inte omvandlas till en apexgraf på detta sätt.

Relaterat till konceptet länklös inbäddning är konceptet knutlös inbäddning , en inbäddning av en graf på ett sådant sätt att ingen av dess enkla cykler bildar en icke-trivial knut . De grafer som inte har knutfria inbäddningar (det vill säga de är knutna i sig ) inkluderar K 7 och K 3,3,1,1 . Men det finns också minimala förbjudna minderåriga för knutlös inbäddning som inte bildas (som dessa två grafer är) genom att lägga till en vertex till en iboende länkad graf.

Man kan också definiera graffamiljer genom närvaron eller frånvaron av mer komplexa knutar och länkar i deras inbäddningar, eller genom länklös inbäddning i andra tredimensionella grenrör än det euklidiska rummet. Flapan, Naimi & Pommersheim (2001) definierar en grafinbäddning att vara trippellänkad om det finns tre cykler av vilka ingen kan separeras från de andra två; de visar att K 9 inte är trefaldigt länkad, men K 10 är det. Mer generellt kan man definiera en n -länkad inbäddning för varje n som en inbäddning som innehåller en n -komponentlänk som inte kan separeras av en topologisk sfär i två separerade delar; mindre-minimala grafer som i sig är n -länkade är kända för alla n .

Historia

Frågan om K 6 har en länklös eller platt inbäddning ställdes inom topologiforskningssamhället i början av 1970-talet av Bothe (1973) . Länklösa inbäddningar uppmärksammades av grafteorigemenskapen av Horst Sachs ( 1983 ), som ställde upp flera relaterade problem inklusive problemet med att hitta en förbjuden grafkarakterisering av graferna med länklösa och platta inbäddningar; Sachs visade att de sju graferna för familjen Petersen (inklusive K 6 ) inte har sådana inbäddningar. Som Nešetřil & Thomas (1985) observerade, stängs länklöst inbäddningsbara grafer under graph minors , av vilket det följer av Robertson-Seymour-satsen att en förbjuden grafkarakterisering existerar. Beviset för existensen av en ändlig uppsättning obstruktionsgrafer leder inte till en explicit beskrivning av denna uppsättning förbjudna minderåriga, men det följer av Sachs resultat att de sju graferna för familjen Petersen tillhör uppsättningen. Dessa problem löstes slutligen av Robertson, Seymour & Thomas (1995), som visade att de sju graferna för familjen Petersen är de enda minimala förbjudna minderåriga för dessa grafer. Därför är länklöst inbäddningsbara grafer och platta inbäddningsbara grafer båda samma uppsättning grafer, och båda är samma som de grafer som inte har någon Petersen-familj minor.

Sachs (1983) bad också om gränser för antalet kanter och det kromatiska antalet länklösa inbäddningsbara grafer. Antalet kanter i en n -vertex länkfri graf är högst 4 n − 10: maximala apex-grafer med n > 4 har exakt så många kanter, och Mader (1968) visade en matchande övre gräns för den mer allmänna klassen av K 6 - mindre fria grafer. Nešetřil & Thomas (1985) observerade att Sachs fråga om det kromatiska talet skulle lösas genom ett bevis på Hadwigers gissning att vilken k -kromatisk graf som helst har en komplett graf med k -vertex. Beviset av Robertson, Seymour & Thomas (1993c) för fallet k = 6 i Hadwigers gissning är tillräckligt för att avgöra Sachs fråga: de länklösa graferna kan färgas med högst fem färger, eftersom vilken 6-kromatisk graf som helst innehåller en K 6 mindre och är inte länkfri, och det finns länklösa grafer som K 5 som kräver fem färger. Snark -satsen antyder att varje kubisk , länklöst inbäddningsbar graf är 3-kant-färgbar .

Länklösa inbäddningar började studeras inom algoritmforskningssamhället i slutet av 1980-talet genom verk av Fellows & Langston (1988) och Motwani, Raghunathan & Saran (1988) . Algoritmiskt löstes problemet med att känna igen länklösa och platta inbäddningsbara grafer när den förbjudna mindre karaktäriseringen bevisades: en algoritm av Robertson & Seymour (1995) kan användas för att testa i polynomtid om en given graf innehåller någon av de sju förbjudna minorerna. Denna metod konstruerar inte länklösa eller platta inbäddningar när de finns, men en algoritm som gör en inbäddning utvecklades av van der Holst (2009), och en mer effektiv linjär tidsalgoritm hittades av Kawarabayashi, Kreutzer & Mohar (2010) .

En sista fråga från Sachs (1983) om möjligheten av en analog till Fárys teorem för länklösa grafer verkar inte ha besvarats: när innebär förekomsten av en länklös eller platt inbäddning med böjda eller bitvis linjära kanter existensen av en länklös eller platt inbäddning där kanterna är raka linjesegment ?

Se även

Anteckningar

Vidare läsning

Hämtad från " https://en.wikipedia.org/w/index.php?title=Linkless_embedding&oldid=1097041619 "