Tare conexitate

  Fie G=(X,E) un graf orientat.

Graful orientat G este tare conex dacă pentru oricare 2 noduri x,y∈X există cel puțin un drum de la x la y și unul de la y la x.
Graf orientat tare conex + conex

  • Graful 1 este un graf tare conex, deoarece putem găsi un drum în ambele sensuri între oricare 2 noduri.
  • Graful 2 este un graf conex. Putem găsi un lanț între oricare două noduri, dar nu un drum. (când vorbim de „lanț”, nu ținem cont de sensul arcelor/muchiilor).

Împărțind imaginar cele două grafuri în câte două componente conexe, putem remarca că arcele colorate sunt cele care fac diferența. Pentru primul graf avem legături „dus-întors” între cele două componente, dar în dreapta găsim doar într-un sens.