Punct de articulare

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 18 iulie 2021; verificarea necesită 1 editare .

Un punct de articulare în teoria grafurilor este un vârf al unui graf , după îndepărtarea căruia numărul componentelor conectate crește. Termenii „vârf de separare” și „balama” sunt, de asemenea, folosiți pentru a desemna acest concept.

Definiții

Un vârf al unui grafic se numește balama dacă subgraful obținut din grafic prin eliminarea vârfului și a tuturor muchiilor incidente acestuia constă din mai multe componente conectate decât graficul original . $v$ $G$ $G_{1}$ $G$ $v$ $G$

Noțiunea de biconectivitate este legată și de noțiunea de balama. Un graf dublu conectat este un graf conectat care nu conține balamale. Componenta biconectată este subgraful dublu conectat maxim (prin includere) al graficului original. Componentele biconectate sunt uneori numite blocuri.

Analogul de margine al balamalei este puntea . O punte este o muchie a unui grafic a cărei îndepărtare are ca rezultat o creștere a numărului de componente conectate în grafic.

Găsirea balamale

O soluție eficientă la problema găsirii tuturor balamalelor unui grafic se bazează pe algoritmul de căutare depth-first .

Să fie dat un grafic . Se notează prin mulțimea tuturor vârfurilor graficului adiacente . Să presupunem că am scanat graficul în profunzime, pornind de la un vârf arbitrar. Enumerăm toate vârfurile graficului în ordinea în care le-am introdus și atribuim un număr corespunzător fiecărui vârf . Dacă am ajuns mai întâi la vârf de la vârf , atunci vom numi vârful descendent al lui și strămoșul lui . Mulțimea tuturor descendenților unui vârf se notează cu . Notați cu numărul minim dintre toate vârfurile adiacente și cu acele vârfuri la care am ajuns de-a lungul căii care trece prin . $G$ $Adj(v)$ $v$ $v$ $n(v)$ $u$ $v$ $u$ $v$ $v$ $u$ $v$ $Ch(v)$ $Scăzut(v)$ $v$ $v$

Este clar că valoarea poate fi calculată recursiv, direct în procesul de parcurgere în profunzime: dacă în momentul de față se ia în considerare vârful și este imposibil să se treacă de la acesta la un vârf care nu a fost încă vizitat (adică, trebuie să vă întoarceți la strămoș sau să opriți traversarea, dacă este vârful de pornire), atunci pentru toți descendenții săi a fost deja calculat și, prin urmare, pentru acesta, este posibil să efectuați calculele corespunzătoare folosind formula $Scăzut(v)$ $v$ $v$ $v$ $scăzut$

$Low(v)=\min \left\{\min _{x\in Ch(v)}Low(x),\min _{y\in Adj(v)/Ch(v)}n( y)\dreapta\}.$

Cunoscând valoarea tuturor vârfurilor graficului, este posibil să se determine în mod unic toate balamalele acestuia conform următoarelor două reguli: $Scăzut(v)$

Vârful de pornire (adică cel de la care am început traversarea) este o balama dacă și numai dacă are mai mult de un copil.
Un alt vârf decât vârful de pornire este o balama dacă și numai dacă are un copil u astfel încât . $v$ $Scăzut(u)=n(v)$

Ca exemplu, luați în considerare aplicarea algoritmului descris la graficul prezentat în figura din dreapta. Numerele care marchează vârfurile corespund uneia dintre variantele posibile ale căutării depth-first. În această ordine, fiecare dintre vârfuri are exact un copil, cu excepția vârfului 6, care nu are copii. Vârful de pornire 1 are un singur copil, deci nu este o balama. Pentru vârfurile rămase, calculăm valorile funcției care ne interesează:

$Scăzut (6) = 5, Scăzut (5) = 2, Scăzut (4) = 2, Scăzut (3) = 2, Scăzut (2) = 1$ .

Vârful 2 are un copil 3, iar 5 are un copil 6 - în ambele cazuri, relația dorită este satisfăcută . Prin urmare, 2 și 5 sunt balamale. Nu există alte balamale în acest grafic. $Scăzut(u)=n(v)$

Vezi și

Componenta de conectivitate a unui grafic

Literatură

V. E. Alekseev, V. A. Talanov. Grafice și algoritmi. Structuri de date. Modele de calcul. — M. : BINOM. Knowledge Lab, 2006. - ISBN 5-94774-543-7 .