Diagram mindre - Graph minor

I grafteorin kallas en oriktad graf H för minor av grafen G om H kan bildas från G genom att radera kanter och hörn och genom att dra ihop kanter .

Teorin om grafiska minderåriga började med Wagners sats om att en graf är plan om och endast om dess minderåriga varken innehåller den fullständiga grafen K ₅ eller den fullständiga tvåpartsdiagrammet K _3,3 . Den Robertson-Seymour teoremet innebär att en analog förbjuden mindre karakterisering existerar för varje egenskap av grafer som konserverade med strykningar och kant sammandragningar. För varje fast graf H är det möjligt att testa om H är en minor av ett inmatningsgraf G i polynomtid ; tillsammans med den förbjudna mindre karaktäriseringen innebär detta att varje grafegenskap som bevaras genom raderingar och sammandragningar kan kännas igen på polynomtid.

Andra resultat och gissningar som involverar grafmindre inkluderar grafstruktursatsen , enligt vilken graferna som inte har H som minor kan bildas genom att limma ihop enklare bitar, och Hadwigers gissning om oförmågan att färga en graf till förekomsten av en stor komplett graf som en mindre av den. Viktiga varianter av grafgrafer inkluderar de topologiska minderåriga och nedsänkande minderåriga.

Definitioner

En kantkontraktion är en operation som tar bort en kant från ett diagram samtidigt som de två hörnen som den använde för att ansluta slogs samman. En oriktad graf H är en minor av en annan oriktad graf G om en graf isomorf till H kan erhållas från G genom att dra ihop några kanter, radera några kanter och radera några isolerade hörn. Den ordning i vilken en sekvens av sådana sammandragningar och deletioner utförs på G påverkar inte den resulterande grafen H .

Mindreåriga grafer studeras ofta i det mer allmänna sammanhanget hos minderåriga . I detta sammanhang är det vanligt att anta att alla grafer är anslutna, med självslingor och flera kanter tillåtna (det vill säga att de är multigrafer snarare än enkla grafer); sammandragning av en slinga och radering av en spets är förbjudna operationer. Denna synvinkel har fördelen att kantborttagningar lämnar grafens rang oförändrad och kantkontraktioner minskar alltid rankningen med en.

I andra sammanhang (till exempel med studier av pseudoforests ) är det mer meningsfullt att tillåta borttagning av ett snitt, och att tillåta bortkopplade grafer, men att förbjuda multigraf. I denna variant av grafmindre teori förenklas alltid en graf efter eventuell kantkontraktion för att eliminera dess självslingor och flera kanter.

En funktion f kallas "minor-monoton" om, när H är en minor av G , man har f (H) ≤ f (G).

Exempel

I följande exempel är graf H en minor av graf G :

H.

G.

Följande diagram illustrerar detta. Konstruera först en delgraf av G genom att radera de streckade kanterna (och den resulterande isolerade hörnpunkten) och dra sedan ihop den grå kanten (slå samman de två hörnen som den ansluter):

Stora resultat och gissningar

Det är enkelt att kontrollera att grafen mindre förhållande bildar en partiell ordning på isomorfism klasser av ändliga oriktade grafer: det är transitiv (en mindre av en mindre av G är en mindre av G själv), och G och H kan bara vara minderåriga av varandra om de är isomorfa eftersom alla icke -små operationer tar bort kanter eller hörn. Ett djupt resultat av Neil Robertson och Paul Seymour säger att denna delordning faktiskt är en väl kvasi-ordning : om en oändlig lista G ₁ , G ₂ , ... av ändliga grafer ges, så finns det alltid två index i < j sådan att G _i är en minor av G _j . Ett annat likvärdigt sätt att ange detta är att varje uppsättning grafer endast kan ha ett begränsat antal minimala element under den mindre ordningen. Detta resultat bevisade en gissning som tidigare kallades Wagners gissning, efter Klaus Wagner ; Wagner hade gissat det länge tidigare, men publicerade det först 1970.

Under bevisningen bevisar Seymour och Robertson också grafstruktursatsen där de för varje fast graf H bestämmer den grova strukturen för en graf som inte har H som minor. Satsens uttalande är i sig självt långt och involverat, men i korthet fastslår det att en sådan graf måste ha strukturen av en klicksumma av mindre grafer som modifieras på små sätt från grafer inbäddade på ytor av begränsat släkte . Således etablerar deras teori grundläggande kopplingar mellan mindreåriga grafer och topologiska inbäddningar av grafer.

För varje graf H måste de enkla H -mindre fria graferna vara glesa , vilket innebär att antalet kanter är mindre än någon konstant multipel av antalet hörn. Närmare bestämt, om H har h hörn, kan en enkel n -vertex enkel H -mindre graf ha högst kanter, och vissa K _h -mindre fria grafer har åtminstone så många kanter. Således, om H har h hörn, så har H -mindre fria grafer genomsnittlig grad och dessutom degenerering . Dessutom har de H -mindre fria graferna en separatorsats som liknar den plana separatorns sats för plana grafer: för alla fasta H och alla n -vertex H -mindre graf G är det möjligt att hitta en delmängd av hörn vars borttagning delar G i två (möjligen frånkopplade) undergrafer med högst 2 n /3 hörn per delgraf. Ännu starkare, för alla fasta H , har H -mindre grafer trebredd . ${\ displaystyle \ scriptstyle O (nh {\ sqrt {\ log h}})}$${\ displaystyle \ scriptstyle O (h {\ sqrt {\ log h}})}$ ${\ displaystyle \ scriptstyle O (h {\ sqrt {\ log h}})}$${\ displaystyle \ scriptstyle O ({\ sqrt {n}})}$ ${\ displaystyle \ scriptstyle O ({\ sqrt {n}})}$

Den Hadwiger gissningar i grafteori föreslår att om en graf G inte innehåller en mindre isomorphic till hela grafen på k hörn, då G har en ordentlig färg med k  - 1 färger. Fallet k  = 5 är en omformulering av satsen med fyra färger . Hadwiger -antagandet har bevisats för k  ≤ 6, men är okänt i det allmänna fallet. Bollobás, Catlin & Erdős (1980) kallar det "ett av de djupaste olösta problemen inom grafteorin." Ett annat resultat som relaterar fyrafärgsatsen till grafiska minderåriga är snark-satsen som tillkännagavs av Robertson, Sanders, Seymour och Thomas, en förstärkning av fyrfärgs satsen som gissas av WT Tutte och anger att varje brolös 3-regelbunden graf som kräver fyra färger i en kantfärgning måste ha Petersen -grafen som minor.

Mindre slutna graffamiljer

Många familjer av grafer har egenskapen att varje minor av en graf i F också är i F ; en sådan klass sägs vara mindre stängd . Till exempel, i alla plana diagram eller inbäddning av en graf på en fast topologisk yta , kan varken borttagning av kanter eller sammandragning av kanter öka inbäddningens släkt ; därför bildar plana grafer och graferna som är inbäddbara på en fast yta mindre stängda familjer.

Om F är en mindre stängd familj finns det (på grund av den välkvasiordande egenskapen hos minderåriga) bland graferna som inte tillhör F en begränsad uppsättning X av mindre-minimala grafer. Diagrammen är förbjudna minderåriga för F : en graf tillhör F om och endast om det inte innehåller som en mindre varje kurva i X . Det vill säga att varje mindre stängd familj F kan karakteriseras som familjen av X- mindre-fria grafer för några ändliga uppsättningar X av förbjudna minderåriga. Det mest kända exemplet på en karakterisering av denna typ är Wagner teorem karakterisera de plana grafer som graferna som har varken K ₅ eller K _3,3 som minderåriga.

I vissa fall kan egenskaperna hos graferna i en mindre sluten familj ha nära samband med egenskaperna hos deras uteslutna minderåriga. Till exempel har en mindre stängd graffamilj F begränsat vägbredd om och endast om dess förbjudna minderåriga inkluderar en skog , F har begränsat trädjupet om och endast om dess förbjudna minderåriga inkluderar en oenig förening av bandiagram , F har begränsat trädbredd om och bara om dess förbjudna minderåriga inkluderar ett plant diagram , och F har begränsat lokal trädbredd (ett funktionellt samband mellan diameter och trädbredd) om och bara om dess förbjudna minderåriga inkluderar en toppgraf (en graf som kan göras plan genom att en enda tas bort vertex). Om H kan ritas i planet med en enda korsning (det vill säga det har korsning nummer ett) så har de H- mindre fria graferna en förenklad struktursats där de bildas som klick-summor av plana grafer och grafer av begränsad trädbredd. Till exempel har både K ₅ och K _3,3 korsning nummer ett, och som Wagner visade är K ₅ -fria graferna exakt 3-klicksummor av plana grafer och åtta-toppunkt Wagner-grafen , medan K _{3, 3-} fria grafer är exakt 2-klicksummor av plana grafer och  K ₅ .

Variationer

Topologiska minderåriga

En graf H kallas en topologisk moll av en graf G , om en underavdelning av H är isomorf till en subgraf av G . Det är lätt att se att varje topologisk minor också är en minor. Det motsatta är emellertid inte sant i allmänhet (till exempel är den fullständiga grafen K ₅ i Petersen -grafen en mindre men inte en topologisk), men gäller för grafen med maximal grad som inte är större än tre.

Det topologiska mindre sambandet är inte en välkvasi-ordning på uppsättningen av ändliga grafer och därför gäller resultatet av Robertson och Seymour inte för topologiska minderåriga. Det är emellertid enkelt att konstruera ändliga förbjudna topologiska mindre karakteriseringar från ändliga förbjudna mindre karakteriseringar genom att ersätta varje grenuppsättning med k utgående kanter med varje träd på k blad som har nedgrader minst två.

Framkallade minderåriga

En graf H kallas en inducerad minor av en graf G om den kan erhållas från en inducerad subgraf av G genom att dra ihop kanter. Annars sägs G vara H -inducerad minorfri.

Nedsänkning

En grafoperation som kallas lyft är central i ett koncept som kallas nedsänkning . Den lyftning är en operation på angränsande kanter. Med tanke på tre hörn v , u och w , där (v, u) och (u, w) är kanter i grafen, är lyftet av vuw eller motsvarande (v, u), (u, w) operationen som raderar de två kanterna (v, u) och (u, w) och lägger till kanten (v, w) . I det fall där (v, w) redan var närvarande, kommer v och w nu att anslutas med mer än en kant, och därför är denna operation i sig en flergrafsoperation.

I det fall där en graf H kan erhållas från en graf G genom en sekvens av lyft (på G ) och sedan hitta en isomorf delgraf, säger vi att H är en nedsänkning moll av G . Det finns ännu ett sätt att definiera nedsänkta minderåriga, vilket motsvarar lyftningen. Vi säger att H är en nedsänkningsminne av G om det finns en injektiv mappning från hörn i H till hörn i G där bilderna av intilliggande element av H är anslutna i G med kantavvikande banor.

Den nedsänkningsmässiga relationen är en välkvasi-ordning på uppsättningen av ändliga grafer och följaktligen gäller resultatet av Robertson och Seymour för nedsänkning av minderåriga. Detta innebär vidare att varje nedsänkt minor-sluten familj kännetecknas av en begränsad familj av förbjudna nedsänkta minderåriga.

I grafritning uppstår nedsänkningsminor som planiseringarna av icke-plana grafer : från en ritning av en graf i planet, med korsningar, kan man bilda en nedsänkningsminne genom att ersätta varje korsningspunkt med en ny toppunkt, och i processen också dela upp varje korsad kant i en bana. Detta gör att ritmetoder för plana grafer kan utökas till icke-plana grafer.

Grunt minderåriga

En grund minor på en graf G är en minor där kanterna på G som dragits ihop för att bilda minor bildar en samling av osammanhängande undergrafer med låg diameter . Grunt minderåriga interpolerar mellan teorierna om grafiska minderåriga och subgrafer, i det att grunda minderåriga med högt djup sammanfaller med den vanliga typen av grafmindre, medan de grunda minderåriga med djup noll är exakt undergraferna. De tillåter också att teorin om grafiska minderåriga kan utökas till klasser av grafer, till exempel de 1-plana graferna som inte stängs under att ta minderåriga.

Paritetsvillkor

En alternativ och likvärdig definition av en grafmoll är att H är en minor av G när hörnen på H kan representeras av en samling av vertex-disjoint subtrees av G , så att om två hörn är intilliggande i H finns det en kant med dess endpoints i de motsvarande två träd i G . En udda minor begränsar denna definition genom att lägga till paritetsvillkor till dessa subtrees. Om H är representerad av en samling av underträd av G som ovan, då H är en udda mindre av G närhelst det är möjligt att tilldela två färger till hörnen i G på ett sådant sätt att varje kant av G inom ett underträd är korrekt färgat (dess slutpunkter har olika färger) och varje kant på G som representerar en närhet mellan två subtrees är monokromatisk (båda dess slutpunkter har samma färg). Till skillnad från för den vanliga sorten av grafmindre är grafer med förbjudna udda minderåriga inte nödvändigtvis glesa. Den Hadwiger hypotes , att k -chromatic grafer innehåller med nödvändighet k -vertex komplett graf som minderåriga, har även studerats ur synvinkel av udda minderåriga.

En annan paritetsbaserad förlängning av begreppet grafgrafer är begreppet en tvåpartsminne , som producerar en tvåpartig graf när startdiagrammet är tvåpartigt. En graf H är en bipartit -minor av en annan graf G när H kan erhållas från G genom att radera hörn, radera kanter och kollapsa par hörn som är på avstånd två från varandra längs en perifer cykel av grafen. En form av Wagners sats gäller för tvåpartsmindreåriga: En tvåpartig graf G är en plan graf om och bara om den inte har bruksdiagrammet K _3,3 som tvåpartsmoll.

Algoritmer

Problemet med att avgöra om en graf G innehåller H som minor är NP-komplett i allmänhet; till exempel, om H är en cykeldiagram med samma antal hörn som G , då är H en minor av G om och endast om G innehåller en Hamiltonisk cykel . När G är en del av ingången men H är fixerad kan den dock lösas på polynomtid. Mer specifikt är drifttiden för att testa om H är en minor av G i detta fall O ( n ³ ), där n är antalet hörn i G och den stora O -notationen döljer en konstant som är superexponentiellt beroende av H ; sedan det ursprungliga Graph Minors -resultatet har denna algoritm förbättrats till O ( n ² ) -tid. Genom att tillämpa den polynomiska tidsalgoritmen för att testa om en given graf innehåller någon av de förbjudna minderåriga är det teoretiskt möjligt att känna igen medlemmarna i en mindre stängd familj under polynomtid . Detta resultat används inte i praktiken eftersom den dolda konstanten är så enorm (behöver tre lager av Knuths uppåtpilen för att uttrycka) att utesluta alla applikationer, vilket gör det till en galaktisk algoritm . För att kunna tillämpa detta resultat konstruktivt är det dessutom nödvändigt att veta vad de förbjudna minderåriga i graffamiljen är. I vissa fall är de förbjudna minderåriga kända eller kan beräknas.

I fallet där H är en fast plan kurva , då kan vi testa i linjär tid i en inmatnings graf G huruvida H är en mindre av G . I de fall H inte är fixerat är snabbare algoritmer kända i det fall där G är plan.

Anteckningar

Referenser

externa länkar

• Weisstein, Eric W. "Graph Minor" . MathWorld .