Drum

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

Se numește drum în graful G o succesiune de noduri cu proprietatea că oricare 2 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.

Clasificarea drumurilor

    1. În funcție de arce:
  • simple: toate arcele din drum sunt diferite între ele (nu se repetă niciun arc);
  • compuse: se pot repeta unele arce de mai multe ori.
    2. În funcție de noduri:
  • elementare: toate nodurile diferă 2 câte 2 (nu se trece prin același nod de 2 ori);
  • neelementare: se pot repeta nodurile.
Graf orientat + Drumuri

Lungimea unui drum este dată numărul de arce pe care acesta îl conține.
  Pentru graful anterior, drumul D3 este cel mai lung drum simplu (neelementar), iar D5 este cel mai lung drum elementar, de lungime 5.