Drum (teoria grafurilor)

În teoria grafurilor, un drum într-un graf este un șir finit sau infinit de muchii care unesc o succesiune de noduri care, după majoritatea definițiilor, sunt toate distincte (și, deoarece nodurile sunt distincte, la fel și muchiile). Un drum orientat într-un graf orientat este un șir finit sau infinit de arce care unesc o succesiune de noduri distincte, dar cu restricția adăugată ca toate arcele să fie toate orientate în aceeași direcție.

Drumurile sunt un concept fundamental al teoriei grafurilor, fiind descrise în secțiunile introductive ale majorității textelor de teoria grafurilor. Vezi de ex Bondy și Murty (1976), Gibbons (1985) sau Diestel (2005). Korte și colab. (1990) acoperă subiecte de algoritmi mai avansați referitori la drumurile prin grafuri.