Graf tare conex
Fie G=(X,E) un graf orientat.
Graful orientat G este tare conex dacă pentru oricare două noduri x,y∈X există cel puțin un Drumul este o succesiune de noduri unite prin arce.drum de la x la y și unul de la y la x.
Numim astfel un graf orientat tare conex dacă putem găsi drumuri în ambele sensuri între toate nodurile grafului (două câte două).
Proprietatea de tare conex are la bază noțiunea de Un graf este conex dacă are toate nodurile unite două câte două prin cel puțin lanț.graf conex. Putem defini astfel un graf orientat ca fiind doar conex, atunci când nodurile sunt unite între ele doar într-un sens.
Exemplu de graf tare conex și graf orientat conex:
Analizând exemplul:
- Graful 1 este un graf orientat tare conex, deoarece putem găsi un drum în ambele sensuri între oricare două noduri;
- Graful 2 este un graf orientat conex, deoarece putem găsi un Putem aplica noțiuni de la grafurile neorientate considerând arcele ca fiind muchii (fără direcție)lanț între oricare două noduri, dar nu un drum.
În desen am marcat câteva arce cu roșu. Subgrafurile pe care le despart respectă proprietatea de tare conexitate. Intuitiv, proprietatea de tare conexitate pentru graf depinde de felul în care se unesc componentele.
Asfel, observăm la primul graf o legătură „dus-întors” între cele două componente, iar pentru al doilea graf avem doar într-un sens.
Noțiunea de subgraf tare conex este cea care stă la baza unei Componenta tare conexă este un subgraf cu proprietatea de tare conexitate.componente tare conexă.