Tæl mindre

Et bifag i grafteori  er en graf for en given graf , som kan dannes ved at fjerne kanter og spidser og trække kanter sammen .

Teorien om graph minor begyndte med Wagners sætning , som siger, at en graf er plan, hvis og kun hvis dens minor ikke hører til hverken den komplette graf K 5 eller den komplette todelte graf K 3,3 [1] [2] . Det følger af Robertson-Seymour- sætningen, at der findes analoger til den forbudte mindre karakterisering for enhver egenskab ved grafer, der er bevaret under fjernelse af kant og sammentrækning [3] [4] .

For enhver graf H , kan man kontrollere, om H er en minor af inputgrafen G i polynomisk tid [5] . Sammen med karakteriseringen af ​​forbudte mindreårige følger det, at enhver grafegenskab, der er bevaret under sletninger og sammentrækninger, kan genkendes i polynomisk tid [6] .

Blandt andre resultater og formodninger ved brug af grafer er grafstruktursætningen , hvorefter grafer, der ikke indeholder H som mol, kan dannes ved at lime simplere dele sammen, og Hadwiger-formodningen , der relaterer umuligheden af ​​graffarvning til eksistensen af en stor komplet graf som hans underordnede. Vigtige varianter af mindreårige grafer er topologiske mindreårige og nedsænkede mindreårige.

Definitioner

Kantkontraktion er en operation, der fjerner en kant fra en graf og slår enderne af kanten sammen i et enkelt toppunkt. En urettet graf H er en mindre af en anden urettet graf G , hvis en graf, der er isomorf til H , kan opnås fra G ved at trække kanter sammen, fjerne nogle kanter og fjerne nogle isolerede hjørner. Rækkefølgen, hvori sammentrækninger og sletninger foretages i G , påvirker ikke den resulterende graf H .

Graph mindreårige studeres ofte i den mere generelle kontekst af matroide mindreårige . I denne sammenhæng antages det normalt, at grafer er forbundet, kan have sløjfer og flere kanter (dvs. multigrafer betragtes som , ikke simple grafer). Det er forbudt at trække i løkken og fjerne skærkanten . Med denne fremgangsmåde forlader fjernelse af en kant grafens rangorden uændret, mens en sammentrækning af en kant altid reducerer rangeringen med én.

I andre sammenhænge (som i studiet af pseudoskove , for eksempel ), giver det mening at tillade skærekanter at blive fjernet og tillade grafer at blive afbrudt, men det giver også mening at forbyde multigrafer. I denne version af teorien om mindre grafer er grafen altid forenklet efter enhver kantsammentrækning for at eliminere sløjfer og flere kanter [7]

Eksempel

I det følgende eksempel er graf H en mindre af graf G :

H.

G.

Følgende figur illustrerer dette. Først konstruerer vi en undergraf af G ved at fjerne de stiplede kanter (og det resulterende isolerede toppunkt) og derefter trække den grå kant sammen (ved at forbinde de to hjørner, som kanten forbinder):

Vigtigste resultater og formodninger

Det kan let verificeres, at forholdet mellem grafiske minorer danner en delrækkefølge på isomorfi-klassen af ​​urettede grafer - relationen er transitiv (minor af en graf G er selv en minor af G ) og graferne G og H kan være hinandens mindreårige, hvis de er isomorfe, da enhver ikke-triviel operation med en minor fjerner kanter eller hjørner. Et dybt resultat af Neil Robertson og Paul Seymour fastslår, at denne delrækkefølge i virkeligheden er en fuldstændig kvasi-ordnet  - givet en uendelig liste G 1 , G 2 ,... af endelige grafer, er der altid to indekser i < j , således at G i er en mol af grafen G j . En ækvivalent formulering af udsagnet er, at ethvert sæt grafer kun kan have et begrænset antal minimale elementer ved en mindre relation [8] . Dette resultat beviser den formodning, der hidtil var kendt som Wagner-formodningen. Wagner formodede meget tidligere, men udgav den først i 1970 [9] .

I løbet af beviset beviste Seymour og Robertson også grafstruktursætningen , hvori de bestemte, for enhver fast graf H , den grove struktur af enhver graf, der ikke indeholder H som en mol. Sætningens udsagn er lang og indviklet, men kort fortalt siger sætningen, at en sådan graf skal have strukturen som en sum over kliker af mindre grafer, som opnås ved en lille ændring af grafer indlejret i overflader af afgrænset slægt . Deres teori etablerer således en grundlæggende sammenhæng mellem grafiske minorer og topologiske indlejringer af grafer [10] [11] .

For enhver graf H , skal simple H-mol-frie grafer være sparsomme , hvilket betyder, at antallet af kanter er mindre end nogle konstante gange antallet af hjørner [12] . Mere specifikt, hvis H har h -spidser , så kan en simpel n - vertex H -mol-fri graf højst have kanter, og nogle K h -mol-frie grafer har mindst det antal kanter [13] . Således, hvis H har h hjørner, så har H -mol-frie grafer gennemsnitlig grad og derudover degeneration . Derudover har H -mol-frie grafer en partitioneringssætning , der ligner den plane graf-partitioneringssætning - for enhver fast H , og enhver n - vertex H -mol-fri graf G , kan man finde en delmængde af toppunkter af størrelse , hvis fjernelse deler grafen G i to (eventuelt afbrudte) undergrafer med højst 2 n /3 hjørner hver [14] . Endnu mere strengt, for enhver fast H , har H- mol- frie grafer træbredde [15] .

Hadwigers formodning gør den antagelse, at hvis grafen G ikke indeholder en mindre isomorf til en komplet graf med k hjørner, så har grafen G en regelmæssig farvning i k  − 1 farver [16] . Tilfældet k  = 5 er en omformulering af firefarveproblemet . Hadwigers formodning er blevet bevist for k  ≤ 6 [17] , men ikke på en generel måde. Bolobas, Katlin og Erdős [18] kaldte problemet "et af de dybeste uløste problemer i grafteori". Et andet resultat, der relaterer fire-farvesætningen til at tegne mindre mol, er snark-sætningen , som blev annonceret af Robertson, Sanders, Seymour og Thomas [19] . Sætningen er en styrkelse af firefarvesætningen og blev fremsat (som en formodning) af Tutt , og den siger, at enhver 3-regulær broløs graf , der kræver, at fire farver er linjefarvede, skal indeholde Petersen-grafen som en mol [20 ] [21] .

Familier af grafer lukket i mindreårige

Mange familier af grafer har den egenskab, at enhver mindre af en graf i F også er i F . I dette tilfælde siges klassen af ​​grafer at være mindre lukket . For eksempel, for enhver plan graf eller graf, der er indlejret i en fast topologisk overflade , kan hverken fjernelse af kanter eller kontraherende kanter øge slægten af ​​indlejringen. Plane grafer og grafer, der kan indlejres i enhver fast overflade, danner således mindre lukkede familier.

Hvis F er en mindre lukket familie, så (på grund af egenskaben med fuldstændig kvasi-ordening af mindreårige) blandt graferne, der ikke hører til F , er der et endeligt sæt X af mindre minimale grafer. Disse grafer er forbudte minor for F  - en graf tilhører F , hvis og kun hvis den ikke indeholder nogen graf fra X som minor . En hvilken som helst mol-lukket familie F kan således karakteriseres som en familie af mol-frie grafer fra X for et eller andet endeligt sæt X af forbudte mindreårige [3] [4] .

Et velkendt eksempel på denne type karakterisering er Wagners sætning , der karakteriserer plane grafer som grafer, der hverken har K 5 eller K 3,3 som biord [1] [2] .

I nogle tilfælde kan egenskaberne ved grafer i en mindre lukket familie være tæt forbundet med egenskaberne for udelukkede mindreårige. For eksempel har en mindre lukket familie af grafer F en afgrænset sti, hvis og kun hvis den forbudte familie i familien omfatter en skov [22] , F har en afgrænset trædybde, hvis og kun hvis de forbudte mindreårige inkluderer en afkoblet stiforening , F har en afgrænset træbredde, hvis og kun hvis dens forbudte mindretal inkluderer en plan graf [23] , og F har en afgrænset lokal træbredde (et funktionelt forhold mellem diameter og træbredde), hvis og kun hvis dets forbudte mindretal inkluderer en topgraf (a graf, der bliver plan, når det ene toppunkt) [24] [25] . Hvis H kan tegnes på planen med et enkelt skæringspunkt (dvs. antallet af skæringspunkter i grafen er lig med én), så for grafer fri for H- mol er den forenklede struktursætning sand, ifølge hvilken sådanne grafer er en kliksum af plane grafer og grafer med en afgrænset træbredde [26] [27] . For eksempel har både K 5 og K 3,3 et skæringsnummer på 1, og som Wagner viste, er grafer fri fra K 5 præcis 3-kliks summen af ​​plane grafer og en otte-vertex Wagner-graf , mens de frie fra K 3,3 grafer er præcis 2-kliks summen af ​​plane grafer og K 5 [28] .

Variationer

Topologiske mindreårige

En graf H kaldes en topologisk minor af en graf G , hvis underinddelingsgrafen for H er isomorf med en undergraf af G [29] . Det er let at se, at enhver topologisk mol er en mol (i sædvanlig forstand). Det omvendte er dog ikke generelt sandt (f.eks. er den komplette graf K 5 i Petersen-grafen en mol, men er ikke en topologisk mol), men gælder for en graf med en maksimal grad, der ikke overstiger tre [30] .

Relationen mellem topologiske mindreårige er ikke fuldstændig kvasi-ordnet på sættet af endelige grafer [31] , og derfor er resultatet af Robertson og Seymour uanvendeligt for topologiske mindreårige. Det er dog let at konstruere karakteriseringer af endelige forbudte topologiske mindreårige ud fra en karakterisering af endelige forbudte mindreårige.

Nedsænket mol

Grafoperationen, kaldet løft , er et centralt begreb i begrebet fordybelse . Løft er en operation på tilstødende kanter. Givet tre hjørner v , u og w , hvor (v, u) og (u, w)  er grafkanter, løfte vuw eller tilsvarende (v, u), (u, w)  er en operation, der fjerner to kanter (v) , u) og (u, w) og tilføjer en kant (v, w) . I det tilfælde, hvor kanten (v, w) allerede er til stede, vil v og w være forbundet med en anden kant, og operationen er derfor i det væsentlige en multigrafoperation.

I det tilfælde, hvor grafen H kan fås fra grafen G ved en sekvens af løfteoperationer (over G ) og derefter finde en isomorf subgraf, siger vi, at H er en nedsænket mol af grafen G .

Der er en anden måde at definere nedsænkede mindreårige på, som svarer til løfteoperationen. Vi siger, at H er en nedsænket mol af en graf G , hvis der findes en injektiv afbildning fra hjørnerne af H til hjørnerne af G , således at billederne af tilstødende elementer i H er forbundet i G af stier, der ikke har fælles kanter.

Forholdet mellem nedsænkede mindreårige er fuldstændig kvasi-ordnet på sættet af endelige grafer, og derfor er resultaterne af Roebrtson og Seymour anvendelige for nedsænkede mindreårige. Desuden betyder dette, at enhver familie, der er lukket i nedsænkede mindreårige, er karakteriseret ved en begrænset familie af forbudte indlejrede mindreårige.

I grafvisualisering vises nedsænkede mindreårige som planariseringer af ikke-plane grafer  - fra en tegning af en graf på et plan med skæringspunkter, kan en nedsænket mol dannes ved at erstatte hvert skæringspunkt med et nyt toppunkt og opdele hver krydsede kant ind på en sti. Dette gør det muligt at udvide tegnemetoder til plane grafer til ikke-plane grafer [32] .

Lavvandede mindreårige

En lav moll af en graf G  er en mol, hvor kanterne af grafen G , der er kontraheret for at opnå den mol, danner usammenhængende undergrafer med lille diameter . Shallow minors danner en slags bro mellem graph minors og subgraphs, i den forstand, at højdybde lavvandede minors er de samme som de sædvanlige typer af minors, mens nul-depth lavvandede minors er nøjagtigt subgraphs [33] . De gør det også muligt at udvide teorien om mindreårige grafer til klasser af grafer, såsom 1-planære grafer , der ikke er lukkede for at tage mindreårige [34] .

Algoritmer

Afgørelighedsproblemet med , om en graf H er indeholdt i en graf G som et minor, er generelt NP-komplet. For eksempel, hvis H er en cyklus med det samme antal hjørner som G , så er H en mindre af G , hvis og kun hvis G indeholder en Hamiltonsk graf . Men hvis G er et input, og H er fikset, kan problemet løses i polynomisk tid. Mere specifikt er køretiden for at kontrollere, om H er en minor af G i dette tilfælde, O ( n 3 ), hvor n  er antallet af hjørner i G , og O large skjuler en konstant, der afhænger supereksponentielt af H [5] . På grund af et resultat på graph minors, forbedres denne algoritme til O ( n 2 ) [35] . Når man anvender en polynomial-tidsalgoritme til at kontrollere, om en given graf indeholder nogen af ​​de forbudte mindreårige, er det således muligt at genkende medlemmerne af enhver mindre-lukket familie i polynomiel tid . Men for at anvende dette resultat konstruktivt er det nødvendigt at kende de forbudte mindreårige i graffamilien [6] .

Noter

  1. ↑ 12 Lovász , 2006 , s. 77.
  2. ↑ 12 Wagner, 1937a .
  3. ↑ 1 2 Lovász, 2006 , bind 4, s. 78.
  4. ↑ 12 Robertson , Seymour, 2004 .
  5. ↑ 12 Robertson , Seymour, 1995 .
  6. ↑ 12 Fellows , Langston, 1988 .
  7. ↑ Lovász (2006 ) modsiger sig selv. På side 76 skriver han, at "parallelle kanter og sløjfer er tilladt", men på side 77 udtaler han, at "en graf er en skov, hvis og kun hvis den ikke indeholder trekant K 3 som mol", hvilket kun gælder for simple grafer.
  8. ↑ Diestel (2005 ), Kapitel 12: Mindreårige, træer og WQO; Robertson, Seymour (2004 ).
  9. ↑ Lovász, 2006 , s. 76.
  10. ↑ Lovász, 2006 , s. 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. ↑ Fra 2012 er beviset dog ikke offentliggjort endnu.
  20. ↑ Thomas, 1999 .
  21. ↑ Pegg, 2002 .
  22. ↑ Robertson, Seymour, 1983 .
  23. ↑ Lovász (2006 ), Sætning 9, s. 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 , s. tyve.
  30. ↑ Diestel, 2005 , s. 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 , s. 319-321.
  35. ↑ Kawarabayashi, Kobayashi, Reed, 2012 .

Litteratur

Links