Graf tare conex

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

Graful orientat GG este un graf tare conex dacă pentru oricare două noduri x,y∈Xx, y \in X există cel puțin un drum de la xx la yy și unul de la yy la xx.

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 graf conex. Astfel, atunci când găsim drumuri între toate nodurile, dar nu în ambele sensuri, graful orientat este doar conex.

Publicitate

Iată un exemplu de graf orientat tare conex și un graf orientat conex:

Graf tare conex și graf conex (orientat)
Graf tare conex și graf conex (orientat)

Analizând exemplul:

  • graful din stânga este un graf orientat tare conex , deoarece putem găsi un drum în ambele sensuri între oricare două noduri;
  • graful din dreapta este un graf orientat conex , deoarece putem găsi un lanț între oricare două noduri, dar nu un drum.

În exemplul anterior, sunt evidențiate câteva arce. Subgrafurile pe care acestea le despart respectă proprietatea de tare conexitate.

Se observă astfel foarte ușor pentru graful din dreapta că nu putem ajunge de la nodurile {5,6,7}\{5,6,7\}, spre niciun din nodurile {1,2,3,4}\{1,2,3,4\}. Legătura între componentele tare conexe este unidirecțională, ceea ce împiedică graful din a fi tare conex (este doar un graf conex).

Noțiunea de subgraf tare conex este cea care stă la baza unei componente tare conexă.

de Echipa EZinfo · Actualizat:

Ai găsit o greșeală? Raportează
Publicitate