Componentă conexă

Un grafic cu trei componente conexe.

Î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 Format:Ill-wd: există un drum trivial de lungime zero de la orice nod la el însuși.
• Este Format:Ill-wd: dacă există un drum de la u la v, aceleași muchii formează un drum de la v la u.
• Este Format:Ill-wd: 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 Format:Ill-wd ale acestei relații.

Numărul de componente conexe

Numărul de componente conexe este o importantă Format:Ill-wd a unui graf. În Format:Ill-wd, acesta poate fi interpretată ca Format:Ill-wd 0 al grafului. În Format:Ill-wd, este egal cu multiplicitatea lui 0 ca valoare proprie a Format:Ill-wd a grafului. Este, de asemenea, indicele primului coeficient diferit de zero al Format:Ill-wd al unui graf. Numărul de componente conexe joacă un rol cheie în Format:Ill-wd care caracterizează grafurile care au Format:Ill-wd și în definirea Format:Ill-wd.

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 Format:Ill-wd. Acești algoritmi necesită un timp Format:Ill-wd 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 Format:Ill-wd, 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 Format:Harvard citation.

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 Format:Ill-wd 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ă Format:Nowrap.

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

• Format:Citation
• Format:Citation
• Format:Citation
• Format:Citation

Legături externe

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