Componente tare conexe la BAC: recunoaștere și exemple

Un graf orientat este tare conex dacă, pentru oricare două vârfuri distincte, poți ajunge din primul în al doilea și din al doilea în primul, respectând sensul arcelor. Nu este suficient ca desenul să pară legat. O componentă tare conexă este un grup maximal de vârfuri între care există această accesibilitate reciprocă.

Lecția urmărește recunoașterea componentelor pe grafuri mici, la nivelul capitolului de grafuri orientate pentru matematică-informatică. Nu ai nevoie de implementarea unui algoritm avansat pentru a verifica exemplele. Consultă programa sesiunii tale pentru încadrarea exactă a capitolului.

De ce contează ambele sensuri?

Într-un graf cu singurul arc (1,2), poți merge din unu în doi, dar nu poți reveni. Cele două vârfuri nu formează împreună o componentă tare conexă. Dacă ignori săgeata, obții o muchie care le leagă, însă ai schimbat problema.

În schimb, arcele (1,2), (2,3), (3,1) formează un circuit orientat. Din orice vârf poți ajunge în oricare altul urmând circuitul. Nu trebuie să existe un arc direct între fiecare pereche; un drum cu mai multe arce este suficient.

De exemplu, din doi ajungi în unu prin trei. Confuzia dintre „există arc” și „există drum” duce la fragmentarea greșită a unui grup care este deja tare conex. Notează drumurile concrete când justifici apartenența unor vârfuri la aceeași componentă.

Exemplul de lucru: trei grupuri și două treceri

Folosim șase vârfuri și arcele (1,2), (2,3), (3,1), (3,4), (4,5), (5,4), (5,6). Lista este completă; nu presupunem săgeți suplimentare doar din apropierea vârfurilor în desen.

Vârfurile unu, doi și trei comunică reciproc prin primul circuit. Vârfurile patru și cinci comunică reciproc prin cele două arce opuse. Din primul grup poți ajunge în al doilea prin arcul (3,4), dar nu există drum de întoarcere.

Din al doilea grup poți ajunge în șase. Vârful șase nu are arc de ieșire, deci nu poate reveni în niciunul dintre grupurile anterioare. Obținem componentele {1,2,3}, {4,5} și {6}.

Punct de plecare	Vârfuri accesibile, incluzând plecarea	Componenta sa
1, 2 sau 3	1, 2, 3, 4, 5, 6	{1,2,3}
4 sau 5	4, 5, 6	{4,5}
6	6	{6}

Includem fiecare vârf în propria mulțime de accesibilitate prin drumul de lungime zero. Această convenție explică de ce un singur vârf poate constitui o componentă tare conexă chiar dacă nu are buclă.

Cum construiești tabelul fără să pierzi drumuri?

Pentru un vârf ales, marchezi întâi vârful însuși. Adaugi toate destinațiile arcelor care pleacă din vârfurile deja marcate și repeți până când nu mai apare nimic nou. Pe un graf mic, această procedură se poate face cu o listă pe hârtie.

Pornind din patru, marchezi patru și apoi cinci. Din cinci revii în patru, deja marcat, și ajungi în șase. Din șase nu mai pleacă arce. Lista finală este patru, cinci, șase; repetarea unei etichete nu adaugă un vârf nou.

Pentru fiecare pereche de vârfuri verifici dacă primul apare în lista celui de-al doilea și invers. Dacă ambele verificări reușesc, ele aparțin aceleiași componente. O singură apariție confirmă numai accesibilitatea într-un sens.

Această schemă îți permite să controlezi înțelegerea definiției printr-o operație concretă. Nu înlocui verificarea cu presupunerea că orice pereche de vârfuri aflată pe aceeași linie a desenului este conectată în ambele sensuri.

Ce înseamnă cuvântul „maximal”?

Grupul {1,2} din exemplu are accesibilitate reciprocă, dar nu este o componentă tare conexă de sine stătătoare. Îl putem extinde cu trei, păstrând proprietatea. Componenta corectă include toate cele trei vârfuri.

Maximal nu înseamnă că alegem numai componenta cu cele mai multe vârfuri. Și grupul {4,5}, și grupul {6} sunt componente, deși au dimensiuni mai mici. Fiecare este maximal în sensul că nu poate primi un vârf exterior fără să piardă accesibilitatea reciprocă.

Componentele împart mulțimea vârfurilor: fiecare vârf aparține uneia singure. Dacă două grupuri pretins maximale ar avea un vârf comun, drumurile prin acel vârf ar permite reunirea lor. De aceea, o listă în care același vârf apare în două componente trebuie corectată.

Ce schimbă adăugarea unui arc?

Adăugăm arcul (6,1) în exemplul inițial. Acum poți trece din primul grup în al doilea, apoi în șase și înapoi în primul. În interiorul fiecărui grup aveai deja deplasare reciprocă. Toate cele șase vârfuri formează o singură componentă tare conexă.

Dacă adaugi numai (6,4), unești reciproc grupul {4,5} cu vârful șase. Nu apare însă niciun drum din acest grup spre unu, doi sau trei. Rămân două componente: {1,2,3} și {4,5,6}.

Prin urmare, nu orice arc nou reduce numărul componentelor și nu orice arc între componente le unește. Arcul (1,5), adăugat singur grafului inițial, oferă doar o altă trecere înainte, care exista deja printr-un drum. Numărul componentelor rămâne trei.

Greșeli frecvente la recunoaștere

Un vârf cu ambele grade pozitive nu garantează tare conexitatea grafului. Poți avea două circuite separate, fiecare cu grade interioare și exterioare pozitive pentru toate vârfurile. Totuși, niciun drum nu trece de la un circuit la celălalt.

Nici egalitatea gradelor interioare și exterioare nu este definiția cerută. Ea privește numărul arcelor locale; tare conexitatea privește existența drumurilor între vârfuri. Folosește proprietatea potrivită întrebării, chiar dacă alte condiții sunt adevărate pe același exemplu.

Într-un graf cu mai mult de un vârf, un grad exterior zero sau interior zero exclude tare conexitatea întregului graf. Acesta este un test rapid de respingere. Absența unor astfel de grade nu este, singură, o demonstrație pozitivă.

Exerciții de verificare

1. Elimină arcul (3,4) din exemplul inițial. Componentele tare conexe rămân aceleași trei, dar primul grup nu mai ajunge la celelalte. Ai schimbat accesibilitatea dintre componente, nu interiorul lor.
2. Păstrează numai arcele (1,2), (2,3), (3,4) pe patru vârfuri. Există patru componente, fiecare cu un singur vârf, deoarece nu există niciun drum de revenire între vârfuri distincte.
3. Adaugă (4,1) la graful exercițiului anterior. Cele patru arce formează un circuit orientat, iar toate vârfurile devin o singură componentă.
4. În exemplul inițial, poate exista drum de la doi la șase? Da: doi, trei, patru, cinci, șase. Existența lui nu pune cele două extremități în aceeași componentă, fiindcă lipsește drumul invers.

Întrebări frecvente

Un vârf izolat este componentă tare conexă?

Da, reprezintă singur o componentă. Nu poate fi unit cu alt vârf într-un grup cu accesibilitate reciprocă. Convenția drumului de lungime zero asigură accesibilitatea sa față de sine.

Cum justific numărul componentelor într-o rezolvare?

Scrie grupurile, arată drumurile reciproce din fiecare și explică de ce trecerile dintre grupuri nu permit revenirea. Dacă doar încercuiești vârfurile pe un desen, justificarea rămâne greu de verificat.

Unde pot exersa recunoașterea?

Alege cerințe cu grafuri orientate din subiectele BAC și construiește tabelul accesibilității înainte să privești răspunsul. Dacă ai nevoie de feedback, poți compara anunțuri pentru informatică, având pregătite listele și drumurile pe care le-ai găsit.