Skrå skillevæg

En skæv partition af en graf er en opdeling af dens hjørner i to delmængder i form af en frakoblet genereret subgraf og komplement ; spiller en vigtig rolle i perfekt grafteori .

Definition

En skæv partition af en graf er en opdeling af grafens hjørner i to undersæt og , for hvilken den genererede undergraf er afbrudt, og den genererede undergraf er komplementet til en afbrudt graf (herefter benævnt "samforbundet"). . En tilsvarende skæv partition af en graf kan beskrives som en opdeling af grafens hjørner i fire delmængder , og , hvor der ikke er kanter fra til , men der er alle mulige kanter fra til . For en sådan partition er de genererede undergrafer henholdsvis frakoblet og co-forbundne, så vi kan tage og . $G$ $x$ $Y$ $G[X]$ $G[Y]$ $G$ $G$ $EN$ $B$ $C$ $D$ $EN$ $B$ $C$ $D$ $G[A\kop B]$ $G[C\cup D]$ $X=A\kop B$ $Y=C\cup D$

Eksempler

Enhver sti med fire eller flere hjørner har en skæv partition, hvor det med-frakoblede sæt er en af stiens indre kanter, og det afbrudte sæt består af begge hjørner af denne kant. Det er dog ikke muligt for cyklusser af enhver længde at have en skæv partition - uanset hvilke delmængder af cykler der vælges som sættet , vil sættets komplement have det samme antal forbundne komponenter, så det er umuligt at nedbryde og være samfrakoblet. $Y$ $x$ $x$ $Y$ $x$ $Y$

Hvis grafen har en skæv partition, har en sådan partition og dens komplement . For eksempel har stikomplementer skæve partitioner, men cykluskomplementer har ikke.

Særlige lejligheder

Hvis grafen er afbrudt, så har den, bortset fra tre simple tilfælde (en tom graf, en graf med en kant og tre hjørner, eller en perfekt matchning på fire spidser), en skæv partition, hvor den med-frakoblede side af skillevæggen består af endepunkterne på den ene kant, og den afbrudte side består af alle andre hjørner. Af samme grund, hvis komplementet af en graf er afbrudt, skal den, bortset fra det tilsvarende sæt af tre tilfælde, have en skæv partition [1] .

Hvis grafen har en klikseparator (en klike , hvis fjernelse gør de resterende toppunkter afbrudt) med mere end ét toppunkt, danner partitionen i en klike og de resterende hjørner en skæv partition. En kliksektion med et toppunkt er et hængsel . Hvis der eksisterer et sådant toppunkt, så eksisterer der med nogle få enkle undtagelser en skæv partition, hvor den medkoblede side består af dette toppunkt og en af dets naboer [1] .

Et stjerneudsnit i en graf er en toppunktseparator , hvor et af hjørnerne støder op til alle andre hjørner af separatoren. Enhver klikseparator er en stjernesektion. Nødvendigvis har en graf med et stjerneudsnit (med mere end et toppunkt) en skæv partition, hvor den medkoblede undergraf består af stjernesektionens hjørner, og den afbrudte undergraf består af alle de resterende hjørner [1] . $G$

Et modul (eller homogent sæt) er en ikke-triviel delmængde af toppunkterne i grafen , sådan at for ethvert toppunkt, der ikke hører til , enten støder op til alle hjørner i , eller ingen af dem. Hvis grafen har et modul og udenfor det er der hjørner ved siden af alle toppunkter og andre toppunkter udenfor den støder ikke op til nogen top fra , så har den et stjerneudsnit bestående af et toppunkt i modulet sammen med dets naboer uden for modulet. På den anden side, hvis der er et modul, hvor en af disse to delmængder er tom, så er grafen afbrudt eller co-frakoblet, og igen (undtagen i tre simple tilfælde) har den en skæv sektion [1] . $H$ $G$ $v$ $H$ $v$ $H$ $G$ $H$ $H$ $H$ $G$

Historie

Skæve partitioner blev introduceret af Khvatal [2] i forbindelse med perfekte grafer . Chvatal beviste, at en minimalt uperfekt graf ikke kan have et stjerneudsnit. Det er klart, at afbrudte grafer ikke kan være minimalt uperfekte, og det var også kendt, at grafer med klikseparatorer eller moduler ikke kan være minimalt uperfekte [3] . Claudy Berge formodede i begyndelsen af 1960'erne, at perfekte grafer skal være det samme som Berge-grafer, grafer uden en genereret ulige cyklus (af længden fem eller mere) eller dens komplement, og (fordi cyklusser og deres komplementer ikke har skæve partitioner) ingen graf det er ikke en minimal Berge-graf kan have en skæv partition. Interesseret i disse resultater formodede Chvatal, at ingen minimalt uperfekt graf kan have en skæv partition. Nogle forfattere har bevist særlige tilfælde af denne formodning, men den har været uafklaret i lang tid [4] .

Skæve partitioner fik særlig betydning, da de blev brugt af Chudnovskaya, Robertson, Seymour og Thomas [5] til at bevise den stærke perfekte grafsætning om, at Berge-grafer er det samme som perfekte grafer. Chudnovskaya og hendes gruppe var ikke i stand til at bevise Khvatals formodning direkte, men viste et svagere resultat, at det minimale modeksempel til sætningen (hvis der var et) skulle have en balanceret skæv partition, hvor hver genereret sti med en ende på den ene side af skillevæggen og indvendige hjørner på den anden side har en jævn længde. Dette resultat blev nøglelemmaet i deres bevis, og den fulde version af Chvatalas lemma følger af deres teorem [6] .

I strukturel grafteori

Skæve partitioner udgør en nøglekomponent i den strukturelle nedbrydning af perfekte grafer, som blev brugt af Chudnovskaya, Robertson, Seymour og Thomas [5] som en del af beviset for den stærke perfekte grafsætning. Chudnovskaya et al viste, at enhver perfekt graf enten tilhører fem grundlæggende klasser af perfekte grafer eller har en af fire typer af nedbrydning til enklere grafer, og en af disse nedbrydninger er en skæv dekomponering.

Et simpelt eksempel på strukturel nedbrydning ved brug af skæve skillevægge blev givet af Seymour [6] . Han bemærkede, at enhver sammenlignelighedsgraf er komplet eller todelt eller har en skæv partition. Faktisk, hvis et element i et delvist ordnet sæt enten er et minimumselement eller et maksimumelement, så er den tilsvarende sammenlignelighedsgraf todelt. Hvis bestillingen er fuldført , er den tilsvarende sammenlignelighedsgraf komplet. Hvis ingen af disse tilfælde finder sted, men ethvert element, der hverken er minimalt eller maksimalt, er sammenligneligt med alle andre elementer, så enten partitionen i minimale og ikke-minimale elementer (hvis der er mere end et minimalt element), eller partitionen i de maksimale og ikke-maksimale elementer (hvis der er mere end et maksimumelement) danner stjerneafsnittet. I det resterende tilfælde er der et element af delvis orden, som hverken er minimalt eller maksimalt og ikke er sammenligneligt med alle andre elementer. I dette tilfælde er der en skæv skillevæg (komplement til stjernesektionen), hvor den med-frakoblede side består af elementer, der kan sammenlignes med (ikke inklusive sig selv ), og den afbrudte side består af de resterende elementer. $x$ $x$ $x$

Akkordgrafer har endnu enklere nedbrydninger af lignende art - de er enten komplette eller har en klikseparator. Hayward [7] viste på samme måde, at enhver forbundet og co-forbundet svag akkordgraf (en graf med en genereret cyklus af længde større end fire eller dens komplement) med fire eller flere hjørner har en stjernesektion eller dens komplement, hvorfra, ifølge Chvatalas lemma , følger det, at enhver sådan graf er perfekt.

Algoritmer og kompleksitet

En skæv partition af en given graf, hvis den findes, kan findes i polynomisk tid . Dette blev oprindeligt vist af Figueiredo, Klein, Kohayakawa og Reid [8] , men med en meget lang køretid , hvor er antallet af hjørner i inputgrafen. Kennedy og Reid [9] forbedrede køretiden til . Her er antallet af kanter. $O(n^{101})$ $n$ $O(n^{4}m)$ $m$

Problemet med at kontrollere, om en graf indeholder en skæv partition, hvor en af delene af den co-frakoblede side er uafhængig, er et NP-komplet problem [10] . At kontrollere om en given graf indeholder en balanceret skæv partition er også NP-komplet for vilkårlige grafer, men problemet kan løses i polynomisk tid for perfekte grafer [11] .

Noter

↑ 1 2 3 4 Reed, 2008 .
↑ Chvatal, 1985 .
↑ Reed (2008 ). Den manglende eksistens af moduler i minimal uperfekte grafer blev brugt af Lovas Lovász (1972 ) i hans bevis på den svage perfekte grafsætning .
↑ Se Cornuéjols, Reed (1993 ) for det tilfælde, hvor den med-frakoblede side af skillevæggen består af flere dele, og Roussel, Rubio (2001 ) for det tilfælde, hvor en af de to dele af den med-frakoblede side er uafhængig.
↑ 1 2 Chudnovsky, Robertson, Seymour, Thomas, 2006 .
↑ 12 Seymour , 2006 .
↑ Hayward, 1985 .
↑ de Figueiredo, Klein, Kohayakawa, Reed, 2000 .
↑ Kennedy, Reed, 2008 .
↑ Dantas, de Figueiredo, Klein, Gravier, Reed, 2004 .
↑ Trotignon, 2008 .

Litteratur

Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. The strong perfect graph theorem // Annals of Mathematics . - 2006. - T. 164 , no. 1 . — S. 51–229 . doi : 10.4007 / annals.2006.164.51 . - arXiv : math/0212070 .
Chvátal V. Stjernesnit og perfekte grafer // Journal of Combinatorial Theory . - 1985. - T. 39 , no. 3 . — S. 189–199 . - doi : 10.1016/0095-8956(85)90049-8 .
Gerard Cornuejols, Bruce Reed. Komplet multi-partite cutsets i minimale uperfekte grafer // Journal of Combinatorial Theory . - 1993. - T. 59 , no. 2 . — S. 191–198 . - doi : 10.1006/jctb.1993.1065 .
Simone Dantas, Celina MH de Figueiredo, Sulamita Klein, Sylvain Gravier, Bruce Reed. Stabil skæv partitionsproblem // Diskret anvendt matematik. - 2004. - T. 143 , no. 1-3 . — S. 17–22 . - doi : 10.1016/j.dam.2004.01.001 .
Celina MH de Figueiredo, Sulamita Klein, Yoshiharu Kohayakawa, Bruce Reed. Find skæve partitioner effektivt // Journal of Algorithms. - 2000. - T. 37 , no. 2 . — S. 505–521 . - doi : 10.1006/jagm.1999.1122 .
Ryan B. Hayward. Svagt triangulerede grafer // Journal of Combinatorial Theory . - 1985. - T. 39 , no. 3 . — S. 200–208 . - doi : 10.1016/0095-8956(85)90050-4 .
William S. Kennedy, Bruce Reed. Hurtig skæv partitionsgenkendelse // Computational Geometry and Graph Theory: International Conference, KyotoCGGT 2007, Kyoto, Japan, 11.-15. juni 2007, Revised Selected Papers. - Berlin: Springer, 2008. - T. 4535. - S. 101-107. — ( Forelæsningsnotater i Datalogi ). - doi : 10.1007/978-3-540-89550-3_11 .
Laszlo Lovasz . Normale hypergrafer og den perfekte grafformodning // Diskret matematik . - 1972. - Vol. 2 , nr. 3 . — S. 253–267 . - doi : 10.1016/0012-365X(72)90006-4 .
Bruce Reed. Skæv partitioner i perfekte grafer // Diskret anvendt matematik. - 2008. - T. 156 , no. 7 . - S. 1150-1156 . - doi : 10.1016/j.dam.2007.05.054 . Arkiveret fra originalen den 19. september 2015.
Roussel F., Rubio P. Om skæve partitioner i minimale uperfekte grafer // Journal of Combinatorial Theory . - 2001. - T. 83 , no. 2 . — S. 171–190 . - doi : 10.1006/jctb.2001.2044 .
Paul Seymour. Hvordan beviset for den stærke perfekte grafformodning blev fundet // Gazette des Mathématiciens. - 2006. - Udgave. 109 . — s. 69–83 .
Nicholas Trotignon. Nedbrydning af Berge-grafer og detektering af balancerede skæve partitioner // Journal of Combinatorial Theory . - 2008. - T. 98 , no. 1 . — S. 173–225 . - doi : 10.1016/j.jctb.2007.07.004 . .