Despărțire oblică

O partiție oblică a unui graf este o partiție a vârfurilor acestuia în două submulțimi sub forma unui subgraf generat deconectat și a unui complement ; joacă un rol important în teoria grafurilor perfecte .

Definiție

O partiție oblică a unui graf este o partiție a vârfurilor grafului în două subseturi și , pentru care subgraful generat este deconectat, iar subgraful generat este complementul unui graf deconectat (denumit în continuare „co-conectat”) . O partiție oblică echivalentă a unui graf poate fi descrisă ca o partiție a vârfurilor grafului în patru submulțimi , și , în care nu există muchii de la până la , dar există toate muchiile posibile de la până la . Pentru o astfel de partiție, subgrafele generate sunt atât deconectate, cât și, respectiv, coconectate, deci putem lua și . $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$

Exemple

Orice cale cu patru sau mai multe vârfuri are o partiție oblică, în care mulțimea co-deconectată este una dintre muchiile interne ale căii, iar mulțimea deconectată este formată din ambele vârfuri ale acestei muchii. Cu toate acestea, nu este posibil ca ciclurile de orice lungime să aibă o partiție oblică - indiferent de subseturile de cicluri alese ca mulțime , complementul setului va avea același număr de componente conectate, deci este imposibil să se descompună și fi co-deconectat. $Y$ $X$ $X$ $Y$ $X$ $Y$

Dacă graficul are o partiție oblică, are o astfel de partiție și complementul său . De exemplu, complementele de cale au partiții oblice, dar complementele de ciclu nu.

Ocazii speciale

Dacă graficul este deconectat, atunci, cu excepția a trei cazuri simple (un grafic gol, un grafic cu o muchie și trei vârfuri, sau o potrivire perfectă pe patru vârfuri), are o partiție oblică, în care latura co-deconectată a partiția este formată din punctele de capăt ale unei muchii, iar partea deconectată este formată din toate celelalte vârfuri. Din același motiv, dacă complementul unui graf este deconectat, atunci, cu excepția setului corespunzător de trei cazuri, acesta trebuie să aibă o partiție oblică [1] .

Dacă graficul are un separator de clică (o clică a cărei îndepărtare face ca vârfurile rămase să fie deconectate) cu mai mult de un vârf, partiția într-o clică și vârfurile rămase formează o partiție oblică. O secțiune de clică cu un vârf este o balama . Dacă un astfel de vârf există, atunci, cu câteva excepții simple, există o partiție oblică în care latura co-deconectată este formată din acest vârf și unul dintre vecinii săi [1] .

O secțiune stea dintr-un grafic este un separator de vârfuri în care unul dintre vârfuri este adiacent tuturor celorlalte vârfuri ale separatorului. Orice separator de clicuri este o secțiune stea. Neapărat, un graf cu o secțiune stea (cu mai mult de un vârf) are o partiție oblică, în care subgraful co-deconectat este format din vârfurile secțiunii stea, iar subgraful deconectat este format din toate vârfurile rămase [1] . $G$

Un modul (sau o mulțime omogenă) este o submulțime non-trivială a vârfurilor graficului , astfel încât, pentru orice vârf care nu aparține lui , fie este adiacent tuturor vârfurilor din , fie niciunul dintre ele. Dacă graficul are un modul și în afara lui există vârfuri adiacente tuturor vârfurilor și alte vârfuri din afara lui nu sunt adiacente niciunui vârf din , atunci are o secțiune stea constând dintr-un vârf în modul împreună cu vecinii săi din afara modulului. Pe de altă parte, dacă există un modul în care unul dintre aceste două submulțimi este gol, atunci graficul este deconectat sau co-deconectat și din nou (cu excepția a trei cazuri simple) are o secțiune oblică [1] . $H$ $G$ $v$ $H$ $v$ $H$ $G$ $H$ $H$ $H$ $G$

Istorie

Partițiile oblice au fost introduse de Khvatal [2] în legătură cu graficele perfecte . Chvatal a demonstrat că un grafic minim imperfect nu poate avea o secțiune de stea. Este clar că grafurile deconectate nu pot fi minim imperfecte și, de asemenea, se știa că grafurile cu separatoare sau module de clică nu pot fi minim imperfecte [3] . Claudy Berge a presupus la începutul anilor 1960 că graficele perfecte trebuie să fie aceleași cu graficele Berge, grafice fără un ciclu impar generat (cu lungimea de cinci sau mai mult) sau complementul acestuia și (deoarece ciclurile și complementele lor nu au partiții oblice) niciun grafic. care nu este un grafic Berge minim poate avea o partiție oblică. Interesat de aceste rezultate, Chvatal a presupus că niciun grafic minim imperfect nu poate avea o partiție oblică. Unii autori au dovedit cazuri speciale ale acestei presupuneri, dar ea a rămas mult timp nerezolvată [4] .

Partițiile oblice au câștigat o importanță deosebită atunci când au fost folosite de Chudnovskaya, Robertson, Seymour și Thomas [5] pentru a demonstra teorema puternică a grafului perfect conform căreia grafurile Berge sunt la fel cu grafurile perfecte. Chudnovskaya și grupul ei nu au putut să demonstreze în mod direct conjectura lui Khvatal, dar au dovedit un rezultat mai slab, că contraexemplul minim al teoremei (dacă ar exista unul) ar trebui să aibă o partiție oblică echilibrată în care fiecare cale generată cu un capăt pe o parte. a despărțitorului și a vârfurilor interioare de pe cealaltă parte are o lungime uniformă. Acest rezultat a devenit lema cheie în demonstrația lor, iar versiunea completă a lemei lui Chvatala rezultă din teorema lor [6] .

În teoria grafurilor structurale

Partițiile oblice formează o componentă cheie a descompunerii structurale a grafurilor perfecte, care a fost folosită de Chudnovskaya, Robertson, Seymour și Thomas [5] ca parte a demonstrației teoremei grafului perfect puternic. Chudnovskaya și colab. au arătat că orice grafic perfect fie aparține la cinci clase de bază de grafice perfecte, fie are unul dintre cele patru tipuri de descompunere în grafice mai simple, iar una dintre aceste descompunere este o descompunere oblică.

Un exemplu simplu de descompunere structurală folosind partiții oblice a fost dat de Seymour [6] . El a observat că orice grafic de comparabilitate este complet sau bipartit sau are o partiție oblică. Într-adevăr, dacă orice element dintr-o mulțime parțial ordonată este fie un element minim, fie un element maxim, atunci graficul de comparabilitate corespunzător este bipartit. Dacă comanda este completă , atunci graficul de comparabilitate corespunzător este complet. Dacă niciunul dintre aceste cazuri nu are loc, dar orice element care nu este nici minim, nici maxim este comparabil cu toate celelalte elemente, atunci fie împărțirea în elemente minime și non-minimale (dacă există mai mult de un element minim), fie împărțirea în elementele maxime și nemaximale (dacă există mai mult de un element maxim) formează secțiunea stelară. În cazul rămas, există un element de ordine parțială care nu este nici minim, nici maxim și nu este comparabil cu toate celelalte elemente. În acest caz, există o despărțire oblică (complement al secțiunii stea) în care partea co-deconectată este formată din elemente comparabile cu (fără includere ), iar partea deconectată este formată din elementele rămase. $X$ $X$ $X$

Graficele cordale au descompoziții și mai simple de un fel similar - sunt fie complete, fie au un separator de clică. Hayward [7] a arătat în mod similar că orice graf cordal slab conectat și co-conectat (un grafic cu un ciclu generat de lungime mai mare de patru sau complementul său) cu patru sau mai multe vârfuri are o secțiune stea sau complementul său, de unde, prin lema lui Chvatala. , rezultă că orice astfel de grafic este perfect.

Algoritmi și complexitate

O partiție oblică a unui grafic dat, dacă există, poate fi găsită în timp polinomial . Acest lucru a fost arătat inițial de Figueiredo, Klein, Kohayakawa și Reid [8] , dar cu un timp de rulare foarte lung , unde este numărul de vârfuri din graficul de intrare. Kennedy și Reid [9] au îmbunătățit timpul de rulare la . Iată numărul de margini. $O(n^{101})$ $n$ $O(n^{4}m)$ $m$

Problema verificării dacă un grafic conține o partiție oblică în care una dintre părțile părții co-deconectate este independentă este o problemă NP-completă [10] . Verificarea dacă un graf dat conține o partiție oblică echilibrată este, de asemenea, NP-complet pentru grafurile arbitrare, dar problema poate fi rezolvată în timp polinomial pentru grafurile perfecte [11] .

Note

↑ 1 2 3 4 Reed, 2008 .
↑ Chvatal, 1985 .
↑ Reed (2008 ). Inexistența modulelor în grafurile minimal imperfect a fost folosită de Lovas Lovász (1972 ) în demonstrarea teoremei grafului perfect slab .
↑ Vezi Cornuéjols, Reed (1993 ) pentru cazul în care partea co-deconectată a partiției este formată din mai multe părți și Roussel, Rubio (2001 ) pentru cazul în care una dintre cele două părți ale co-deconectate este independent.
↑ 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 .

Literatură

Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. Teorema grafului perfect puternic // Analele matematicii . - 2006. - T. 164 , nr. 1 . — S. 51–229 . doi : 10.4007 / anals.2006.164.51 . - arXiv : math/0212070 .
Chvátal V. Star-cutsets and perfect graphs // Journal of Combinatorial Theory . - 1985. - T. 39 , nr. 3 . — S. 189–199 . - doi : 10.1016/0095-8956(85)90049-8 .
Gerard Cornuejols, Bruce Reed. Seturi complete cu mai multe partite în grafice minime imperfecte // Journal of Combinatorial Theory . - 1993. - T. 59 , nr. 2 . — S. 191–198 . - doi : 10.1006/jctb.1993.1065 .
Simone Dantas, Celina MH de Figueiredo, Sulamita Klein, Sylvain Gravier, Bruce Reed. Problemă de partiție oblică stabilă // Matematică aplicată discretă. - 2004. - T. 143 , nr. 1-3 . — S. 17–22 . - doi : 10.1016/j.dam.2004.01.001 .
Celina MH de Figueiredo, Sulamita Klein, Yoshiharu Kohayakawa, Bruce Reed. Găsirea eficientă a partițiilor oblice // Journal of Algorithms. - 2000. - T. 37 , nr. 2 . — S. 505–521 . - doi : 10.1006/jagm.1999.1122 .
Ryan B. Hayward. Grafice slab triangulate // Journal of Combinatorial Theory . - 1985. - T. 39 , nr. 3 . — S. 200–208 . - doi : 10.1016/0095-8956(85)90050-4 .
William S. Kennedy, Bruce Reed. Recunoaștere rapidă a partițiilor declinate // Computational Geometry and Graph Theory: International Conference, KyotoCGGT 2007, Kyoto, Japan, June 11–15, 2007, Revised Selected Papers. - Berlin: Springer, 2008. - T. 4535. - S. 101-107. — ( Note de curs în Informatică ). - doi : 10.1007/978-3-540-89550-3_11 .
Laszlo Lovasz . Hipergrafele normale și conjectura grafică perfectă // Matematică discretă . - 1972. - Vol. 2 , nr. 3 . — S. 253–267 . - doi : 10.1016/0012-365X(72)90006-4 .
Bruce Reed. Schimbați partiții în grafice perfecte // Matematică aplicată discretă. - 2008. - T. 156 , nr. 7 . - S. 1150-1156 . - doi : 10.1016/j.dam.2007.05.054 . Arhivat din original pe 19 septembrie 2015.
Roussel F., Rubio P. Despre skew partitions in minimal imperfect graphs // Journal of Combinatorial Theory . - 2001. - T. 83 , nr. 2 . — S. 171–190 . - doi : 10.1006/jctb.2001.2044 .
Paul Seymour. Cum a fost găsită dovada conjecturei puternice a grafului perfect // Gazette des Mathématiciens. - 2006. - Emisiune. 109 . — p. 69–83 .
Nicolae Trotignon. Descompunerea graficelor Berge și detectarea partițiilor oblice echilibrate // Journal of Combinatorial Theory . - 2008. - T. 98 , nr. 1 . — S. 173–225 . - doi : 10.1016/j.jctb.2007.07.004 . .