В чем отличие пути от маршрута в теории графов?

Question

[Alexveto]

Маршрут в графе — это чередующаяся последовательность вершин и рёбер в которой любые два соседних элемента инцидентны.
Путь — последовательность рёбер (в неориентированном графе) и/или дуг (в ориентированном графе), такая, что конец одной дуги (ребра) является началом другой дуги (ребра).

Не понимаю в чем отличие, по мне так это одно и тоже, или я все таки чего-то не понимаю?

Answer 1

[balezz]

По Кузнецову О.П. Дискретная математика для инженеров 1980 г.: определение маршрута более общее, дается в разделе 4-2, понятие пути вводится для ориентированных графов, раздел 4-4

Answer 2

[YURIY KOZLOV]

Сам учил Теорию графов довольно давно, помню не все. Судя по результатам поиска в сети, есть разные трактовки:
- маршрут и пути, по сути, одно и то же...
- путь есть частный случай маршрута, но не содержащий повторяющиеся ребра..
Встречалось и еще что-то....

Если же брать дословно формулировку вашего вопроса, то маршрут - подграф исходного графа, с вершинами и ребрами, а путь - множество ТОЛЬКО ребер... Не думаю, что это правильно, но у вас написано именно так.

Answer 3

[sgrogov]

Вот что подсказал гугл:

Маршрут называется открытым, если его концевые вершины различны, и замкнутым или циклическим в противном случае.
Открытый маршрут называют цепью, если все ребра в нем различны (вершины могут повторяться).
Цепь, в которой не повторяются вершины, называется путем (простой цепью).

Отсюда следует, что путь - часть маршрута, не содержащая рёбра между повторно встречающимися вершинами.

Определения подсмотрел здесь https://studopedia.ru/3_80680_marshruti-puti-i-tsi...

Answer 4

[otdameskapizm]

Если еще актуально)))
Ну вообще, маршрут - это совокупность вида V0(E0E1), V1(E1E2), V2(E2E3), ... Vn (V - вершины, Е - ребра). Он может быть любой. Например маршрут может быть цепью - маршрут без повтора проходимых ребер графа (то есть по каждому ребру проход совершается только один раз. Маршрут может быть простой цепью - маршрут, в котором при проходе по графу нет повторяющихся вершин. А вот ПУТЬ - это тот же маршрут, только он ориентирован (т.е у него есть направление). Если есть граф и нужно совершить по нему обход, неважно в каком направлении - то это просто маршрут, а если в определенном направлении - то это путь.