Componente biconexe

biconex

== include(page="template/taskheader" task_id="biconex") ==

Se dă un 'graf neorientat':http://mathworld.wolfram.com/UndirectedGraph.html $G = (V, E)$. Un graf se numeşte 'graf biconex':http://en.wikipedia.org/wiki/Biconnected_graph dacă nu are puncte de articulaţie. Un nod se numeşte punct de articulaţie dacă 'subgraful':http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Subgraphs obţinut prin eliminarea nodului şi a muchiilor incidente cu acesta nu mai este {'conex':http://en.wikipedia.org/wiki/Connectivity_(graph_theory)#Definitions_of_components.2C_cuts_and_connectivity}. O componentă biconexă a unui graf este un subgraf biconex maximal cu această proprietate.

Se dă un 'graf neorientat':http://mathworld.wolfram.com/UndirectedGraph.html $G = (V, E)$. Un graf se numeşte 'graf biconex':http://en.wikipedia.org/wiki/Biconnected_graph dacă nu are 'puncte de articulaţie':http://en.wikipedia.org/wiki/Articulation_vertex. O componentă biconexă a unui graf este un 'subgraf':http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Subgraphs biconex maximal cu această proprietate.

h2. Cerinţă

1 5
|

!> problema/biconex?biconex.png 60%!

!> problema/biconex?CB.png 35%!

h3. Explicaţie

Toate informaţiile necesare le găsiţi în cartea '"Introducere in algoritmi"':http://zhuzeyuan.hp.infoseek.co.jp/ita/chap23.htm, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. În exerciţiul $23-2$ se tratează teoretic problema determinării componentelor biconexe.

!> problema/biconex?biconex2.png 50%!
 

Pentru a descompune graful în componente biconexe am folosit proprietăţile parcurgerii $DFS$. După o parcurgere $DFS$ muchiile grafului se vor clasifica în două categorii:

* muchii care aparţin arborelui $DFS$ (muchiile normale din figură);
* muchii care nu aparţin arborelui şi care unesc un nod cu un strămoş al său, aceste muchii numindu-se muchii de întoarecere (muchiile reprezentate punctat în figură).

* muchii care aparţin arborelui $DFS$;
* muchii care nu aparţin arborelui şi care unesc un nod cu un strămoş al său, aceste muchii numindu-se muchii de întoarecere.

Problema determinării componentelor biconexe este strâns legată de problema determinării punctelor de articulaţie. După parcurgerea anterioară, un nod $X$ va fi nod de articulaţie dacă există cel puţin un fiu al său $Y$ din care nu se poate ajunge la un strămoş al lui $X$ pe un alt drum „în jos” în arborele $DFS$ şi apoi pe o muchie de întoarcere. Folosind o stivă în care reţinem muchiile din graf în ordinea în care sunt întâlnite în timpul parcurgerii, atunci când întâlnim un nod $X$ care are un fiu $Y$ cu proprietăţile de mai înainte, vom elimina din stivă toate muchiile până la muchia $(X, Y)$ inclusiv. Acest muchii formează o componentă biconexă. În desenul din dreapta, muchiile $(X, Y)$ cu proprietatea de mai sus sunt $(7, 8)$, $(5, 6)$, $(1, 5)$ şi $(1, 2)$.

Problema determinării punctelor de articulaţie este strâns legată de problema determinării componentelor biconexe. După parcurgerea anterioară, un nod $X$ va fi nod de articulaţie dacă există cel puţin un fiu al său $Y$ din care nu se poate ajunge la un strămoş al lui $X$ pe un alt drum „în jos” în arborele $DFS$ şi apoi pe o muchie de întoarcere. Folosind o stivă în care reţinem muchiile din graf în ordinea în care sunt întâlnite în timpul parcurgerii, atunci când întâlnim un nod $X$ care are un fiu $Y$ cu proprietăţile de mai înainte, vom elimina din stivă toate muchiile, inclusiv muchia $(X, Y)$. Acest muchii formează o componentă biconexă.

Dacă graful este reprezentat prin liste de adiacenţă atunci complexitatea 'algoritmului':job_detail/236392?action=view-source este $O(N + M)$.

Dacă graful este reprezentat prin liste de adiacenţă atunci complexitatea 'soluţiei':job_detail/236392?action=view-source este $O(N + M)$.

h2. Probleme suplimentare

Printre problemele care folosesc ideile de mai sus se numără:

* 'Ro':problema/ro
* 'Santa':problema/santa
* SICN, '_ONI 2000_':downloads#oni
* 'Roads':http://ceoi.inf.elte.hu/probarch/00/p2.htm, _CEOI 2000_
* "Apple Tree":http://acm.tju.edu.cn/toj/showp.php?pid=2840

* SICN, ONI 2000

== include(page="template/taskfooter" task_id="biconex") ==

3544