Grafstruktursætningen er et grundlæggende resultat i grafteori . Resultatet etablerer en dyb forbindelse mellem graph minor theory og topologiske indlejringer . Sætningen blev formuleret i sytten artikler i en serie på 23 artikler af Neil Robertson og Paul Seymour . Beviset for sætningen er meget langt og forvirrende. Kawarabayashi og Mohar [1] og Lowash [2] gennemgik sætningen i en form, der er tilgængelig for ikke-specialister, og beskrev sætningen og dens konsekvenser.
En minor af en graf G er enhver graf H , der er isomorf i forhold til en graf, der kan fås fra en undergraf af G ved at trække nogle kanter sammen. Hvis G ikke har en graf H som mol, så siger vi, at G er H - fri . Lad H være en fast graf. Intuitivt, hvis G er en stor H- fri graf, så må der være en "god grund" til at gøre det. Graph Structure Theorem giver en sådan "god grund" i form af en grov beskrivelse af strukturen af grafen G . I det væsentlige har enhver H- fri graf G en eller to strukturelle defekter - enten er G "for tynd" til at indeholde H som en minor, eller G kan være (næsten) topologisk indlejret i en overflade, der er for nem at indlejre den mindre H . Den første årsag opstår, når H er plan , og begge årsager opstår, når H er ikke-plan . Lad os først afklare disse begreber.
Træbredden af G er et positivt heltal, der definerer "tyndheden" af G . For eksempel har en forbundet graf G træbredde et, hvis og kun hvis det er et træ, og G har træbredde to, hvis og kun hvis det er en parallel-seriel graf . Det er intuitivt klart, at en stor graf G har en lille træbredde, hvis og kun hvis G antager strukturen af et stort træ, hvor noder og kanter er erstattet af små grafer. Vi vil give en præcis definition af træbredden i underafsnittet i forhold til kliksummerne. Der er en sætning om, at hvis H er en mol af en graf G , så overstiger træbredden af H ikke træbredden af G. En "god grund" til, at G er H- fri, er således, at træbredden af G ikke er særlig stor . Graph Structure Theorem har den konsekvens, at denne grund altid gælder, når H er plan .
Konsekvens 1. For enhver plan graf H eksisterer der et positivt heltal k , således at enhver H- fri graf har træbredde mindre end k .
Værdien af k i følge 1 er normalt meget større end træets bredde H (der er en bemærkelsesværdig undtagelse, når H = K 4 , det vil sige, H er lig med en komplet graf med fire hjørner, for hvilken k = 3). Dette er en af grundene til, at struktursætningen siges at beskrive den "ru struktur" af H - frie grafer.
Groft sagt er en overflade et sæt punkter med en lokal topologisk struktur i form af en skive. Overflader falder i to uendelige familier - orienterbare overflader omfatter kugle , torus , dobbelt torus osv. Ikke -orienterbare overflader inkluderer det rigtige projektive plan , Klein-flasken og så videre. En graf er indlejret i en overflade, hvis den kan tegnes på overfladen som et sæt af punkter (hjørnepunkter) og buer (kanter), så de ikke skærer eller rører hinanden, undtagen når spidserne og kanterne er indfaldende eller støder op til hinanden. En graf er plan , hvis den kan indlejres i en kugle. Hvis en graf G er indlejret i en bestemt overflade, så kan enhver mindre af grafen G også indlejres i den samme overflade. En "god grund" til, at en graf G er H- fri, er således muligheden for at indlejre G i en overflade, hvori H ikke kan indlejres.
Hvis H ikke er plan, kan strukturgrafsætningen ses som en stærk generalisering af Pontryagin-Kuratovsky-sætningen . Den version af denne sætning bevist af Wagner [3] siger, at hvis en graf G er både K 5 -fri og K 3,3 -fri, så er G plan. Denne sætning giver en "god grund" til, at G ikke har K 5 eller K 3,3 som biord. Mere specifikt er G indlejret i en kugle, mens hverken K 5 eller K 3,3 kan indlejres i en kugle. Begrebet "god grund" er ikke nok til den strukturelle grafsætning. Der kræves yderligere to koncepter - summer pr. klik og hvirvler .
En klike i en graf G er ethvert sæt af hjørner, der parvis støder op til hinanden i G. For et ikke-negativt heltal k er k -klik summen af to grafer G og K en hvilken som helst graf opnået ved i graferne G og K at vælge kliker af størrelse m ≤ k for nogle ikke-negative m , der identificerer disse to kliker i én klik (af størrelse m ) og slette nogle (muligvis nul) antal kanter i denne nye klike.
Hvis G 1 , G 2 , ..., G n er en liste over grafer, kan du få en ny graf ved at kombinere grafer fra listen ved hjælp af k-klik-summer . Det vil sige, at vi opretter en k -klik sum af grafen G 1 og G 2 , derefter skaber vi en k -klik sum af grafen G 3 med den forrige resulterende graf, og så videre. En graf har højst træbredde k , hvis den kan opnås som en k -klik sum af en liste af grafer, hvor hver graf højst har k + 1 hjørner.
Resultat 1 viser os, at k -kliksummer af små grafer beskriver den grove struktur af H- frie grafer i tilfælde af planaritet H . Hvis H er ikke-plan, er vi tvunget til også at overveje k -kliksummer af grafer, som vi hver især indlejrer i en overflade. Det følgende eksempel med H = K 5 illustrerer dette punkt. Grafen K 5 kan indlejres i enhver overflade, undtagen en kugle. Der er dog K 5 -frie grafer, der langt fra er plane. Især 3-klik summen af enhver liste af plane grafer giver en K 5 -fri graf. Wagner [3] definerede den nøjagtige struktur af K 5 - frie grafer som en del af en gruppe resultater kendt som Wagners sætning :
Sætning 2. Hvis G er fri for K 5 , så kan G fås som 3-klik summer af en liste af plane grafer og kopier af en specifik ikke-plan graf med 8 toppunkter.
Bemærk, at sætning 2 er en eksakt struktursætning, fordi den præcist definerer strukturen af K 5 -frie grafer. Sådanne resultater er sjældne i grafteori. Den strukturelle grafsætning er ikke præcis i den forstand, at for de fleste H- grafer omfatter den strukturelle beskrivelse af H- frie grafer nogle grafer, der ikke er H- frie.
Der er en fristelse til at antage, at en analog af sætning 2 gælder for andre grafer H end K 5 . Måske ville det lyde sådan her: For enhver ikke-plan graf H er der et positivt tal k, således at hver H-fri graf kan fås som en k-klik sum af en liste af grafer, som hver har enten højst k hjørner, eller indlejret i en overflade, hvori H ikke kan indlejres . Dette udsagn er for simpelt til at være sandt. Vi skal tillade hver indlejret graf G i at "snyde" på to begrænsede måder. For det første må vi tillade tilføjelse af nogle nye hjørner og kanter et begrænset antal steder på overfladen, som får lov til at krydse hinanden i en vis begrænset kompleksitet . Sådanne steder kaldes hvirvler . "Kompleksiteten" af en hvirvel er begrænset af en parameter kaldet dens dybde , som er tæt forbundet med kurvens stibredde . Læseren kan springe over at læse den nøjagtige definition af dybdek eddyen i næste afsnit. For det andet skal vi tillade, at et begrænset antal nye hjørner tilføjes til indlejrede hvirvelgrafer.
En kant af en indlejret graf er en åben 2-celle af overfladen, der ikke skærer grafen, men hvis grænser er foreningen af nogle kanter af den indlejrede graf. Lad F være en flade af en indlejret graf G og lad v 0 , v 1 , ..., v n −1 , v n = v 0 være toppunkterne, der ligger på grænsen af F (i cyklusrækkefølge). Det cykliske interval for F er et sæt af hjørner af formen { v a , v a +1 , ..., v a + s }, hvor a og s er heltal, og hvor indekset er taget modulo n . Lad Λ være en endelig liste over cyklusintervaller for F . Vi konstruerer en ny graf som følger. For hvert cyklusinterval L fra Λ tilføjer vi et nyt toppunkt v L forbundet med et eller andet antal (muligvis nul) hjørner fra L . For hvert par { L , M } af intervaller i Λ kan vi tilføje en kant, der forbinder v L med v M , hvis L og M har et ikke-tomt skæringspunkt. Den resulterende graf siges at være opnået fra G ved at tilføje en hvirvel af dybde højst k (til en flade F ), hvis intet toppunkt på F vises i mere end k intervaller fra Λ.
Strukturel grafsætning . For enhver graf H er der et positivt heltal k, således at enhver H-fri graf kan opnås som følger:
Bemærk, at trin 1 og 2 giver tomme grafer, hvis H er plan, men det begrænsede antal hjørner tilføjet i trin 3 gør påstanden kompatibel med konsekvens 1.
Stærkere versioner af den strukturelle grafsætning er mulige afhængigt af sættet H af forbudte mindreårige. For eksempel, hvis en af graferne i H er plan , så har enhver H- fri graf en trænedbrydning af afgrænset bredde. Tilsvarende kan det repræsenteres som en sum over en klike af grafer af konstant størrelse [4] . Hvis en af graferne H kan tegnes i planet med et skæringspunkt , så tillader H -mol-frie grafer en kliksum-nedbrydning af grafer af konstant størrelse og grafer af afgrænset slægt (uden at bruge hvirvler) [5] [6] ). Forskellige forstærkninger kendes også, hvis en af graferne H er en apex-graf [7] .