Circuit - Grafuri orientate
Fie un graf orientat.
Se numește circuit în graful un drum simplu în care primul nod coincide cu ultimul.
Circuitul diferă de noțiunea de ciclu de la grafuri neorientate prin existența „sensului de mers” al arcelor.
Publicitate
Clasificarea circuitelor
Circuitele dintr-un graf orientat se pot clasifica în funcție de nodurile sale:
- circuit elementar : nodurile diferă două câte două (nu se repetă niciun nod), cu excepția extremităților;
- circuit neelementar : se trece de mai multe ori prin cel puțin un nod (excluzând capetele circuitului).
Lungimea unui circuit este egală cu numărul de arce din care acesta este format.
Exemple de circuite în graful orientat:
Pentru acest graf orientat:
- este cel mai lung circuit elementar (lungime );
- , și sunt circuite elementare;
- și sunt cele mai lungi circuite simple neelementare, de lungime .
Un graf orientat fără circuite se numește graf aciclic.