Componenta tare conexă
Fie un graf orientat.
Se numește componentă tare conexă a grafului un subgraf al său, maximal în raport cu proprietatea de tare conexitate.
Altfel spus, o componentă tare conexă este o parte din graf care respectă proprietatea de tare conexitate.
Un graf tare conex este format dintr-o singură componentă tare conexă. Un nod izolat reprezintă la rândul lui o componentă tare conexă.
Exemple de componente tare conexe:
Observăm că:
- graful din stânga este tare conex, astfel este compus dintr-o singură componentă tare conexă;
- graful din dreapta are trei componente tare conexe. Văzute ca subgrafuri, ele au proprietatea de tare conexitate.
Transformarea în graf tare conex
Un graf orientat poate fi transformat într-un graf tare conex prin formarea unui circuit între componentele tare conexe.
Într-un graf orientat cu componente tare conexe, ne sunt necesare arce pentru a-i restabili proprietatea de tare conexitate (pentru a forma circuitul necesar).
Cele componente conexe se unesc într-un circuit prin adăugarea a arce.
O particularitate a exemplului arată cum subgraful format din nodurile nu formează o componentă tare conexă. Deși putem ajunge la nodul din nodurile și , în sens invers nu avem drum. Deoarece avem drum într-un singur sens, acest subgraf poate fi numit componentă conexă, dar nu componentă tare conexă.