Ferde válaszfal

A gráf ferde partíciója a csúcsainak két részhalmazra való felosztása szétválasztott generált részgráf és komplementer formájában ; fontos szerepet játszik a tökéletes gráfelméletben .

Definíció

A gráf ferde partíciója a gráf csúcsainak két és részhalmazra való felosztása, amelynél a generált részgráf szét van kapcsolva, a generált részgráf pedig egy szétkapcsolt gráf komplementere (a továbbiakban együtt kapcsolt) . Egy gráf ekvivalens ferde partíciója úgy írható le, mint a gráf csúcsainak négy részhalmazra , , és , amelyben nincsenek élek -tól -ig , de minden lehetséges él van -tól -ig . Egy ilyen partíciónál a generált részgráfok szétválasztottak és együtt vannak kapcsolva, így vehetjük és . $G$ $x$ $Y$ $G[X]$ $G[Y]$ $G$ $G$ $A$ $B$ $C$ $D$ $A$ $B$ $C$ $D$ $G[A\cup B]$ $G[C\cup D]$ $X=A\cup B$ $Y=C\cup D$

Példák

Minden négy vagy több csúcsot tartalmazó útvonalnak van egy ferde partíciója, amelyben az együtt leválasztott halmaz az útvonal egyik belső éle, a szétkapcsolt halmaz pedig ennek az élnek mindkét csúcsából áll. Azonban nem lehetséges, hogy bármilyen hosszúságú ciklusnak legyen ferde partíciója – függetlenül attól, hogy a ciklusok milyen részhalmazai vannak kiválasztva halmazként , a halmaz komplementerének ugyanannyi összekapcsolt komponense lesz, így lehetetlen felbontani és együtt kell lekapcsolni. $Y$ $x$ $x$ $Y$ $x$ $Y$

Ha a gráfnak van ferde partíciója, akkor van egy ilyen partíciója és annak komplementere . Például az útvonal-kiegészítőknek vannak ferde partíciói, de a ciklus-kiegészítőknek nincs.

Különleges alkalmak

Ha a gráf szétkapcsolt, akkor három egyszerű esetet (üres gráf, egy élű és három csúcsú gráf, vagy négy csúcson tökéletes illeszkedés ) leszámítva van egy ferde partíciója, amelyben a közösen szétkapcsolt oldal a partíció az egyik él végpontjaiból áll, a leválasztott oldal pedig az összes többi csúcsból. Ugyanebből az okból kifolyólag, ha egy gráf komplementere le van kötve, akkor a megfelelő három esetből álló halmaz kivételével ferde partícióval kell rendelkeznie [1] .

Ha a gráfnak van egy klikkelválasztója (olyan klikk , amelynek eltávolításakor a fennmaradó csúcsok szétkapcsolódnak), több mint egy csúcstal, akkor a partíció klikkdé és a többi csúcs egy ferde partíciót alkot. Az egy csúcsú klikkszakasz egy zsanér . Ha létezik ilyen csúcs, akkor néhány egyszerű kivételtől eltekintve létezik egy ferde partíció, amelyben az együtt leválasztott oldal ebből a csúcsból és annak egyik szomszédjából áll [1] .

A gráf csillagszakasza olyan csúcselválasztó , amelyben az egyik csúcs szomszédos az elválasztó összes többi csúcsával. Minden kattintáselválasztó egy csillag szakasz. Szükségszerűen egy csillagszakaszú (több csúcsú) gráfnak van egy ferde partíciója, amelyben az együtt szétkapcsolt részgráf a csillagszakasz csúcsaiból, a szétkapcsolt részgráf pedig az összes többi csúcsból áll [1] . $G$

A modul (vagy homogén halmaz) a gráf csúcsainak nem triviális részhalmaza , így bármely olyan csúcshoz, amely nem tartozik a -hoz , vagy szomszédos a -ben lévő összes csúcstal , vagy egyik sem. Ha a gráfnak van egy modulja , és azon kívül minden csúcs mellett vannak csúcsok, és rajta kívül más csúcsok nem szomszédosak egyik csúcsával sem -ból , akkor van egy csillagszaka, amely a modulban található egy csúcsból és a modulon kívüli szomszédaiból áll. Másrészt, ha van egy modul, amelyben e két részhalmaz közül az egyik üres, akkor a gráf szét van kapcsolva, vagy együtt le van kötve, és ismét (három egyszerű eset kivételével) van egy ferde szakasza [1] . $H$ $G$ $v$ $H$ $v$ $H$ $G$ $H$ $H$ $H$ $G$

Történelem

A ferde partíciókat Khvatal [2] vezette be a tökéletes gráfok kapcsán . Chvatal bebizonyította, hogy egy minimálisan tökéletlen gráfnak nem lehet csillagmetszete. Nyilvánvaló, hogy a szétkapcsolt gráfok nem lehetnek minimálisan tökéletlenek, és az is ismert volt, hogy a klikkelválasztókkal vagy modulokkal ellátott gráfok nem lehetnek minimálisan tökéletlenek [3] . Claudy Berge az 1960-as évek elején sejtette, hogy a tökéletes gráfoknak meg kell egyezniük a Berge-gráfokkal, amelyeknek nincs generált páratlan ciklusa (öt vagy több hosszúságú) vagy annak komplementere, és (mivel a ciklusoknak és komplementereiknek nincs ferde partíciója) nincs gráf. ez nem egy minimális Berge-gráfnak lehet ferde partíciója. Chvatal, akit érdekeltek ezek az eredmények, úgy sejtette, hogy egy minimálisan tökéletlen gráfnak sem lehet ferde partíciója. Egyes szerzők igazolták ennek a feltételezésnek speciális eseteit, de ez sokáig megfejtetlen maradt [4] .

A ferde partíciók különös jelentőséget kaptak, amikor Chudnovskaya, Robertson, Seymour és Thomas [5] használta őket annak az erős tökéletes gráftételnek a bizonyítására , hogy a Berge-gráfok megegyeznek a tökéletes gráfokkal. Chudnovskaya és csoportja nem tudta közvetlenül bizonyítani Khvatal sejtését, de gyengébb eredményt mutatott be, miszerint a tétel minimális ellenpéldájának (ha lenne) kiegyensúlyozott ferde partíciónak kell lennie, amelyben minden generált útvonalnak az egyik oldalon van a vége. a válaszfal és a belső csúcsok másik oldalán egyenletes hosszúságú. Ez az eredmény lett bizonyításuk kulcslemmája, Chvatala lemmájának teljes változata pedig az ő tételükből következik [6] .

A strukturális gráfelméletben

A ferde partíciók a tökéletes gráfok strukturális dekompozíciójának kulcsfontosságú összetevői, amelyet Chudnovskaya, Robertson, Seymour és Thomas [5] használt az erős tökéletes gráftétel bizonyítása részeként. Chudnovskaya és munkatársai kimutatták, hogy bármely tökéletes gráf vagy a tökéletes gráfok öt alapvető osztályába tartozik, vagy rendelkezik a négy egyszerűbb gráfokra való bontás egyikével, és az egyik ilyen dekompozíció a ferde dekompozíció.

A ferde partíciókat használó szerkezeti dekompozíció egyszerű példáját adta Seymour [6] . Észrevette, hogy minden összehasonlíthatósági gráf teljes vagy kétoldalú , vagy ferde partícióval rendelkezik. Valójában, ha egy részlegesen rendezett halmaz bármely eleme minimum elem vagy maximum elem, akkor a megfelelő összehasonlítási gráf kétrészes. Ha a rendezés kész , akkor a megfelelő összehasonlítási grafikon elkészült. Ha ezen esetek egyike sem következik be, de bármely olyan elem, amely nem minimális és nem maximális, összehasonlítható az összes többi elemmel, akkor vagy a minimális és nem minimális elemekre történő felosztás (ha több minimális elem van), vagy a felosztás a maximum és a nem maximum elemek (ha egynél több maximális elem van) alkotják a csillagszakaszt. A fennmaradó esetben van egy részleges rendű elem, amely sem nem minimális, sem nem maximális, és nem hasonlítható össze az összes többi elemmel. Ebben az esetben van egy ferde partíció (a csillagszakasz kiegészítése), amelyben az együtt leválasztott oldal hasonló elemekből áll (nem beleértve önmagát ), a leválasztott oldal pedig a fennmaradó elemekből áll. $x$ $x$ $x$

Az akkordgráfok még egyszerűbb, hasonló jellegű dekompozíciókkal rendelkeznek – vagy teljesek, vagy klikkelválasztójuk van. Hayward [7] hasonlóképpen kimutatta, hogy minden összefüggő és társkapcsolt gyenge akkordgráfnak (olyan gráfnak, amelynek generált ciklusa nagyobb, mint négy vagy annak komplementere), amely négy vagy több csúcsot tartalmaz, van egy csillagszakasz vagy annak komplementere, ahonnan Chvatala lemmája szerint. , ebből az következik, hogy minden ilyen gráf tökéletes.

Algoritmusok és összetettség

Egy adott gráf ferde partíciója, ha létezik, megtalálható polinomidőben . Ezt eredetileg Figueiredo, Klein, Kohayakawa és Reid mutatta [8] , de nagyon hosszú futási idővel , ahol a bemeneti gráf csúcsainak száma. Kennedy és Reid [9] -re javította a futási időt . Itt van az élek száma. $O(n^{101})$ $n$ $O(n^{4}m)$ $m$

Annak ellenőrzése, hogy egy gráf tartalmaz-e ferde partíciót, amelyben az együtt leválasztott oldal egyik része független, NP-teljes probléma [10] . Annak ellenőrzése, hogy egy adott gráf tartalmaz-e kiegyensúlyozott ferde partíciót, tetszőleges gráfok esetén is NP-teljes, de tökéletes gráfok esetén a probléma polinomiális időben is megoldható [11] .

Jegyzetek

↑ 1 2 3 4 Reed, 2008 .
↑ Chvatal, 1985 .
↑ Reed (2008 ). A modulok hiányát a minimális imperfektális gráfokban Lovas Lovász (1972 ) használta fel a gyenge tökéletes gráftétel bizonyítására .
↑ Lásd Cornuéjols, Reed (1993 ) arra az esetre, amikor a partíció együtt leválasztott oldala több részből áll, és Roussel, Rubio (2001 ) arról az esetről, amikor az együtt leválasztott oldal két része közül az egyik független.
↑ 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 .

Irodalom

Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. Az erős tökéletes gráf tétel // Annals of Mathematics . - 2006. - T. 164 , sz. 1 . – S. 51–229 . doi : 10.4007 / annals.2006.164.51 . - arXiv : math/0212070 .
Chvátal V. Csillagvágások és tökéletes gráfok // Journal of Combinatorial Theory . - 1985. - T. 39 , sz. 3 . – S. 189–199 . - doi : 10.1016/0095-8956(85)90049-8 .
Gerard Cornuejols, Bruce Reed. Teljes többrészes kivágások minimális tökéletlen gráfokban // Journal of Combinatorial Theory . - 1993. - T. 59 , sz. 2 . – S. 191–198 . - doi : 10.1006/jctb.1993.1065 .
Simone Dantas, Celina MH de Figueiredo, Sulamita Klein, Sylvain Gravier, Bruce Reed. Stabil ferde partíció probléma // Discrete Applied Mathematics. - 2004. - T. 143 , sz. 1-3 . – S. 17–22 . - doi : 10.1016/j.dam.2004.01.001 .
Celina MH de Figueiredo, Sulamita Klein, Yoshiharu Kohayakawa, Bruce Reed. Ferde partíciók hatékony keresése // Journal of Algorithms. - 2000. - T. 37 , sz. 2 . – S. 505–521 . - doi : 10.1006/jagm.1999.1122 .
Ryan B. Hayward. Gyengén háromszögezett gráfok // Journal of Combinatorial Theory . - 1985. - T. 39 , sz. 3 . — S. 200–208 . - doi : 10.1016/0095-8956(85)90050-4 .
William S. Kennedy, Bruce Reed. Gyors ferde partíció felismerés // Számítógépes geometria és gráfelmélet: Nemzetközi Konferencia, KyotoCGGT 2007, Kyoto, Japán, 2007. június 11–15., Revised Selected Papers. - Berlin: Springer, 2008. - T. 4535. - S. 101-107. — ( Számítástechnikai előadásjegyzetek ). - doi : 10.1007/978-3-540-89550-3_11 .
Lovasz László . Normál hipergráfok és a tökéletes gráf sejtés // Diszkrét matematika . - 1972. -2. évf . 3 . – S. 253–267 . - doi : 10.1016/0012-365X(72)90006-4 .
Bruce Reed. Partíciók ferdítése tökéletes gráfokban // Discrete Applied Mathematics. - 2008. - T. 156 , sz. 7 . - S. 1150-1156 . - doi : 10.1016/j.dam.2007.05.054 . Az eredetiből archiválva : 2015. szeptember 19.
Roussel F., Rubio P. A ferde partíciókról minimális tökéletlen gráfokban // Journal of Combinatorial Theory . - 2001. - T. 83 , sz. 2 . – S. 171–190 . - doi : 10.1006/jctb.2001.2044 .
Paul Seymour. Hogyan találták meg az erős tökéletes gráf-sejtés bizonyítékát // Gazette des Mathématiciens. - 2006. - Kiadás. 109 . — 69–83 .
Nicholas Trotignon. Berge-gráfok felbontása és kiegyensúlyozott ferde partíciók detektálása // Journal of Combinatorial Theory . - 2008. - T. 98 , sz. 1 . – S. 173–225 . - doi : 10.1016/j.jctb.2007.07.004 . .