Определение 9.

Путь в графе или орграфе – это последовательность ребер, по которым можно поочередно проходить.

 

Другими словами, путь из вершины А в вершину В начинается в А и походит по набору ребер до тех пор, пока не будет достигнута вершина В.

С формальной точки зрения, путь из вершины в вершину – это последовательность ребер графа , , …, .

При этом требуется, чтобы любая вершина встречалась на таком пути не более чем один раз. У всякого пути есть длина – число ребер в нем (Рисунок 9).

 

Рисунок 9. Путь в графе. В данном случае имеет место два пути из вершины А в вершину В, определяемых суммой длин дуг:

для пути ;

для пути .