Räkna mindre

En minor i grafteori  är en graf för en given graf , som kan bildas genom att ta bort kanter och hörn och dra ihop sig kanter .

Teorin om graph minors började med Wagners sats , som säger att en graf är plan om och endast om dess bipartier inte tillhör antingen den fullständiga grafen K 5 eller den fullständiga tvådelade grafen K 3,3 [1] [2] . Det följer av Robertson-Seymour- satsen att analoger till den förbjudna mindre karaktäriseringen finns för alla egenskaper hos grafer som bevaras under kantborttagning och sammandragning [3] [4] .

För vilken graf H som helst kan man kontrollera om H är en moll av ingångsgrafen G i polynomtid [5] . Tillsammans med karaktäriseringen av förbjudna minderåriga, följer det att vilken grafegenskap som helst som är bevarad under raderingar och sammandragningar kan kännas igen i polynomtid [6] .

Bland andra resultat och gissningar som använder grafmolor är grafstruktursatsen , enligt vilken grafer som inte innehåller H som moll kan bildas genom att limma ihop enklare delar, och Hadwiger-förmodan , som relaterar omöjligheten av graffärgning till existensen av en stor komplett graf som hans underordnade. Viktiga varianter av graph minderåriga är topologiska minderåriga och nedsänkta minderåriga.

Definitioner

Kantkontraktion är en operation som tar bort en kant från en graf och slår samman kantens ändar till en enda vertex. En oriktad graf H är en moll av en annan oriktad graf G om en graf som är isomorf till H kan erhållas från G genom att dra ihop kanter, ta bort några kanter och ta bort några isolerade hörn. Ordningen i vilken sammandragningar och raderingar görs i G påverkar inte den resulterande grafen H .

Graph minderåriga studeras ofta i det mer allmänna sammanhanget av matroid minderåriga . I detta sammanhang antas det vanligtvis att grafer är sammankopplade, kan ha slingor och flera kanter (dvs. multigrafer anses vara , inte enkla grafer). Det är förbjudet att dra i öglan och ta bort skäreggen . Med detta tillvägagångssätt lämnar borttagning av en kant grafens rangordning oförändrad, medan en sammandragning av en kant alltid minskar rangordningen med en.

I andra sammanhang (som i studien av pseudoskogar , till exempel ), är det vettigt att tillåta skärkanter att tas bort och tillåta att grafer kopplas bort, men det är också vettigt att inte tillåta multigrafer. I den här versionen av teorin om graph minors förenklas grafen alltid efter eventuell kantkontraktion för att eliminera slingor och flera kanter [7]

Exempel

I följande exempel är graf H en moll av graf G :

H.

G.

Följande figur illustrerar detta. Först konstruerar vi en subgraf av G genom att ta bort de streckade kanterna (och den resulterande isolerade vertexen) och sedan dra ihop den grå kanten (genom att förena de två hörnen som kanten förbinder):

Huvudresultat och gissningar

Det kan lätt verifieras att förhållandet mellan grafer bildar en partiell ordning på isomorfismklassen av oriktade grafer - relationen är transitiv (mollgraden i en graf G är själv en moll av G ) och graferna G och H kan vara varandras minderåriga om de är isomorfa, eftersom varje icke-trivial operation med en mindre tar bort kanter eller hörn. Ett djupt resultat av Neil Robertson och Paul Seymour säger att denna partiella ordning i själva verket är en helt kvasi-ordnad  — givet en oändlig lista G 1 , G 2 ,... av finita grafer, finns det alltid två index i < j , så att Gi är en moll av grafen G j . En likvärdig formulering av påståendet är att vilken uppsättning grafer som helst kan ha endast ett ändligt antal minimala element genom en mindre relation [8] . Detta resultat bevisar den gissning som hittills känts som Wagner-förmodan. Wagner gissade mycket tidigare, men publicerade det först 1970 [9] .

Under bevisets gång bevisade Seymour och Robertson också grafstruktursatsen , där de bestämde, för varje fast graf H , den grova strukturen för varje graf som inte innehåller H som en moll. Utsagan av satsen är lång och krystad, men i korthet säger satsen att en sådan graf måste ha strukturen av en summa över klick av mindre grafer, som erhålls genom en liten modifiering av grafer inbäddade i ytor av avgränsat släkte . Sålunda etablerar deras teori ett grundläggande samband mellan grafer och topologiska inbäddningar av grafer [10] [11] .

För varje graf H , måste enkla H-moll-fria grafer vara glesa , vilket betyder att antalet kanter är mindre än någon konstant gånger antalet hörn [12] . Mer specifikt, om H har h hörn, så kan en enkel n -vertex H -moll-fri graf ha som mest kanter, och vissa K h -moll-fria grafer har åtminstone det antalet kanter [13] . Således, om H har h hörn, så har H -moll-fria grafer medelgrad och dessutom degeneration . Dessutom har H -mollfria grafer en partitioneringssats som liknar partitioneringssatsen för plana grafer—för alla fasta H , och alla n -vertex H -mollfria grafer G , kan man hitta en delmängd av hörn av storlek , vars borttagning delar grafen G i två (eventuellt frånkopplade) subgrafer med högst 2 n /3 hörn vardera [14] . Ännu mer strikt, för alla fasta H , har H -moll- fria grafer trädbredd [15] .

Hadwigers gissning gör antagandet att om grafen G inte innehåller en mindre isomorf till en komplett graf med k hörn, så har grafen G en regelbunden färgning i k  − 1 färger [16] . Fallet k  =5 är en omformulering av fyrfärgsproblemet . Hadwigers gissning har bevisats för k  ≤ 6 [17] , men inte på ett generellt sätt. Bolobas, Katlin och Erdős [18] kallade problemet "ett av de djupaste olösta problemen inom grafteorin". Ett annat resultat som relaterar fyra färgsatsen till grafiska mindreåriga är snarksatsen , som tillkännagavs av Robertson, Sanders, Seymour och Thomas [19] . Satsen är en förstärkning av fyrfärgssatsen och lades fram (som en gissning) av Tutt och den säger att varje 3-regelbunden brolös graf som kräver att fyra färger är linjefärgade måste innehålla Petersen-grafen som en moll [20 ] [21] .

Familjer av grafer stängda i mindreåriga

Många familjer av grafer har egenskapen att vilken moll som helst av en graf i F också är i F . I det här fallet sägs klassen av grafer vara mindre stängd . Till exempel, för en plan graf eller graf som bäddas in i en fast topologisk yta , kan varken ta bort kanter eller sammandragande kanter öka släktet för inbäddningen. Plana grafer och grafer som är inbäddade i vilken fast yta som helst bildar således mindre slutna familjer.

Om F är en mindre sluten familj, så finns det (på grund av egenskapen att helt kvasiordning av mindreåriga) bland de grafer som inte tillhör F , en ändlig uppsättning X av mindre minimala grafer. Dessa grafer är förbjudna minor för F  - en graf tillhör F om och endast om den inte innehåller någon graf från X som minor . Således kan vilken moll-sluten familj F som helst karakteriseras som en familj av mollfria grafer från X för någon finit uppsättning X av förbjudna minderåriga [3] [4] .

Ett välkänt exempel på denna typ av karaktärisering är Wagners sats , som karakteriserar plana grafer som grafer som varken har K 5 eller K 3,3 som moll [1] [2] .

I vissa fall kan egenskaperna hos grafer i en mindre sluten familj vara nära relaterade till egenskaperna hos uteslutna minderåriga. Till exempel, en mindre sluten familj av grafer F har en avgränsad väg om och endast om den förbjudna familjen i familjen inkluderar en skog [22] , F har ett begränsat träddjup om och endast om de förbjudna minderåriga inkluderar en frikopplad vägunion , F har en avgränsad trädbredd om och endast om dess förbjudna minor inkluderar en plan graf [23] , och F har en begränsad lokal trädbredd (ett funktionellt förhållande mellan diameter och trädbredd) om och endast om dess förbjudna minor inkluderar en apexgraf (a graf som blir plan när det ena hörnet) [24] [25] . Om H kan ritas på planet med en enda skärningspunkt (dvs. antalet skärningar i grafen är lika med ett), så gäller för grafer fria från H -moll den förenklade struktursatsen, enligt vilken sådana grafer är en klicksumma av plana grafer och grafer med en avgränsad trädbredd [26] [27] . Till exempel har både K 5 och K 3,3 skärningstalet ett, och som Wagner visade är grafer fria från K 5 exakt 3-klicksummorna av plana grafer och en Wagner-graf med åtta vertex , medan de fria från K 3,3 -grafer är exakt 2-klicksummorna av plana grafer och K 5 [28] .

Variationer

Topologiska minderåriga

En graf H kallas en topologisk moll av en graf G om indelningsgrafen för H är isomorf till en subgraf av G [29] . Det är lätt att se att vilken topologisk moll som helst är moll (i vanlig mening). Det omvända är dock inte generellt sant (till exempel är den fullständiga grafen K 5 i Petersen-grafen en moll, men är inte en topologisk moll), men gäller för en graf med en maximal grad som inte överstiger tre [30] .

Relationen mellan topologiska minderåriga är inte helt kvasiordnad på uppsättningen av ändliga grafer [31] , och därför är resultatet av Robertson och Seymour inte tillämpligt på topologiska mindreåriga. Det är dock lätt att konstruera karakteriseringar av ändliga förbjudna topologiska minderåriga från en karakterisering av finita förbjudna minderåriga.

Nedsänkt moll

Grafoperationen, som kallas lyftning , är ett centralt begrepp i begreppet nedsänkning . Lyft är en operation på intilliggande kanter. Givet tre hörn v , u och w , där (v, u) och (u, w)  är grafkanter, är lyft vuw , eller motsvarande (v, u), (u, w)  en operation som tar bort två kanter (v ) , u) och (u, w) och lägger till en kant (v, w) . I fallet där kanten (v, w) redan är närvarande, kommer v och w att vara sammankopplade med en annan kant, och så är operationen i huvudsak en multigrafoperation.

I det fall där grafen H kan erhållas från grafen G genom en sekvens av lyftoperationer (över G ) och sedan hitta en isomorf subgraf, säger vi att H är en nedsänkt moll av grafen G .

Det finns ett annat sätt att definiera nedsänkta minderåriga, vilket motsvarar lyftoperationen. Vi säger att H är en nedsänkt moll av en graf G om det finns en injektiv avbildning från hörn av H till hörn av G så att bilderna av intilliggande element i H är sammankopplade i G av banor som inte har gemensamma kanter.

Relationen mellan nedsänkta minderåriga är helt kvasiordnad på uppsättningen av ändliga grafer, och därför är resultaten av Roebrtson och Seymour tillämpliga på nedsänkta minderåriga. Dessutom betyder detta att alla familjer som är stängda i nedsänkta minderåriga kännetecknas av en ändlig familj av förbjudna inbäddade minderåriga.

I grafvisualisering visas nedsänkta moll som planariseringar av icke-plana grafer  - från en ritning av en graf på ett plan med skärningar kan en nedsänkt moll bildas genom att ersätta varje skärningspunkt med en ny vertex och dela varje korsad kant in på en väg. Detta gör att ritmetoder för plana grafer kan utökas till icke-plana grafer [32] .

Grunda minderåriga

En grund moll av en graf G  är en moll där kanterna på grafen G , sammandragna för att erhålla moll, bildar osammanhängande subgrafer med liten diameter . Grunda minderåriga bildar en sorts bro mellan graph-moll och subgrafer, i den meningen att högdjupa grunda minderåriga är desamma som de vanliga typerna av minderåriga, medan noll-djupa grunda minderåriga är exakt subgrafer [33] . De tillåter också teorin om graph minors att utvidgas till klasser av grafer, till exempel 1-planar graphs , som inte är stängda i att ta mindreåriga [34] .

Algoritmer

Beslutbarhetsproblemet med huruvida en graf H ingår i en graf G som ett biämne är i allmänhet NP-komplett. Till exempel, om H är en cykel med samma antal hörn som G , så är H en moll av G om och endast om G innehåller en Hamiltonsk graf . Men om G är en ingång och H är fixat kan problemet lösas i polynomtid. Mer specifikt är körtiden för att kontrollera om H är en moll av G i detta fall O ( n 3 ), där n  är antalet hörn i G och O large döljer en konstant som superexponentiellt beror på H [5] . På grund av ett resultat på graph minors förbättras denna algoritm till O ( n 2 ) [35] . Sålunda, när man använder en polynom-tidsalgoritm för att kontrollera om en given graf innehåller någon av de förbjudna minorerna, är det möjligt att känna igen medlemmarna i en minor-closed familj i polynomtid . Men för att tillämpa detta resultat konstruktivt är det nödvändigt att känna till de förbjudna minderåriga i graffamiljen [6] .

Anteckningar

  1. ↑ 12 Lovász , 2006 , sid. 77.
  2. ↑ 12 Wagner, 1937a .
  3. ↑ 1 2 Lovász, 2006 , volym 4, sid. 78.
  4. ↑ 12 Robertson , Seymour, 2004 .
  5. ↑ 12 Robertson , Seymour, 1995 .
  6. ↑ 12 Fellows , Langston, 1988 .
  7. ↑ Lovász (2006 ) säger emot sig själv. På sidan 76 skriver han att "parallella kanter och slingor är tillåtna", men på sidan 77 konstaterar han att "en graf är en skog om och bara om den inte innehåller triangeln K 3 som moll", vilket bara är sant för enkla grafer.
  8. ↑ Diestel (2005 ), kapitel 12: Minderåriga, träd och WQO; Robertson, Seymour (2004 ).
  9. ↑ Lovász, 2006 , sid. 76.
  10. ↑ Lovász, 2006 , sid. 80-82.
  11. ↑ Robertson, Seymour, 2003 .
  12. ↑ Mader, 1967 .
  13. ↑ Kostochka, 1984 ; Thomason, 1984 ; Thomason, 2001 .
  14. ↑ Alon, Seymour, Thomas, 1990 ; Plotkin, Rao, Smith, 1994 ; Reed, Wood, 2009 .
  15. ↑ Grohe, 2003 .
  16. ↑ Hadwiger, 1943 .
  17. ↑ Robertson, Seymour, Thomas, 1993 .
  18. ↑ Bollobás, Catlin, Erdős, 1980 .
  19. ↑ Men från och med 2012 har beviset inte publicerats ännu.
  20. ↑ Thomas, 1999 .
  21. ↑ Pegg, 2002 .
  22. ↑ Robertson, Seymour, 1983 .
  23. ↑ Lovász (2006 ), Theorem 9, sid. 81; Robertson, Seymour (1986 ).
  24. ↑ Eppstein, 2000 .
  25. ↑ Demaine, Hajiaghayi, 2004 .
  26. ↑ Robertson, Seymour, 1993 .
  27. ↑ Demaine, Hajiaghayi, Thilikos, 2002 .
  28. ↑ Wagner, 1937a ; Hall, 1943 .
  29. ↑ Diestel, 2005 , sid. tjugo.
  30. ↑ Diestel, 2005 , sid. 22.
  31. ↑ Ding, 1996 .
  32. ↑ Buchheim, Chimani, Gutwenger, Jünger, Mutzel, 2014 .
  33. ↑ Nešetřil, de Mendez, 2012 .
  34. ↑ Nešetřil, de Mendez, 2012 , sid. 319-321.
  35. ↑ Kawarabayashi, Kobayashi, Reed, 2012 .

Litteratur

Länkar