Robertson-Seymour- sætningen (også kaldet den lille grafiske sætning [1] ) siger, at enhver familie af grafer , der er lukket under kantfjernelse og sammentrækningsoperationer, kan defineres af et begrænset sæt af forbudte grafer .
For eksempel lukkes sættet af plane grafer under operationerne med at fjerne og trække kanter sammen; de forbudte grafer i dette tilfælde er den komplette graf K 5 og den komplette todelte graf K 3,3 . Det sidste udsagn kaldes Wagner-sætningen og er tæt forbundet med Pontryagin-Kuratovsky-sætningen .
Sætningen er bredt kendt for sin elementære formulering i mangel af et simpelt bevis. Hun går under navnet Neil Robertson.og Paul Seymour , som beviste det i en serie på tyve artikler på i alt 500 sider udgivet fra 1983 til 2004 [2] [3] [4] . Før beviset var sætningen af sætningen kendt som Wagner-formodningen , selvom Wagner selv hævdede, at han aldrig udtalte denne formodning [5] .
En svagere påstand for træer følger af Kruskals træsætning. Udtalelsen blev fremsat i form af en hypotese i 1937 af den ungarske matematiker Andrew Vazonyiog bevist i 1960 uafhængigt af Joseph Kruskalog S. Tarkovsky [6] [7] .
En mindre af en urettet graf G er enhver graf, der kan opnås fra G ved en (muligvis tom) sekvens af kantkontraktion og fjernelse af kanter og toppunkter af G . Minoritetsrelationen danner en partiel orden på sættet af alle distinkte endelige urettede grafer, da denne relation opfylder tre partielle ordensaksiomer - relationen er refleksiv (enhver graf er en minor af sig selv), transitiv (en minor af en graf G er sig selv en mol af en graf G ), og antisymmetrisk (hvis to grafer G og H er mindre af hinanden, skal de være isomorfe ). Men hvis graferne er isomorfe, kan de stadig betragtes som forskellige objekter, så danner rækkefølgen efter minor en forudbestilling , en relation der er refleksiv og transitiv, men ikke nødvendigvis antisymmetrisk [1] .
En forudbestilling siges at danne en fuldstændig kvasiordnet relation, hvis den ikke indeholder enten en uendeligt aftagende kæde, heller ikke en uendelig antikæde [8] . For eksempel er det sædvanlige forhold mellem ikke-negative heltal fuldstændig kvasi-ordnet, men den samme rækkefølge på sættet af alle heltal vil ikke være sådan, da den indeholder en uendelig faldende kæde 0, −1, −2, −3...
Robertson-Seymour-sætningen siger, at endelige, ikke-rettede grafer og grafer (som en relation) er fuldt kvasi-ordnede. Det er klart, at minoritetsrelationen ikke indeholder nogen uendelig faldende kæde, da enhver sammentrækning eller fjernelse reducerer antallet af kanter eller hjørner af grafen (ikke-negative heltal) [9] . Den ikke-trivielle del af sætningen er, at der ikke er uendelige antikæder, det vil sige uendelige sæt af grafer, der ikke er relateret til hinanden ved en minoritetsrelation. Hvis S er et sæt af grafer, og M er en delmængde af S , der indeholder en repræsentativ graf for hver ækvivalensklasse af minimale elementer (grafer, der tilhører S , men enhver egentlig mindre af dem tilhører ikke S ), så danner M en antikæde. Således er sætningens ækvivalente udsagn, at for ethvert uendeligt sæt S af grafer, skal der kun være et endeligt antal ikke-isomorfe minimale elementer.
En anden tilsvarende formulering af sætningen siger, at i ethvert uendeligt sæt af grafer skal der være et par grafer, hvoraf den ene er en mindre af den anden [9] . Udsagnet om, at ethvert uendeligt sæt har et endeligt antal minimale elementer, indebærer dette sidste udsagn, da alle de resterende (ikke-minimale) grafer danner et sådant par. I den anden retning følger det af denne formulering af sætningen, at der ikke kan være uendelige antikæder, da en uendelig antikæde ikke indeholder elementer forbundet med en minoritetsrelation.
En familie F af grafer siges at være lukket under driften af at tage en mindreårig, hvis nogen mindre af en graf i F også hører til F . Hvis F er en mindre lukket familie, så lad S være det sæt af grafer, der ikke hører til F ( komplementet af mængden F ). Ifølge Robertson-Seymour-sætningen er der et endeligt sæt H af minimale elementer i S . Disse minimale elementer danner en forbudt grafkarakterisering af sættet F — grafer fra F er præcis de grafer, der ikke har nogen graf fra H som en mol [10] [11] . Medlemmerne af sættet H kaldes ugyldige mindreårige (eller forbudte mindreårige ) for familien F , og selve sættet H kaldes et obstruerende sæt.
For eksempel lukkes plane grafer ved dannelsen af en mol - at trække en kant sammen i en plan graf eller fjerne en kant eller et toppunkt kan ikke ødelægge planheden. Plane grafer har således en karakterisering af forbudte mol, som i dette tilfælde er defineret af Wagners sætning - sættet H af mindre minimale ikke-plane grafer indeholder præcis to grafer, en komplet graf K 5 og en komplet todelt graf K 3,3 . Plane grafer er præcis de grafer, der ikke har elementer fra mængden { K 5 , K 3,3 } som minor.
Eksistensen af karakteriseringer af forbudte mindreårige for alle mindre lukkede familier af grafer er en tilsvarende formulering af Robertson-Seymour-sætningen. Antag, at enhver mindre lukket familie F har et endeligt sæt H af minimale forbudte mindreårige, og lad S være ethvert uendeligt sæt af grafer. Vi definerer F for S som en familie af grafer, der ikke har mindre i S . Så er sættet F mol lukket og har et endeligt sæt H af minimale forbudte mindreårige. Lad C være komplementet til F . S er en delmængde af C , fordi S og F ikke skærer hinanden. Sættet H indeholder minimale grafer fra C . Tag en graf G fra H . G kan ikke have egentlige mindreårige i S , da G er minimal i C. Samtidig skal G have et biord i S , for ellers ville G være et element af F. G er således et element af S , hvilket betyder, at H er en delmængde af S , og alle andre grafer fra S har mindretal fra grafsættet H , så H er et endeligt sæt af minimale elementer af S.
Antag på den anden side, at ethvert sæt grafer har en begrænset delmængde af minimale grafer, og lad F være et mindre lukket sæt . Vi ønsker at finde et sæt H af grafer, således at grafen er indeholdt i F , hvis og kun hvis den ikke har nogen biord i H . Lad E være det sæt af grafer, der ikke er mindre af nogen graf fra F , og lad H være et endeligt sæt af minimale elementer fra E . Lad nu en vilkårlig graf G blive givet . Lad G høre til F . G kan ikke have mindreårige fra H , da G tilhører F og H er en delmængde af E . Lad nu G ikke høre til F . Så er G ikke en mol af nogen graf i F , da F er lukket i mol. G hører altså til E , så G har et biord i H.
Følgende sæt af endelige grafer er lukket i mol, og har derfor (ifølge Robertson-Seymour-sætningen) en karakterisering ved forbudte grafer:
Nogle eksempler på endelige obstruktive mængder var allerede kendt for nogle klasser, selv før beviset for Robertson-Seymour-sætningen. For eksempel er forhindringen for alle skove en løkke (eller, hvis vi begrænser os til simple grafer , en cyklus med tre hjørner). Det betyder, at en graf er en skov, hvis og kun hvis ingen af dens mindre er en løkke (hhv. en cyklus med tre hjørner). Den eneste forhindring for et sæt stier er et træ med fire hjørner, hvoraf den ene har grad 3. I disse tilfælde består forhindringen af et enkelt element, men generelt kan der være flere elementer. Wagners sætning siger, at en graf er plan, hvis og kun hvis den hverken indeholder K 5 eller K 3,3 som mol. Med andre ord er mængden { K 5 , K 3,3 } obstruktionssættet for alle plane grafer, og det er minimum obstruktionssæt. En lignende sætning siger, at K 4 og K 2,3 er forbudte minor for sættet af ydreplanære grafer.
Selvom Robertson-Seymour-sætningen udvider disse resultater til vilkårlige mindre lukkede familier af grafer, erstatter den ikke disse resultater, fordi den ikke eksplicit beskriver obstruktionssættet for nogen familie. For eksempel angiver sætningen, at sættet af toroidale grafer har et begrænset obstruktionssæt, men giver ikke noget sådant sæt. Det komplette sæt af forbudte mindreårige til toroidale grafer forbliver ukendt og indeholder mindst 16.000 grafer [13] .
Robertson-Seymour-sætningen har en vigtig konsekvens i beregningsmæssig kompleksitetsteori, da Robertson og Seymour beviste, at for hver fast graf G , er der en polynomiel tidsalgoritme til at kontrollere, om den større graf G har en mindre. Løbetiden for denne algoritme er udtrykt ved et kubisk polynomium i størrelsen af den større graf (selvom der er en konstant faktor i dette polynomium, der afhænger superpolynomialt af størrelsen af G ), og denne tid blev forbedret til en kvadratisk af Kawarabayashi , Kobayashi og Reid [14] . For enhver familie F lukket i mol er der således en algoritme med polynomisk køretid, der kontrollerer, om grafen tilhører familien F - bare for alle forbudte mindreårige for F kontrollerer vi, om den givne graf indeholder denne forbudte mol [15] [16] [17] .
Men for at denne metode skal fungere, er det nødvendigt at have en blokerende finit mængde, og sætningen giver det ikke. Sætningen viser, at en sådan mængde findes, og hvis en sådan mængde er kendt, bliver problemet polynomium. I praksis kan algoritmen kun anvendes, når vi har et blokerende sæt. Som et resultat viser sætningen, at problemet kan løses i polynomiel tid, men giver ikke en specifik polynomiel tidsalgoritme. Et sådant bevis for polynomialitet er ikke-konstruktivt [18] [19] . I mange specifikke tilfælde kan kontrol af, at en graf tilhører en given familie, der er lukket i mindreårige, gøres mere effektivt. For eksempel kan planariteten af en graf kontrolleres i lineær tid.
Den samme metode kan anvendes på grafiske invarianter med den egenskab, at for enhver k er familien af grafer, for hvilke invarianten ikke overstiger k , mindre lukket. For eksempel, ifølge dette resultat, egner træbredde, grenbredde, stibredde, toppunktsdækning og minimum indlejringsslægt sig alle til denne tilgang, og for enhver fast k er der en polynomiel-tidsalgoritme til at kontrollere, at en given invariant ikke overstiger k , og eksponenten i algoritmens køretid afhænger ikke k . Problemer med polynomisk løsningstid for enhver fast k og en eksponent i køretid uafhængig af k er kendt som løselige problemer med faste parametre..
Denne metode giver dog ikke en direkte fast-parametrisk afgørbar algoritme til at beregne værdien af en parameter for en given graf med ukendt k på grund af vanskeligheden ved at finde sættet af forbudte mindreårige. Hertil kommer, at de resulterende enorme konstante faktorer gør algoritmen til ringe nytte i praksis. Udviklingen af eksplicitte algoritmer, der kan løses med faste parametre til disse problemer med forbedret afhængighed af k , forbliver således en vigtig forskningslinje.
Friedman, Robertson og Seymour [20] har vist, at følgende sætning demonstrerer uafhængighedsfænomenet , idet det ikke kan bevises i forskellige formelle systemer, der er stærkere end Peano-aritmetikken , men det kan bevises i systemer, der er væsentligt svagere end Zermelo-Fraenkels mængdeteori :
Sætning : For ethvert positivt heltal n er der et heltal m , således at hvis G 1 , …, G m er en sekvens af endelige urettede grafer, hvor hver graf G i højst har størrelse n + i , så G j ≤ G k for nogle j < k .(Her er størrelsen af en graf det samlede antal af dens hjørner, og ≤ betyder rækkefølge efter mindreårige.)