Componentă conexă

În teoria grafurilor, o componentă conexă (uneori denumită simplu componentă) a unui graf neorientat este un subgraf indus în care oricare două noduri sunt legate între ele prin drumuri, și care nu este legată la niciun nod suplimentar din restul grafului. De exemplu, graful prezentat în ilustrație are trei componente conexe. Un nod fără muchii incidente este el însuși o componentă. Un graf conex are exact o componentă conexă, constând din întregul graf.

O relație de echivalență

O modalitate alternativă de definire a componentelor conexe implică clasele de echivalență ale unei relații de echivalență care este definită pe nodurile grafului. Într-un graf neorientat, un nod v este accesibil de la un nod u dacă există un drum de la u la v. În această definiție, un singur nod este numărat ca un drum de lungime zero și același nod poate apărea de mai multe ori într-un drum. Accesibilitatea este o relație de echivalență, deoarece:

Este reflexivă^⁠(d): există un drum trivial de lungime zero de la orice nod la el însuși.
Este simetrică^⁠(d): dacă există un drum de la u la v, aceleași muchii formează un drum de la v la u.
Este tranzitivă^⁠(d): dacă există drum de la u la v și drum de la v la w, cele două drumuri pot fi concatenate pentru a forma un drum de la u la w.

Ca urmare, componentele conexe sunt subgrafuri induse formate de clasele de echivalență^⁠(d) ale acestei relații.

Numărul de componente conexe

Numărul de componente conexe este o importantă invariantă topologică^⁠(d) a unui graf. În teoria topologică a grafurilor^⁠(d), acesta poate fi interpretată ca numărul Betti^⁠(d) 0 al grafului. În teoria algebrică a grafurilor, este egal cu multiplicitatea lui 0 ca valoare proprie a matricei laplaciene^⁠(d) a grafului. Este, de asemenea, indicele primului coeficient diferit de zero al polinomului cromatic^⁠(d) al unui graf. Numărul de componente conexe joacă un rol cheie în teorema Tutte^⁠(d) care caracterizează grafurile care au potriviri perfecte^⁠(d) și în definirea durității grafului^⁠(d).

Algoritmi

Calculul numărului de componente conexe ale unui graf este trivial în timp liniar (în raport cu numărul de noduri și de muchii ale grafului) folosind fie căutarea în lățime, fie căutarea în adâncime. În ambele cazuri, o căutare care începe la un anumit nod v va găsi întreaga componentă care conține v (și nu și altele) înainte de a reveni. Pentru a găsi toate componentele unui graf, se parcurg nodurile acestuia, pornind mai întâi o nouă căutare în lățime sau în adâncime, ori de câte ori bucla ajunge la un nod care nu a fost deja inclus într-o componentă conexă găsită anterior. Hopcroft & Tarjan (1973) descriu în esență acest algoritm și afirmă că la acel moment era „bine cunoscut”.

Există și algoritmi eficienți pentru a urmări dinamic componentele conexe ale unui graf pe măsură ce se adaugă noduri și muchii, ca o aplicare simplă a structurilor de date cu mulțimi disjuncte^⁠(d). Acești algoritmi necesită un timp amortizat^⁠(d) O( α ( n ) ) per operație, unde adăugarea de noduri și muchii și determinarea componentei în care se încadrează un nod sunt operații, iar α ( n ) este o inversă cu creștere foarte lentă a funcției Ackermann^⁠(d), care crește foarte repede. O problemă asociată este urmărirea componentelor conexe, pe măsură ce toate muchiile sunt șterse dintr-un graf, una câte una; există un algoritm pentru a rezolva acest lucru cu timp constant per interogare și timp $O(| V || E |)$ pentru a menține structura de date; acesta este un cost amortizat de $O(| V |)$ pe fiecare ștergere de muchie. Pentru păduri, costul poate fi redus la $O(q + | V | log | V |)$ sau $O(log | V |)$ cost amortizat per ștergere de muchie (Shiloach & Even 1981).

Cercetătorii au studiat și unii algoritmi pentru găsirea componentelor conexe în modele mai limitate de calcul, cum ar fi programe în care memoria de lucru este limitată la un număr logaritmic de biți (definit de clasa de complexitate L). Lewis & Papadimitriou (1982) s-au întrebat dacă este posibil să se testeze în logspace dacă două noduri aparțin aceleiași componente conexe a unui graf neorientat și au definit o clasă de complexitate SL^⁠(d) a problemelor logspace-echivalente cu conexitatea grafurilor. În cele din urmă Reingold (2008) a reușit să găsească un algoritm pentru rezolvarea acestei probleme de conexitate în logspace, demonstrând că L = SL.

Componente conexe în grafuri aleatorii

În grafurile aleatorii, dimensiunile componentelor conexe sunt date de o variabilă aleatoare, care, la rândul ei, depinde de modelul specific.

Modelul $G(n,p)$ are trei regiuni cu comportament aparent diferit:

Subcritic $np<1$: Toate componentele conexe sunt simple și foarte mici, cea mai mare componentă are dimensiunea $|C_{1}|=O(\log n)$ ;

Critic $np=1$: $|C_{1}|=O(n^{2/3})$ ;

Supercritic $np>1$: $|C_{1}|\approx yn$ unde $y=y(np)$ este soluția pozitivă a ecuației $e^{-pny}=1-y.$

unde $C_{1}$ și $C_{2}$ sunt, primele două componente conexe ca mărime. Toate celelalte componente au dimensiunile de ordinul $O(\log n).$

Bibliografie

Hopcroft, J.; Tarjan, R. (1973), „Algorithm 447: efficient algorithms for graph manipulation”, Communications of the ACM^⁠(d), 16 (6), pp. 372–378, doi:10.1145/362248.362272
Lewis, Harry R.; Papadimitriou, Christos H. (1982), „Symmetric space-bounded computation”, Theoretical Computer Science^⁠(d), 19 (2), pp. 161–187, doi:10.1016/0304-3975(82)90058-5
Reingold, Omer (2008), „Undirected connectivity in log-space”, Journal of the ACM^⁠(d), 55 (4), pp. Article 17, 24 pages, doi:10.1145/1391289.1391291
Shiloach, Yossi; Even, Shimon (1981), „An on-line edge-deletion problem”, Journal of the ACM^⁠(d), 28 (1), pp. 1–4, doi:10.1145/322234.322235

Legături externe

Cod MATLAB pentru găsirea componentelor conexe în grafuri neorientate MATLAB File Exchange.
Componente conexe, Steven Skiena, Stony Brook Algorithm Repository