Wagners sats - Wagner's theorem
I grafteori , är Wagner teorem är en matematisk förbjudet graf karakterisering av plana grafer , uppkallad efter Klaus Wagner , som anger att en ändlig graf är plan om och endast om dess minderåriga inkluderar varken K 5 (den fullständiga grafen på fem hörn ) eller K 3, 3 ( verktygsdiagrammet , en komplett bipartitgraf på sex hörn). Detta var ett av de tidigaste resultaten i teorin om mindreåriga och kan ses som en föregångare för satsen Robertson – Seymour .
Definitioner och uttalande
En plan inbäddning av en given graf är en ritning av diagrammet i det euklidiska planet , med punkter för sina hörn och kurvor för dess kanter , på ett sådant sätt att de enda skärningarna mellan kanter är vid en gemensam slutpunkt för de två kanterna. . En mindre av en given graf är en annan graf som bildas genom att radera hörn, ta bort kanter och kontraherande kanter. När en kant dras samman slås de två slutpunkterna samman för att bilda ett enda toppunkt. I vissa versioner av grafmorsteorin förenklas grafen till följd av en sammandragning genom att ta bort självslingor och flera adjacenser, medan i andra versioner multigrafer är tillåtna, men denna variation gör ingen skillnad för Wagners sats. Wagners sats säger att varje graf har antingen en plan inbäddning, eller en mindre av en av två typer, den fullständiga grafen K 5 eller den fullständiga bipartitgrafen K 3,3 . (Det är också möjligt för en enda graf att ha båda typerna av mindre.)
Om en given graf är plan, så är alla dess minderåriga: radering av vertex och kant bevarar uppenbarligen planaritet, och kantkontraktion kan också göras på ett planeringsbevarande sätt genom att lämna en av de två slutpunkterna på den kontraherade kanten på plats och dirigera alla kanter som inträffade i den andra ändpunkten längs den kontraherade kanten. En mindre-minimal icke-plan graf är en graf som inte är plan, men där alla rätta minderåriga (minderåriga bildade av minst en radering eller sammandragning) är plana. Ett annat sätt att ange Wagners sats är att det bara finns två mindre-minimala icke-plana grafer, K 5 och K 3,3 .
Ett annat resultat, även kallat Wagners teorem, säger att en fyra-ansluten graf är plan om och bara om den inte har någon K 5- minor. Det vill säga, genom att anta en högre anslutningsnivå kan grafen K 3,3 göras onödig i karakteriseringen och lämnar bara en enda förbjuden minor, K 5 . På motsvarande sätt antar Kelmans-Seymour-antagandet att en 5-ansluten graf är plan om och bara om den inte har K 5 som en topologisk minor .
Historia och förhållande till Kuratowskis teorem
Wagner publicerade båda satserna 1937, efter 1930-publiceringen av Kuratowskis sats , enligt vilken en graf är plan om och bara om den inte innehåller en underavdelning av en av samma två förbjudna grafer K 5 och K 3, 3 . På sätt och vis är Kuratowskis sats starkare än Wagners sats: en underavdelning kan omvandlas till en mindre av samma typ genom att dra samman alla utom en kant i varje väg som bildas av underindelningsprocessen, men omvandla en mindre till en underavdelning av samma typ är inte alltid möjligt. I fallet med de två graferna K 5 och K 3,3 är det enkelt att bevisa att en graf som har minst en av dessa två grafer som mindre också har minst en av dem som en indelning, så två satser är likvärdiga.
Implikationer
En konsekvens av den starkare versionen av Wagners sats för fyra anslutna grafer är att karakterisera graferna som inte har en K 5- minor. Satsen kan omformuleras så att den säger att varje sådan graf är antingen plan eller att den kan sönderdelas i enklare bitar. Med hjälp av denna idé, de K 5 kan -minor fria grafer karakteriseras som graferna som kan bildas som kombinationer av plana grafer och åtta-vertex Wagner graf , limmade samman av klick-sum operationer. Till exempel, K 3,3 kan bildas på detta sätt som en klick-summan av tre plana grafer, som var och en är en kopia av det tetraedriska grafen K 4 .
Wagner teorem är en viktig prekursor till teorin om graf minderåriga, som kulminerade i bevisen för två djupa och långtgående resultat: den grafstruktur theorem (en generalisering av wagner s clique summa nedbrytning av K 5 -minor fria grafer) och den Robertson-Seymour sats (en generalisering av den förbjudna mindre karakteriseringen av plana grafer, som anger att varje graf familj stängd under drift av tar minderåriga har en karakterisering av ett ändligt antal förbjudna minderåriga). Analoger av Wagners sats kan också utvidgas till teorin om matroider : i synnerhet visas samma två diagram K 5 och K 3,3 (tillsammans med tre andra förbjudna konfigurationer) i en karaktärisering av grafiska matroider av förbjudna matroida minderåriga .