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 cu această proprietate.

h2. Cerinţă

1 5
|

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

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

h3. Explicaţie

h2. Indicaţii de rezolvare

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ă).
 
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)$.
 
Dacă graful este reprezentat prin liste de adiacenţă atunci complexitatea 'algoritmului':job_detail/236392?action=view-source este $O(N + M)$.
 
h2. Probleme suplimentare
 
În multe aplicaţii practice modelate cu ajutorul grafurilor, punctele de articulaţie nu sunt de dorit. Să considerăm o reţea de telecomunicaţii. Dacă o centrală dintr-un punct de articulaţie se defectează atunci comunicarea este întreruptă nu numai cu centrala respectivă ci şi cu alte centrale. Deci, un graf biconex este dorit.
 
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

O scurtă lecţie de teorie 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$.

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

3544