Grafstruktursatsen är ett grundläggande resultat inom grafteorin . Resultatet etablerar en djup koppling mellan grafisk teori och topologiska inbäddningar . Satsen formulerades i sjutton artiklar i en serie av 23 artiklar av Neil Robertson och Paul Seymour . Beviset för satsen är mycket långt och förvirrande. Kawarabayashi och Mohar [1] och Lowash [2] granskade satsen i en form tillgänglig för icke-specialister, och beskrev satsen och dess följder.
En moll av en graf G är vilken graf som helst som är isomorf till en graf som kan erhållas från en subgraf av G genom att dra ihop några kanter. Om G inte har en graf H som moll, så säger vi att G är H - fri . Låt H vara en fast graf. Intuitivt, om G är en stor H -fri graf, måste det finnas någon "god anledning" för att göra det. Graph Structure Theorem ger en sådan "god anledning" i form av en grov beskrivning av grafens G . I huvudsak har vilken H -fri graf G som helst en eller två strukturella defekter - antingen är G "för tunt" för att innehålla H som en moll, eller så kan G vara (nästan) topologiskt inbäddad i en yta som är för lätt att bädda in det mindre H . Den första orsaken uppstår när H är plan , och båda orsakerna uppstår när H är icke-plan . Låt oss först klargöra dessa begrepp.
Trädbredden för G är ett positivt heltal som definierar "tunnheten" av G . Till exempel har en sammankopplad graf G trädbredd ett om och endast om det är ett träd, och G har trädbredd två om och endast om det är en parallell-seriell graf . Det är intuitivt tydligt att en stor graf G har en liten trädbredd om och bara om G antar strukturen hos ett stort träd där noder och kanter ersätts av små grafer. Vi kommer att ge en exakt definition av trädbredden i underavsnittet i förhållande till klicksummorna. Det finns ett teorem att om H är en moll av en graf G , så överstiger inte trädbredden på H trädbredden på G . En "god anledning" till att G är H -fri är alltså att trädbredden för G inte är särskilt stor . Graph Structure Theorem har som konsekvens att detta skäl alltid gäller när H är plan .
Resultat 1. För varje plan graf H finns det ett positivt heltal k så att varje H -fri graf har trädbredd mindre än k .
Värdet på k i följd 1 är vanligtvis mycket större än trädets bredd H (det finns ett anmärkningsvärt undantag när H = K 4 , det vill säga H är lika med en komplett graf med fyra vertex där k = 3). Detta är en av anledningarna till att struktursatsen sägs beskriva den "grova strukturen" hos H - fria grafer.
Grovt sett är en yta en uppsättning punkter med en lokal topologisk struktur i form av en skiva. Ytor delas in i två oändliga familjer - orienterbara ytor inkluderar sfär , torus , dubbel torus , etc. Icke- orienterbara ytor inkluderar det verkliga projektiva planet , Klein-flaskan och så vidare. En graf är inbäddad i en yta om den kan ritas på ytan som en uppsättning punkter (hörn) och bågar (kanter) så att de inte skär eller vidrör varandra, förutom när hörn och kanter är infallande eller intill varandra. En graf är plan om den är inbäddningsbar i en sfär. Om en graf G är inbäddad i en viss yta, så är även valfri moll av grafen G inbäddad i samma yta. En "god anledning" till att en graf G är H -fri är alltså möjligheten att bädda in G i en yta i vilken H inte kan bäddas in.
Om H inte är plan, kan strukturgrafsatsen ses som en stark generalisering av Pontryagin-Kuratovsky-satsen . Den version av detta teorem som bevisats av Wagner [3] säger att om en graf G är både K 5 -fri och K 3,3 -fri, så är G plan. Denna sats ger en "god anledning" för G att inte ha K 5 eller K 3,3 som biroller. Mer specifikt är G inbäddad i en sfär, medan varken K 5 eller K 3,3 kan bäddas in i en sfär. Begreppet "goda skäl" är inte tillräckligt för strukturgrafsatsen. Ytterligare två koncept krävs - summor per klick och virvlar .
En klick i en graf G är vilken uppsättning hörn som helst som ligger parvis intill varandra i G . För ett icke-negativt heltal k , är k -klicksumman av två grafer G och K vilken graf som helst som erhålls genom att i graferna G och K välja klick med storleken m ≤ k för några icke-negativa m , vilket identifierar dessa två klick i en klick (av storlek m ) och ta bort något (möjligen noll) antal kanter i denna nya klick.
Om G 1 , G 2 , ..., G n är en lista med grafer kan du få en ny graf genom att kombinera grafer från listan med hjälp av k-klicksummor . Det vill säga, vi skapar en k -klicksumma av grafen G 1 och G 2 , sedan skapar vi en k -klicksumma av grafen G 3 med den föregående resulterande grafen, och så vidare. En graf har högst trädbredd k om den kan erhållas som en k -klick summa av någon lista med grafer där varje graf har högst k + 1 hörn.
Resultat 1 visar att k -klicksummor av små grafer beskriver den grova strukturen för H -fria grafer i fallet med planaritet H . Om H är icke-plan, tvingas vi att även överväga k -klicksummor av grafer, som var och en bäddar in i en yta. Följande exempel med H = K 5 illustrerar denna punkt. Grafen K 5 kan bäddas in i vilken yta som helst, förutom en sfär. Det finns dock K 5 -fria grafer som är långt ifrån plana. Speciellt ger summan med 3 klick av en lista med plana grafer en K 5 -fri graf. Wagner [3] definierade den exakta strukturen av K 5 -fria grafer som en del av en grupp resultat som kallas Wagners sats :
Sats 2. Om G är fri från K 5 , så kan G erhållas som 3-klicksummor av en lista med plana grafer och kopior av någon specifik icke-plan graf med 8 hörn.
Observera att sats 2 är en exakt struktursats eftersom den definierar exakt strukturen för K 5 -fria grafer. Sådana resultat är sällsynta i grafteorin. Strukturgrafsatsen är inte exakt i den meningen att för de flesta H -grafer innehåller den strukturella beskrivningen av H -fria grafer några grafer som inte är H -fria.
Det finns en frestelse att anta att en analog till sats 2 gäller för andra grafer H än K 5 . Kanske skulle det låta så här: För alla icke-planära grafer H finns det ett positivt tal k så att varje H-fri graf kan erhållas som en k-klick summa av en lista med grafer, som var och en har högst k hörn, eller inbäddade i någon yta där H inte kan bäddas in . Detta påstående är för enkelt för att vara sant. Vi måste tillåta varje kapslad graf G i att "fuska" på två begränsade sätt. För det första måste vi tillåta, på ett begränsat antal platser på ytan, tillägg av några nya hörn och kanter, som tillåts skära varandra i en viss begränsad komplexitet . Sådana platser kallas virvlar . "Komplexiteten" hos en virvel begränsas av en parameter som kallas dess djup , som är nära relaterad till kurvans bredd . Läsaren kan hoppa över att läsa den exakta definitionen av djupk eddy i nästa avsnitt. För det andra måste vi tillåta att ett begränsat antal nya hörn läggs till för kapslade virveldiagram.
En kant på en kapslad graf är en öppen 2-cell av ytan som inte skär grafen, men vars gränser är föreningen av vissa kanter på den kapslade grafen. Låt F vara en yta av en inbäddad graf G och låt v 0 , v 1 , ..., v n −1 , v n = v 0 vara de hörn som ligger på gränsen till F (i cykelordning). Det cykliska intervallet för F är en uppsättning av hörn av formen { v a , v a +1 , ..., v a + s }, där a och s är heltal, och där indexet tas modulo n . Låt Λ vara en ändlig lista över cykelintervall för F . Vi konstruerar en ny graf enligt följande. För varje cykelintervall L från Λ lägger vi till en ny vertex v L kopplad till ett antal (eventuellt noll) hörn från L . För varje par { L , M } av intervall i Λ kan vi lägga till en kant som förbinder v L med v M om L och M har en icke-tom skärningspunkt. Den resulterande grafen sägs erhållas från G genom att lägga till en virvel av djup som högst k (till en yta F ) om ingen vertex på F visas i mer än k intervall från Λ.
Strukturell grafsats . För varje graf H finns det ett positivt heltal k så att vilken H-fri graf som helst kan erhållas enligt följande:
Observera att steg 1 och 2 ger tomma grafer om H är plan, men det begränsade antalet hörn som läggs till i steg 3 gör påståendet kompatibelt med konsekvens 1.
Starkare versioner av strukturgrafsatsen är möjliga beroende på mängden H av förbjudna minderåriga. Till exempel, om en av graferna i H är plan , så har varje H -fri graf en trädupplösning av begränsad bredd. På motsvarande sätt kan det representeras som en summa över en klick grafer av konstant storlek [4] . Om en av graferna H kan ritas i planet med en skärningspunkt , så tillåter H -mollfria grafer en klicksummauppdelning av grafer med konstant storlek och grafer för avgränsat släkte (utan att använda virvlar) [5] [6] ). Olika förstärkningar är också kända om någon av graferna H är en apexgraf [7] .