Conexitatea grafurilor orientate
Când ne referim la proprietăți de conexitate pentru grafurile orientate, este important să recunoaștem clasificările succesiunilor de noduri și structurile care se pot forma în funcție de arcele grafului.
Un drum într-un graf orientat reprezintă o succesiune de arce care unesc nodurile între ele. Un drum elementar în graful orientat are noduri care nu se repetă între ele.
Citește totUn circuit într-un graf orientat reprezintă o succesiune de arce în care primul și ultimul nod coincid. Un graf fără circuite se numește graf aciclic.
Citește totUn graf orientat este tare conex dacă între orice două noduri se găsește cel puțin un drum. Tare conexitatea are la bază noțiunea de graf conex.
Citește totO componentă tare conexă într-un graf orientat reprezintă un subgraf ce are proprietatea de graf tare conex. Transformarea în graf tare conex se poate face prin formarea unui circuit între componentele tare conexe.
Citește tot