Descompunere modulară

Descompunerea modulară este descompunerea unui grafic în subseturi de vârfuri, numite module. Un modul este o generalizare a unei componente conexe a unui grafic. Spre deosebire de componentele de conectivitate, totuși, un modul poate fi propriul său subset al altuia. Prin urmare, modulele conduc la o descompunere recursivă (ierarhică) a graficului, nu doar la partiții.

Variante de descompunere modulară există pentru graficele nedirecționate și pentru graficele direcționate . Pentru fiecare grafic nedirecționat, o astfel de descompunere este unică.

Noțiunea poate fi generalizată la alte structuri (cum ar fi graficele direcționate) și este utilă pentru dezvoltarea algoritmilor eficienți pentru recunoașterea anumitor clase de grafice, pentru găsirea orientărilor tranzitive ale graficelor de comparabilitate , pentru probleme de optimizare pe grafice și pentru vizualizarea graficelor .

Module

Conceptul de modul a fost redescoperit în multe domenii. Pentru acest concept s-au folosit denumirile multimi autonome , multimi omogene , intervale si multimi fractionare . Aparent, cea mai veche mențiune și prima descriere a coeficientilor modulari și a împărțirii grafurilor care apar în acest caz a fost în lucrarea lui Galai din 1967.

Modulul grafic este o generalizare a componentei conectate . O componentă conectată are proprietatea că este un set de vârfuri astfel încât orice membru nu este vecin cu niciun vârf care nu este în . O generalizare va fi, este un modul atunci când, pentru fiecare vârf , fie orice membru nu este vecin , fie orice membru este vecin . $X$ $X$ $X$ $X$ $v\nu \in X$ $X$ $v$ $X$ $v$

În mod echivalent, este un modul dacă toți membrii au același set de vecini între vârfuri nu în . $X$ $X$ $X$

Spre deosebire de componentele conectate, modulele unui graf sunt aceleași cu modulele complementului său , iar modulele pot fi „imbricate” - un modul poate fi propriul subset al altuia. Rețineți că mulțimea de vârfuri a unui grafic este un modul, la fel ca seturile singleton și mulțimea goală . Ele sunt numite module triviale . Graficul poate avea sau nu alte module. Un grafic se numește simplu dacă toate modulele sale sunt triviale. $V$

În ciuda diferențelor, modulele păstrează proprietatea dorită a componentelor conectate, și anume că multe proprietăți ale subgrafului generate de o componentă conectată sunt independente de restul graficului. Un fenomen similar este observat pentru subgrafele generate de module. $G[X]$ $X$

Modulele grafice sunt deci de mare interes algoritmic. Un set de module imbricate, dintre care extinderea modulară este un exemplu, poate fi utilizat pentru a obține o soluție recursivă la multe probleme combinatorii de pe grafice, cum ar fi recunoașterea și găsirea orientării tranzitive a graficelor de comparabilitate , recunoașterea și găsirea reprezentării permutării graficelor de permutare. , recunoașterea dacă un grafic este un cograf , recunoașterea graficelor de interval și găsirea unei reprezentări de interval pentru acesta, definirea graficelor moștenite de distanță [1] și pentru vizualizarea graficului [2] . Ele joacă un rol important în demonstrarea teoremei grafului perfect [3] .

Pentru recunoașterea graficelor moștenite la distanță și a graficelor circulare , o generalizare suplimentară a descompunerii modulare, numită descompunere divizată [1] , este deosebit de utilă .

Pentru a evita ambiguitatea definiției de mai sus, oferim următoarea definiție formală a modulelor. . este un modul al unui grafic dacă: $G=(V,E)$ $M\subseteq V$ $G$

vârfurile nu pot fi distinse printr-un vârf în , adică fie adiacente ambelor , și c , fie nu adiacente ambelor , și . $M$ $V\backslash M$ $\forall u,v\in M,\forall x\in V\backslash M$ $X$ $u$ $v$ $X$ $u$ $v$
vârfurile au același set de vecini exteriori, adică . $M$ $\forall u,v\in M,N(u)\setminus M=N(v)\setminus M$

$\emptyset$ , și toate singleton -urile pentru sunt module și sunt numite module triviale . Un grafic este simplu dacă toate modulele sale sunt banale. Componentele de conectivitate ale unui graf sau complementele acestora sunt, de asemenea, module ale unui graf . $V$ $\{v\}$ $v\în V$ $G$ $G$

$M$ este un modul grafic puternic dacă nu se suprapune (parțial) cu niciun alt modul grafic - modulul grafic este fie , fie , sau . $G$ $G$ $\forall M'$ $G$ $M\cap M'=\emptyset$ $M\subseteq M'$ $M'\subseteq M$

Coeficienti si factori modulari

Dacă și sunt module disjunse, atunci este ușor de observat că fie orice membru este vecin al oricărui element al lui , fie niciun membru nu este adiacent vreunui membru al lui . Astfel, toate elementele a două module care nu se intersectează sunt fie adiacente , fie nu adiacente . Nu există o stare intermediară între aceste două extreme. $X$ $Y$ $X$ $Y$ $X$ $Y$

Având în vedere acest lucru, descompunerile modulare , în care fiecare clasă de descompunere este un modul, prezintă un interes deosebit. Să presupunem că este o descompunere modulară. Deoarece clasele de partiții nu se intersectează, adiacența lor formează un nou graf, graful coeficient , ale cărui vârfuri sunt termenii . Adică, fiecare vârf este un modul al graficului G, iar adiacența acestor module definește muchiile . $V$ $P$ $G/P$ $P$ $G/P$ $G/P$

În figura de mai jos, vârfurile 1, vârfurile 2 până la 4, vârfurile 5, vârfurile 6 și 7 și vârfurile 8 până la 11 sunt modulare. În diagrama din dreapta sus, muchiile dintre aceste mulțimi arată coeficientii dați de descompunerea dată, în timp ce muchiile din mulțimi arată factorii corespunzători.

Partiții și sunt partiții modulare banale . este un grafic cu un singur vârf, în timp ce . Să presupunem că este un modul non-trivial. Apoi , submulțimea unui element este, de asemenea, o partiție modulară non-trivială . Astfel, existența oricăror module non-triviale implică existența unor partiții de module non-triviale. În general, majoritatea sau toți membrii pot fi module non-triviale. $\{V\)$ $\{\{x\}|x\în V\}$ $G/\{V\}$ $G/\{\{x\}|x\in V\}=G$ $X$ $X$ $V\backslash X$ $V$ $P$

Dacă este o partiție modulară non-trivială, atunci este o reprezentare compactă a tuturor marginilor care se termină în diferite clase de partiții . Pentru fiecare clasă de partiție subgraf generată de se numește factor și oferă o reprezentare a tuturor marginilor cu ambele capete în . Astfel, muchiile unui grafic pot fi reconstruite dacă se cunosc graficul coeficientului și factorii săi. Termenul de graf simplu provine din faptul că un graf simplu are doar coeficienti și factori banali. $P$ $G/P$ $P$ $X$ $P$ $G[X]$ $X$ $X$ $G$ $G/P$

Dacă este un multiplicator al coeficientului modulo , se poate dovedi că poate fi factorizat recursiv și coeficienti. Fiecare nivel de recursivitate produce un coeficient. Ca caz de bază, graficul are un singur vârf. Graficul poate fi reconstruit prin reconstruirea factorilor de jos, inversând etapele de partiţionare prin asamblarea factorilor cu câte la fiecare nivel. $G[X]$ $G/P$ $G[X]$ $G$

În figura de mai jos, o astfel de descompunere recursivă este reprezentată ca un arbore, care reflectă una dintre modalitățile de a factoriza recursiv factorii de descompunere modulară inițială în partiții modulare mai mici.

Metoda de partiționare recursivă a unui grafic în factori și coeficienti poate să nu fie singura. (De exemplu, toate subseturile de vârfuri ale unui graf complet sunt module, ceea ce înseamnă că există multe moduri diferite de a descompune acel graf în mod recursiv.) Unele moduri de descompunere pot fi mai utile decât altele.

Modularizare

Din fericire, există o descompunere recursivă a unui grafic care reprezintă implicit toate modalitățile în care acesta poate fi descompus. Aceasta este modularizarea. Este în sine o modalitate de a descompune recursiv un grafic în câte, dar le include pe toate celelalte. Descompunerea prezentată în figura de mai jos este o descompunere specială a graficului dat.

Mai jos este o observație cheie pentru înțelegerea descompunerii modulare:

Dacă este un modul al graficului și este un submult al lui $X$ $G$ $Y$ $X$ , atunci este un modul dacă și numai dacă este un modul al lui . $Y$ $G$ $G[X]$

Gallai [4] a definit recursiv o descompunere modulară pe un graf cu multe vârfuri , după cum urmează: $V$

În cazul de bază, dacă are un singur vârf, descompunerea sa modulară este un arbore cu un singur nod. $G$
Gallai a arătat că dacă este conectat și la fel și complementul său, atunci modulele maxime, care sunt submulțimi proprii ale lui , sunt o partiție a lui . Prin urmare, sunt modulare. Coeficientii pe care ii definesc sunt simpli. Rădăcina arborelui este marcată ca un nod simplu , iar aceste module sunt acceptate de descendenții setului . Deoarece sunt maxime, orice modul nereprezentat în acest fel este conținut în descendentul lui . Pentru fiecare descendent al mulțimii, înlocuirea arborelui de modularizare cu un arbore de descompunere modulară oferă o reprezentare a tuturor modulelor graficului, conform observației cheie de mai sus. $G$ $V$ $V$ $V$ $X$ $V$ $X$ $V$ $X$ $G[X]$ $G$
Dacă nu este conectat, complementul său este conectat. Orice unire de componente conectate este un modul grafic . Toate celelalte module sunt subseturi ale unei componente de conectivitate separate. Aceasta reprezintă toate modulele, cu excepția subseturilor de componente de conectivitate. Pentru fiecare componentă, înlocuirea cu un arbore de descompunere modulară oferă o reprezentare a tuturor modulelor graficului conform observației cheie de mai sus. Rădăcina arborelui este marcată ca un nod paralel , dar este un copil al rădăcinii. Coeficientul definit de descendent este complementul grafului complet. $G$ $G$ $X$ $X$ $G[X]$ $G$ $X$
Dacă complementul graficului nu este conexat, graficul este conex. Subarborele care sunt copii ai sunt definiți simetric față de cazul în care graficul nu este conectat, deoarece modulele graficului sunt aceleași cu modulele complementului său. Rădăcina arborelui este etichetată ca un nod secvenţial , iar coeficientul definit de descendenţi este graficul complet. $G$ $G$ $V$ $G$

Arborele final are un singur set de vârfuri grafice sub formă de frunze, care sunt cazul de bază. Un set de vârfuri de graf este un modul dacă și numai dacă este un nod arborescent sau o uniune de descendenți ai unui nod în serie sau paralel. Acest lucru atribuie implicit toate expansiunile modulare în partea de sus . În acest sens, arborele de descompunere modulară „concentrează în sine” toate celelalte modalități de a descompune recursiv un grafic în unele parțiale. $G$ $Y$ $G$ $V$ $G$

Probleme algoritmice

Structura de date pentru reprezentarea unui arbore de descompunere modular trebuie să suporte operațiuni care iau un nod ca intrare și returnează setul de vârfuri ale graficului pe care le reprezintă nodul. Modul evident de a face acest lucru este de a atribui fiecărui nod o listă de vârfuri în graficul pe care îl reprezintă nodul. Dat un pointer către un nod, setul de vârfuri ale graficului pe care le reprezintă nodul poate fi recuperat în timp . Cu toate acestea, o astfel de structură va necesita memorie în cel mai rău caz . $G$ $k$ $G$ $G$ ${\mathcal {O}}(k)$ $\Theta (n^{2})$

Alternativa de memorie este obținută prin reprezentarea arborelui de descompunere modulară cu orice structură de date standard bazată pe arbore înrădăcinat și etichetând fiecare frunză cu vârful graficului pe care îl reprezintă. Setul reprezentat de nodul intern este definit de setul de etichete ale frunzelor sale descendente. Este bine cunoscut faptul că orice copac înrădăcinat cu frunze are cel mult noduri interne. Puteți utiliza căutarea în profunzime, începând de la pentru a obține etichete ale frunzelor descendente la timp . ${\mathcal {O}}(n)$ ${\mathcal {O}}(n)$ $G$ $v$ $k$ $k-1$ $v$ $v$ ${\mathcal {O}}(k)$

Fiecare nod este un set de vârfuri în grafic și, dacă este un nod intern, mulțimea de descendenți este o divizare , unde fiecare clasă divizată este un modul. Prin urmare, ele generează un coeficient în . Vârfurile acestui coeficient sunt elemente ale lui , deci pot fi reprezentate prin stabilirea muchiilor între copiii lui . Dacă și sunt doi termeni și , , atunci și sunt adiacente în dacă și numai dacă și sunt adiacente în cât. Pentru orice pereche de vârfuri de graf, aceasta este determinată de descendenții privați ai celui mai mare strămoș comun și în arborele de descompunere modulară. Prin urmare, o descompunere modulară etichetată ca coeficienti în acest fel oferă o reprezentare completă a graficului . $X$ $G$ $X$ $P$ $X$ $X$ $G[X]/P$ $G[X]$ $P$ $G[X]/P$ $X$ $Y$ $Z$ $P$ $u\în Y$ $v\in Z$ $u$ $v$ $G$ $Y$ $Z$ $\{u,v\)$ $G$ $\{u\)$ $\{v\}$ $G$

Multe probleme combinatorii pot fi rezolvate pe un grafic rezolvându-le separat pentru fiecare coeficient. De exemplu, este un grafic de comparabilitate dacă și numai dacă fiecare dintre acești coeficienti este un grafic de comparabilitate [4] [5] . Prin urmare, pentru a determina dacă un grafic este un grafic de comparabilitate, este suficient să verificați acest lucru pentru fiecare dintre câtetorii săi. De fapt, pentru a găsi orientarea tranzitivă a unui grafic de comparabilitate, este suficient să găsim orientarea tranzitivă a fiecăruia dintre coeficientii săi în descompunerea modulară [4] [5] . Un fenomen similar se găsește pentru graficele de permutare [6] , graficele de intervale [7] , graficele perfecte și alte clase de grafice. Unele probleme importante de optimizare combinatorie pe grafice pot fi rezolvate folosind strategii similare [8] . $G$ $G$

Cografele sunt grafice care au doar noduri paralele sau secvențiale în arborele lor de descompunere modulară.

Primul algoritm de timp polinomial pentru calcularea arborelui de descompunere modulară a unui graf a fost publicat în 1972 [9] , iar algoritmii de timp liniar sunt acum disponibili [6] [10] .

Generalizări

Descompunerea modulară a graficelor direcționate poate fi obținută în timp liniar [11] .

Cu câteva excepții simple, orice graf cu o descompunere modulară netrivială are și o partiție oblică [12] .

Note

↑ 12 Spinrad , 2003 .
↑ Papadopoulos, Voglis, 2005 .
↑ Golumbic, 1980 .
↑ 1 2 3 Gallai, 1967 , p. 25–66.
↑ 12 Möhring , 1985a , p. 41–101.
↑ 1 2 McConnell, Spinrad, 1999 , p. 189–241.
↑ Hsu, Ma, 1999 , p. 1004–1020.
↑ Möhring, 1985b , p. 195–225.
↑ James, Stanton, Cowan, 1972 , p. 281–290.
↑ Tedder, Corneil, Habib, Paul, 2008 , p. 634–645.
↑ McConnell, de Montgolfier, 2005 , p. 198–209.
↑ Reed, 2008 .

Literatură

Tibor Gallai. Transitiv orientierbare Graphen // Acta Mathematica Academiae Scientiarum Hungaricae. - 1967. - T. 18 . - doi : 10.1007/BF02020961 .
Lee O. James, Ralph G. Stanton, Donald D. Cowan. Descompunerea grafică pentru grafice nedirecţionate // Proc. A 3-a Conferință Internațională de Sud-Est despre Combinatorică, Teoria Graficelor și Calcul (Univ. Florida Atlantic, Boca Raton, Fla., 1972). - Universitatea Florida Atlantic , 1972.
Martin C. Golumbic. Teoria graficelor algoritmice și graficele perfecte. - Academic Press, 1980. - ISBN 0-444-51530-5 .
Hsu WL, Ma T. Algoritmi rapidi și simpli pentru recunoașterea graficelor de comparabilitate a acordurilor și a graficelor de intervale // SIAM Journal on Computing. - 1999. - T. 28 , nr. 3 . - doi : 10.1137/S0097539792224814 .
Ross M. McConnell, Fabien de Montgolfier. Descompunerea modulară în timp liniar a graficelor direcționate // Matematică aplicată discretă. - 2005. - T. 145 , nr. 2 . - doi : 10.1016/j.dam.2004.02.017 .
Ross M. McConnell, Jeremy P. Spinrad. Descompunere modulară și orientare tranzitivă // Matematică discretă . - 1999. - T. 201 . - doi : 10.1016/S0012-365X(98)00319-7 .
Rolf H. Möhring. Aspecte algoritmice ale graficelor de comparabilitate și ale graficelor de intervale // Grafice și ordine. — D. Reidel, 1985a.
Rolf H. Möhring. Aspecte algoritmice ale descompunerii substituției în optimizarea peste relații, sisteme de mulțimi și funcții booleene // Annals of Operations Research. — 1985b. - T. 4 . - doi : 10.1007/BF02022041 .
Charis Papadopoulos, Constantinos Voglis. Desenarea graficelor folosind descompunerea modulară // Proc. Al 13-lea Simpozion Internațional de Desen Grafic (GD'05) . - Springer-Verlag, 2005. - T. 3843. - (Lecture Notes in Computer Science). - doi : 10.1007/11618058_31 .
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.
Jeremy P Spinrad. Reprezentări grafice eficiente. - Societatea Americană de Matematică, 2003. - (Monografii de la Fields Institute). — ISBN 0-8218-2815-0 .
Marc Tedder, Derek Corneil, Michel Habib, Christophe Paul. Descompunere modulară în timp liniar mai simplă prin permutări recursive de factorizare // Proc. Al 35-lea Colocviu Internațional despre Automate, Limbaje și Programare (ICALP 2008) . - Springer-Verlag, 2008. - T. 5125. - (Lecture Notes in Computer Science). - doi : 10.1007/978-3-540-70575-8_52 .
Emad Zahedi, Jason Smith. Descompunerea modulară a graficelor și proprietatea de păstrare a distanței // Matematică aplicată discretă. - 2018. - Emisiune. 7 .

Link -uri

Implementarea Perl a algoritmului de descompunere modulară
Implementarea Java a algoritmului de descompunere modulară
Implementarea în Julia a algoritmului de descompunere modulară