Drum - Grafuri orientate
Fie un graf orientat.
Se numește drum în graful o succesiune de noduri cu proprietatea că oricare două noduri sunt unite de un arc.
Fiind vorba despre un graf orientat, va trebui să ținem cont de orientarea arcelor pentru a determina corect un drum.
Publicitate
Clasificarea drumurilor
Clasificarea drumurilor în graful orientat se poate face după două criterii.
În funcție de noduri:
- drum elementar : toate nodurile diferă două câte două (nu se trece prin același nod de două ori);
- drum neelementar : se pot repeta nodurile.
În funcție de arce:
- drum simplu : toate arcele din drum sunt diferite între ele (nu se repetă niciun arc);
- drum compus : se pot repeta unele arce de mai multe ori în același drum.
Exemple de drumuri în graful orientat:
Lungimea unui drum este dată numărul de arce pe care acesta îl conține.
Pentru graful anterior, drumul este cel mai lung drum simplu (neelementar), iar este cel mai lung drum elementar, de lungime .