Robertson-Seymours teorem (även kallad graph minor theorem [1] ) säger att vilken familj av grafer som helst som stängs under kantborttagning och kontraktionsoperationer kan definieras av en ändlig uppsättning förbjudna grafer .
Till exempel stängs uppsättningen av plana grafer under operationerna att ta bort och dra ihop kanter; de förbjudna graferna i detta fall är den fullständiga grafen K 5 och den fullständiga tvådelade grafen K 3,3 . Det sista påståendet kallas Wagner-satsen och är nära besläktad med Pontryagin-Kuratovsky-satsen .
Teoremet är allmänt känt för sin elementära formulering i avsaknad av ett enkelt bevis. Hon går under namnet Neil Robertson.och Paul Seymour , som bevisade det i en serie av tjugo artiklar på totalt 500 sidor publicerade från 1983 till 2004 [2] [3] [4] . Innan beviset var påståendet om satsen känt som Wagner-förmodan , även om Wagner själv hävdade att han aldrig angav denna gissning [5] .
Ett svagare påstående för träd följer av Kruskals trädsats. Uttalandet gjordes i form av en hypotes 1937 av den ungerske matematikern Andrew Vazonyioch bevisades 1960 oberoende av Joseph Kruskaloch S. Tarkovsky [6] [7] .
En moll av en oriktad graf G är vilken graf som helst som kan erhållas från G genom en (eventuellt tom) sekvens av kantkontraktion och avlägsnande av kanter och hörn av G . Minoritetsrelationen bildar en partiell ordning på mängden av alla distinkta finita oriktade grafer, eftersom denna relation uppfyller tre partiella ordningens axiom - relationen är reflexiv (vilken graf som helst är en moll i sig själv), transitiv (en moll i en graf G är sig själv ). en moll av en graf G ), och antisymmetrisk (om två grafer G och H är mindre av varandra måste de vara isomorfa ). Men om graferna är isomorfa kan de fortfarande betraktas som olika objekt, då bildar ordningen efter minor en förordning , en relation som är reflexiv och transitiv, men inte nödvändigtvis antisymmetrisk [1] .
En förordning sägs bilda en fullständigt kvasiordnad relation, om den inte heller innehåller en oändligt minskande kedja, inte heller en oändlig antikedja [8] . Till exempel är det vanliga förhållandet mellan icke-negativa heltal helt kvasi-ordnat, men samma ordning på mängden av alla heltal kommer inte att vara sådan, eftersom den innehåller en oändligt fallande kedja 0, −1, −2, −3...
Robertson-Seymour-satsen säger att ändliga oriktade grafer och grafiska mindre (som en relation) är helt kvasi-ordnade. Uppenbarligen innehåller minoritetsrelationen ingen oändlig nedåtgående kedja, eftersom varje sammandragning eller borttagning minskar antalet kanter eller hörn på grafen (icke-negativa heltal) [9] . Den icke-triviala delen av satsen är att det inte finns några oändliga antikedjor, det vill säga oändliga uppsättningar av grafer som inte är relaterade till varandra genom en minoritetsrelation. Om S är en uppsättning grafer och M är en delmängd av S som innehåller en representativ graf för varje ekvivalensklass av minimala element (grafer som hör till S men vilken som helst egen underordnad av dem inte tillhör S ), så bildar M en antikedja. Således är det ekvivalenta påståendet i satsen att för varje oändlig uppsättning S av grafer måste det bara finnas ett ändligt antal icke-isomorfa minimala element.
En annan likvärdig formulering av satsen säger att i varje oändlig uppsättning S av grafer måste det finnas ett par grafer, varav en är en moll av den andra [9] . Påståendet att varje oändlig mängd har ett ändligt antal minimala element innebär detta sista påstående, eftersom alla återstående (icke-minimala) grafer bildar ett sådant par. Åt andra hållet följer av denna formulering av satsen att det inte kan finnas oändliga antikedjor, eftersom en oändlig antikedja inte innehåller element som är förbundna med en minoritetsrelation.
En familj F av grafer sägs vara sluten under operationen att ta en mindre om någon mindre av en graf i F också tillhör F . Om F är en minor-sluten familj, låt S vara den uppsättning grafer som inte hör till F ( komplementet av mängden F ). Enligt Robertson-Seymour-satsen finns det en ändlig mängd H av minimala element i S . Dessa minimala element bildar en förbjuden grafkarakterisering av mängden F — grafer från F är exakt de grafer som inte har någon graf från H som moll [10] [11] . Medlemmarna i mängden H kallas ogiltiga minderåriga (eller förbjudna minderåriga ) för familjen F , och själva uppsättningen H kallas en obstruerande uppsättning.
Till exempel stängs plana grafer genom att en moll bildas - att dra ihop en kant i en plan graf eller ta bort en kant eller vertex kan inte förstöra planariteten. Plana grafer har alltså en karaktärisering av förbjudna moll, som i detta fall definieras av Wagners teorem - uppsättningen H av mindre minimala icke-planära grafer innehåller exakt två grafer, en komplett graf K 5 och en fullständig tvådelad graf K 3,3 . Plana grafer är exakt de grafer som inte har element från mängden { K 5 , K 3,3 } som mindre.
Förekomsten av karaktäriseringar av förbjudna minderåriga för alla mindre slutna familjer av grafer är en likvärdig formulering av Robertson-Seymours sats. Antag att vilken som helst mindre sluten familj F har en finit uppsättning H av minimala förbjudna minderåriga, och låt S vara vilken oändlig uppsättning grafer som helst. Vi definierar F för S som en familj av grafer som inte har minor i S . Då är mängden F moll sluten och har en finit mängd H av minimala förbjudna minderåriga. Låt C vara komplementet till F . S är en delmängd av C eftersom S och F inte skär varandra. Uppsättningen H innehåller minimala grafer från C . Ta en graf G från H . G kan inte ha riktiga minderåriga i S eftersom G är minimal i C. Samtidigt måste G ha en moll i S , för annars skulle G vara ett element i F. G är alltså ett element av S , vilket betyder att H är en delmängd av S och alla andra grafer från S har molor från grafuppsättningen H , så H är en finit uppsättning av minimala element av S.
Anta å andra sidan att varje uppsättning grafer har en ändlig delmängd av minimala grafer och låt F vara en mindre sluten uppsättning . Vi vill hitta en uppsättning H med grafer så att grafen ingår i F om och endast om den inte har några biämnen i H . Låt E vara uppsättningen av grafer som inte är mindre till någon graf från F , och låt H vara en ändlig uppsättning av minimala element från E . Låt nu en godtycklig graf G ges . Låt G tillhöra F . G kan inte ha minderåriga från H eftersom G tillhör F och H är en delmängd av E . Låt nu G inte tillhöra F . Då är G inte en moll av någon graf i F eftersom F är stängd i moll. G tillhör alltså E , så G har en moll i H.
Följande uppsättningar av finita grafer är stängda i moll, och har därför (enligt Robertson-Seymour-satsen) en karaktärisering av förbjudna grafer:
Några exempel på ändliga obstruktiva mängder var redan kända för vissa klasser redan innan beviset för Robertson-Seymour-satsen. Till exempel är hindret för alla skogar en slinga (eller, om vi begränsar oss till enkla grafer , en cykel med tre hörn). Det betyder att en graf är en skog om och endast om ingen av dess mindre är en slinga (eller en cykel med tre hörn). Det enda hindret för en uppsättning stigar är ett träd med fyra hörn, varav en har grad 3. I dessa fall består hindret av ett enda element, men i allmänhet kan det finnas fler element. Wagners teorem säger att en graf är plan om och endast om den varken innehåller K 5 eller K 3,3 som moll. Med andra ord, mängden { K 5 , K 3,3 } är obstruktionsuppsättningen för alla plana grafer, och den är den minsta obstruktionsuppsättningen. En liknande sats säger att K 4 och K 2,3 är förbjudna minorer för uppsättningen av ytterplanära grafer.
Även om Robertson-Seymour-satsen utvidgar dessa resultat till godtyckliga mindre slutna graffamiljer, ersätter den inte dessa resultat eftersom den inte uttryckligen beskriver obstruktionsuppsättningen för någon familj. Till exempel indikerar satsen att uppsättningen toroidformade grafer har en ändlig obstruktionsuppsättning, men ger ingen sådan uppsättning. Den kompletta uppsättningen av förbjudna minderåriga för toroidformade grafer är fortfarande okänd och innehåller minst 16 000 grafer [13] .
Robertson–Seymour-satsen har en viktig konsekvens inom beräkningskomplexitetsteorin, eftersom Robertson och Seymour bevisade att för varje fast graf G finns det en polynomtidsalgoritm för att kontrollera om den större grafen G har en moll. Löptiden för denna algoritm uttrycks av ett kubiskt polynom i storleken på den större grafen (även om det finns en konstant faktor i detta polynom som beror superpolynomiellt på storleken på G ), och denna tid förbättrades till en kvadratisk av Kawarabayashi , Kobayashi och Reid [14] . För varje familj F som är stängd i minors finns det en algoritm med polynom körtid som kontrollerar om grafen tillhör familjen F - bara för alla förbjudna minderåriga för F kontrollerar vi om den givna grafen innehåller denna förbjudna minor [15] [16] [17] .
Men för att denna metod ska fungera är det nödvändigt att ha en hindrande finit mängd, och satsen ger det inte. Satsen visar att en sådan mängd finns, och om en sådan mängd är känd blir problemet polynom. I praktiken kan algoritmen endast tillämpas när vi har en blockerande uppsättning. Som ett resultat visar satsen att problemet kan lösas i polynomtid, men ger ingen specifik polynomtidsalgoritm. Sådant bevis på polynomitet är icke-konstruktivt [18] [19] . I många specifika fall kan kontroll av att en graf tillhör en given familj som är stängd för minderåriga göras mer effektivt. Till exempel kan planariteten för en graf kontrolleras i linjär tid.
Samma metod kan tillämpas på grafinvarianter med egenskapen att, för varje k , är familjen av grafer för vilka invarianten inte överstiger k minor sluten. Till exempel, enligt detta resultat, lämpar sig trädbredd, grenbredd, vägbredd, vertextäckning och minsta häckande genus alla för detta tillvägagångssätt, och för varje fast k finns det en polynom-tidsalgoritm för att kontrollera att en given invariant inte överskrider k , och exponenten i algoritmens gångtid beror inte k . Problem med polynomlösningstid för valfri fix k och en exponent i gångtid oberoende av k är kända som lösbara problem med fasta parametrar..
Denna metod tillhandahåller dock inte en direkt fast parametriskt avgörbar algoritm för att beräkna värdet av en parameter för en given graf med okänt k på grund av svårigheten att hitta uppsättningen förbjudna minderåriga. Dessutom gör de resulterande enorma konstanta faktorerna algoritmen till liten nytta i praktiken. Utvecklingen av explicita lösbara algoritmer med fasta parametrar för dessa problem med förbättrat beroende av k förblir således en viktig forskningslinje.
Friedman, Robertson och Seymour [20] har visat att följande sats visar att fenomenet oberoende är obevisbart i olika formella system starkare än Peano-arithmetik , men det är bevisbart i system som är väsentligt svagare än Zermelo-Fraenkels mängdteorin :
Sats : För varje positivt heltal n finns det ett heltal m så att om G 1 , …, G m är en sekvens av ändliga oriktade grafer, där varje graf Gi har storlek som mest n + i , då G j ≤ G k för vissa j < k .(Här är storleken på en graf det totala antalet av dess hörn, och ≤ betyder ordning efter minderåriga.)