Olänkad grafinbäddning

En olänkad grafinbäddning  är en inbäddning av en oriktad graf i det euklidiska rummet så att inga två cykler av grafen har en länkkoefficient som inte är noll . En platt inbäddning  är en inbäddning där vilken cykel som helst är gränsen för en topologisk cirkel vars inre inte är kopplat till grafen. En inbäddningsbar graf utan länkar  är en graf som har en olänkad eller platt inbäddning. Dessa grafer bildar en tredimensionell analog av plana grafer [1] . Däremot är en väsentligen länkad graf  en som inte har någon olänkad inbäddning.

Platta inbäddningar har automatiskt inga länkar, men inte vice versa [2] . Den fullständiga grafen , Petersen-grafen och de andra fem graferna från Petersen-familjen av grafer har inte olänkade inbäddningar [1] . Olänkade inbäddningsgrafer stängs av grafiska mindreer [3] och Y-Δ-transformationer [2] . Dessa grafer har Petersen-familjens grafer som förbjudna minderåriga [4] och inkluderar plana grafer och vertexgrafer [2] . Grafer kan kännas igen (och en platt inbäddning kan byggas) i linjär tid [5] .

Definitioner

Två icke-korsande kurvor i det euklidiska rummet sägs vara okopplade om det finns en kontinuerlig rörelse av kurvorna som omvandlar dem till två icke-korsande koplanära cirklar utan att en kurva går genom den andra eller genom sig själv. Om det inte finns någon sådan kontinuerlig rörelse, sägs kurvorna vara länkade . Hopf-länken som bildas av två cirklar som passerar genom en skiva som sträcks av dessa cirklar ger det enklaste exemplet på ett par länkade kurvor, men kurvorna kan länkas på mycket mer komplexa sätt. Om kurvorna inte är länkade kan man hitta en (topologisk) skiva i rymden som begränsas av den första kurvan och inte skär den andra. Omvänt, om en sådan skiva finns, är kurvorna inte länkade.

Länkningskoefficienten för två stängda kurvor i tredimensionellt rymden är en topologisk invariant av kurvan - detta är ett tal definierat för kurvor på ett av de ekvivalenta sätten, som inte ändras om kurvorna flyttas i rymden kontinuerligt utan att korsa varandra eller sig själva. Ingreppskoefficienten hittas genom att projicera en inbäddning på ett plan och på ett visst sätt räkna antalet passager av den första kurvan över den andra (med +1 eller −1 tecken beroende på passageriktningen). Projektionen måste vara "korrekt", vilket innebär att inga två hörn projiceras till samma punkt, ingen hörn projiceras inuti en kant, och vid någon punkt i projektionen där kanterna skär varandra, skär de tvärs . Under sådana restriktioner leder varje projektion till samma länkkoefficient. Länkningskoefficienten för olänkade kurvor är noll, och därför, om ett par kurvor har en länkkoefficient som inte är noll, måste de två kurvorna länkas. Det finns dock exempel på länkade kurvor som har en länkningsfaktor på noll, som Whitehead-länken .

Inbäddningen av en graf i det tredimensionella rummet består av att kartlägga grafens hörn till punkter i rymden och avbildningar av kanter till kurvor, så att varje ändpunkt av en kant avbildas till en ändpunkt för motsvarande kurva och kurvorna som motsvarar två olika kanter skär sig inte (förutom vid gemensamma ändpunkter). Vilken finit graf som helst har ett ändligt (möjligen exponentiellt) antal olika enkla cykler , och om grafen är inbäddad i tredimensionellt utrymme bildar varje sådan cykel en enkel sluten kurva. Det är möjligt att beräkna länkkoefficienten för varje icke-korsande par av kurvor som bildas på detta sätt. Om alla par av cykler har noll länkkoefficient, sägs inbäddningen vara olänkad [6] [1] [2] .

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 som avgränsas av denna cykel som inte skär andra element i grafen. I det här fallet får cykeln inte kopplas till andra cykler i grafen som inte skär den. En inbäddning sägs vara platt om någon cykel begränsar skivan på det beskrivna sättet [2] . På liknande sätt ges en definition av "bra investering" i Motwani, Raghunathan, Saran, 1988 . Se även Saran (1989 ) och Böhme (1990 ). En platt inbäddning är nödvändigtvis olänkad, men det kan finnas olänkade inbäddningar som inte är platt. Till exempel, om G är en graf som bildas av två separata cykler och inbäddningen resulterar i en Whitehead-länk, är inbäddningen olänkad men inte plan.

En graf sägs vara väsentligen länkad om någon inbäddning resulterar i en alltid länkad inbäddning. Även om olänkade och platta inbäddningar inte är samma, visar sig grafer med olänkade inbäddningar vara samma grafer som grafer med platta inbäddningar [7] .

Exempel och motexempel

Som Sacks [1] visade , är alla sju graferna i en Petersen-familj väsentligen länkade, och det spelar ingen roll hur dessa grafer är inbäddade i rymden, för varje inbäddning har de två länkade cykler. Dessa grafer inkluderar den fullständiga grafen , Petersen -grafen, grafen som bildas genom att ta bort en kant från en komplett tvådelad graf och den fullständiga tredelade grafen .

Alla plana grafer har en platt och olänkad inbäddning - bara bädda in grafen i ett plan placerat i (tredimensionellt) rymden. Om grafen är plan är detta det enda sättet att bädda in grafen platt och olänkad – vilken platt inbäddning som helst kan kontinuerligt deformeras till en inbäddning i planet. Omvänt har alla icke-planära olänkade grafer flera olänkade inbäddningar [2] .

Hönsgrafen , som bildas genom att lägga till en vertex till den plana grafen, har också en platt och icke-kedjad inbäddning - vi bäddar in den plana delen av grafen på planet, placerar grafens vertex (den vertex som bryter mot planariteten) ovanför planet, och rita sedan kanter från vertex till intilliggande hörn i form av segment. Varje stängd kurva på planet begränsar en skiva som inte passerar genom ett annat element i grafen, och varje stängd kurva genom spetsen begränsar en skiva ovanför planet som inte passerar genom något annat element i grafen [2] .

Om grafen har en olänkad eller platt inbäddning, modifiera grafen genom att dela eller slå samman dess kanter, lägga till eller ta bort flera kanter mellan ett par hörn, eller utföra Y-Δ-transformationer , där en vertex av grad tre ersätts med en triangel som förbinder tre grannar, eller vice versa, leder till bevarandet av existensen av en platt eller obunden inbäddning [2] . I synnerhet, i en kubisk plan graf (där alla hörn har exakt tre grannar, som en kub), kan man göra kopior av vilken oberoende uppsättning hörn som helst genom att utföra en Y-Δ-transformation, lägga till flera kopior av kanterna i den resulterande trianglar och gör sedan de inversa Δ -Y-transformerna.

Karakterisering och igenkänning

Om en graf har en olänkad eller platt inbäddning, har alla grafer mindre (grafen som bildas genom att kanter dras samman och tar bort kanter och hörn) också en olänkad eller platt inbäddning. Borttagning kan inte bryta möjligheten till olänkade eller platt kapsling, och sammandragning kan göras genom att lämna en ändpunkt av kanten på plats och byta alla kanter som faller in mot den motsatta vertexen. Genom Robertson-Seymour-satsen kännetecknas alltså grafer som har en olänkad inbäddning av förbjudna grafer som grafer som inte innehåller någon av en ändlig uppsättning av molor [3] .

Uppsättningen av förbjudna minderåriga för grafer som tillåter olänkade inbäddningar upptäcktes av Sacks [1] — sju  grafer av Petersen-familjen är mindre grafer som är väsentligen länkade. Sachs kunde dock inte bevisa att endast dessa grafer är minor-minimal länkade grafer, och detta gjordes av Robertson, Seymour och Thomas [4] .

Karakteriseringen av förbjudna minderåriga av grafer som tillåter olänkad inbäddning leder till en algoritm med polynom körtid för deras igenkänning, men denna algoritm konstruerar inte en riktig inbäddning. Karavabaishi, Kreutzer och Mohar [5] beskrev en linjär-tidsalgoritm som kontrollerar om en graf är inbäddningsbar utan en länk och, om den går att bädda in, konstruerar en platt inbäddning av grafen. Deras algoritm hittar stora plana subgrafer inom en given graf så att, om det finns en olänkad inbäddning, representerar de en plan inbäddning av subgrafen. Genom att omförenkla grafen när en sådan subgraf hittas, reducerar de problemet till ett där den återstående grafen begränsas av trädets bredd , då problemet kan lösas med dynamisk programmering .

Problemet med att effektivt kontrollera huruvida en given inbäddning är platt eller okopplad framställdes av Robertson, Seymour och Thomas [2] . Problemet förblir olöst och är likvärdigt i komplexitet med knutupplösningsproblemet , problemet med att kontrollera om en kurva i rymden är oknuten [5] . Det är känt att kontrollen för oknötning (och därmed även för obunden häckning) tillhör NP -klassen , men det är inte känt om den tillhör klassen av NP-kompletta problem [8] .

Besläktade familjer av grafer

Colin de Verdière-invarianten  är ett tal som definieras för vilken graf som helst baserat på algebraisk grafteori . En graf med en Colin de Verdière invariant som inte överstiger μ för någon fast konstant μ bildar en mindre sluten familj, och de första få sådana familjerna är välkända — grafer med μ ≤ 1 är linjära skogar (en osammanhängande förening av stigar), grafer med μ ≤ 2 är ytterplanära grafer och grafer med μ ≤ 3 är plana grafer . Som föreslagits av Robertson, Seymour och Thomas [2] och bevisat av Lowash och Schreiver [9] är grafer med μ ≤ 4 exakt grafer med olänkade inbäddningar.

Plana grafer och vertexgrafer tillåter olänkad inbäddning, liksom grafer som erhålls genom Y-Δ-transformationer från dem [2] . YΔY-reducerbara grafer  är grafer som kan reduceras till en enda vertex genom en Y-Δ-transformation, ta bort isolerade hörn och hängande hörn (topp i grad 1) och ersätta bågar vid en vertex med grad två med en enda båge. Dessa grafer är också stängda i mindre. Det finns emellertid icke-länkade YΔY-irreducerbara grafer, såsom vertexgrafen som bildas genom att koppla en vertex (en planaritetsbrytande vertex) till alla hörn av grad tre i en rombisk dodekaeder [10] . Det finns också olänkade grafer som inte kan transformeras genom Y-Δ-transformationer, ta bort isolerade och hängande hörn och ersätta bågar vid en vertex med grad två med en båge till en vertexgraf. Till exempel har en krona med tio hörn en olänkad inbäddning, men kan inte konverteras till en vertexgraf på det sätt som beskrivs ovan [2] .

Relaterat till begreppet en olänkad inbäddning är begreppet en okunnad inbäddning. Det är en sådan grafinbäddning att ingen enkel cykel bildar en icke-trivial knut . De grafer som inte har en oknuten inbäddning inkluderar K 7 och K 3,3,1,1 [6] [11] . Det finns dock minimala förbjudna minderåriga för oknutna inbäddningar som inte bildas (till skillnad från ovanstående två grafer) genom att lägga till en vertex till en väsentligen länkad graf [12] .

Man kan definiera graffamiljer genom närvaron eller frånvaron av mer komplexa knutar och länkar i deras inbäddning [3] [13] , eller genom en olänkad inbäddning i ett tredimensionellt mångfald annat än det euklidiska rummet [14] . Flapan, Naimi och Pommersheim [15] definierade en inbäddning av en graf som trippellänkad om det finns tre cykler, av vilka ingen kan separeras från de andra två. De visade att K 9 inte är väsentligen tre gånger länkad, medan K 10 är länkad [16] . Mer generellt kan man definiera en n -länkad inbäddning för vilken som helst som en inbäddning som innehåller en -komponentlänk som inte kan delas av en topologisk sfär i två separata delar. Minor-minimal essentiellt länkade grafer är kända för alla [17] .

Historik

Frågan om en inbäddning har en länk eller ett plan togs upp i det topologiska forskarsamhället i början av 1970-talet av Bothe [18] . Olänkad inbäddning uppmärksammades av grafteoretiker Sacks [1] , som föreslog flera relaterade problem, inklusive problemet med att hitta en karakterisering av förbjudna grafer av grafer med olänkade eller platta inbäddningar. Sachs visade att sju grafer av familjen Petersen (inklusive ) inte har sådana inbäddningar. Som Nexetril och Thomas [3] noterade , är icke-länkade inbäddade grafer stängda i minorerna av grafen , vilket antyder, av Robertson-Seymour-satsen , att en karaktärisering av förbjudna grafer existerar. Beviset för existensen av ett ändligt antal obstruktiva grafer leder inte till en explicit beskrivning av denna uppsättning förbjudna minderåriga, men det följer av Sacks resultat att sju grafer av familjen Petersen tillhör uppsättningen. Dessa problem löstes slutligen av Robertson, Seymour och Thomas [4] [7] som visade att dessa sju grafer av familjen Petersen är de enda minimala förbjudna minderåriga för sådana grafer. Olänkade inbäddningsbara grafer och plana inbäddningsbara grafer är alltså samma uppsättning grafer, och båda familjerna kan definieras som grafer som inte innehåller element från Petersen-familjen som underordnade.

Sacks [1] frågade också om gränser för antalet kanter och det kromatiska antalet inbäddningsbara grafer utan länk. Antalet kanter i en inbäddningsbar vertexgraf utan länk överstiger inte  — maximala vertexgrafer c har exakt detta antal kanter [1] , och Mader [19] bevisade den övre gränsen för en mer allmän klass av K 6 -fri graf minderåriga. 1985 visades det att Sachs fråga om det kromatiska talet skulle lösas om Hadwigers gissning bevisades att vilken kromatisk graf som helst har en komplett graf med hörn som moll [3] . Beviset från Robertson, Seymour och Thomas [20] för fallet med Hadwigers gissningar är tillräckligt för att lösa Sachs fråga - grafer utan länkar kan färgas med högst fem färger, eftersom vilken 6-kromatisk graf som helst innehåller en moll och inte är okopplad , och det finns olänkade grafer som , som kräver fem färger. Det följer av snark -satsen att alla kubiska inbäddningsbara grafer utan länk är 3-kantsfärgbara .

Studiet av länklösa inbäddningar började i studiet av algoritmer i slutet av 1980-talet [21] [22] . Algoritmiskt löstes problemet med att känna igen länklösa inbäddningsbara och platta inbäddningsbara grafer när karaktärisering av förbjudna minderåriga bevisades - algoritmen från Robertson och Seymour [23] kan användas för att kontrollera i polynomtid om en given graf innehåller någon av de sju förbjudna minderåriga [24] . Denna metod bygger inte en olänkad eller platt inbäddning om den finns, utan en algoritm som bygger en inbäddning [25] och senare hittade en mer effektiv algoritm som körs i linjär tid [5] .

Den sista frågan från Sachs [1] om möjligheten till en analogi av Fari-satsen för olänkade grafer har ännu inte besvarats. Frågan ställs som följer: när innebär förekomsten av en obunden eller platt inbäddning med böjda eller bitvis linjära kanter förekomsten av en obunden eller platt inbäddning där kanterna är segment ?

Anteckningar

  1. ↑ 1 2 3 4 5 6 7 8 9 Sachs, 1983 .
  2. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 Robertson, Seymour, Thomas, 1993a .
  3. ↑ 1 2 3 4 5 Nešetřil, Thomas, 1985 .
  4. ↑ 1 2 3 Robertson, Seymour, Thomas, 1995 .
  5. ↑ 1 2 3 4 Kawarabayashi, Kreutzer, Mohar, 2010 .
  6. ↑ 1 2 Conway, Gordon, 1983 .
  7. ↑ 12 Robertson, Seymour, Thomas, 1993b .
  8. ↑ Hass, Lagarias, Pippenger, 1999 .
  9. ↑ Lovász, Schrijver, 1998 .
  10. ↑ Truemper, 1992 .
  11. ↑ Foisy, 2002 .
  12. ↑ Foisy, 2003 .
  13. ↑ Fleming, Diesl, 2005 .
  14. ↑ Flapan, Howards, Lawrence, Mellor, 2006 .
  15. ↑ Flapan, Naimi, Pommersheim, 2001 .
  16. ↑ För andra exempel på icke-tre-länkade grafer, se Bowlin och Foisy 2004 .
  17. ↑ Flapan, Pommersheim, Foisy, Naimi, 2001 .
  18. ↑ Bothe, 1973 .
  19. ↑ Mader, 1968 .
  20. ↑ Robertson, Seymour, Thomas, 1993c .
  21. ↑ Fellows, Langston, 1988 .
  22. ↑ Motwani, Raghunathan, Saran, 1988 .
  23. ↑ Robertson, Seymour, 1995 .
  24. ↑ Tillämpligheten av Robertson-Seymour-algoritmen på detta problem uppmärksammades av Fellows och Langston ( Fellows, Langston, 1988 ).
  25. ↑ van der Holst, 2009 .

Litteratur