Componentă puternic conectată

Un graf direcționat (digraf) se numește puternic conectat dacă oricare dintre vârfurile sale s și t sunt puternic conectate, adică dacă există o cale direcționată de la până  și o cale direcționată simultan de la până la

Componentele puternic conectate ale unui digraf sunt subgrafele puternic legate de incluziune maximă. O regiune puternic conectată este un set de vârfuri de componente puternic conectate.

Definiții

Un digraf care nu aparține clasei de grafuri puternic conectate conține un set de componente puternic conectate și un set de muchii direcționate care merg de la o componentă la alta.

Orice vârf al unui digraf este puternic legat de el însuși.

Algoritmi

Cel mai simplu algoritm pentru rezolvarea problemei găsirii componentelor puternic conectate într-un digraf funcționează după cum urmează:

  1. Utilizând închiderea tranzitivă , verificăm dacă este accesibil de la și de la toate perechile și
  2. Apoi definim un astfel de graf nedirecționat , care conține o margine pentru fiecare astfel de pereche.
  3. Căutarea componentelor conectate ale unui astfel de graf nedirecționat produce componente puternic conectate ale digrafului.

Evident, timpul de rulare principal al acestui algoritm este ocupat de o închidere tranzitivă.

Există și trei algoritmi care rezolvă această problemă în timp liniar, adică de V ori mai rapid decât algoritmul de mai sus. Aceștia sunt algoritmii lui Kosaraju , căutarea componentelor puternic conectate cu două stive și Tarjan .

Exemplu

Figura prezintă un digraf pentru care sunt afișate toate cele trei componente puternic conectate (zone umbrite conturate de o linie punctată).

Vezi și

Literatură