Маршрут

Маршрут (Sequence) — 1. Чередующаяся последовательность

[math]\displaystyle{ a = v_{0}, \, e_{1}, \, v_{1}, \, e_{2}, \ldots , \, v_{n-1}, \, e_{n}, \, v_{n} = b }[/math]

вершин и ребер графа такая, что [math]\displaystyle{ e_{i} = (v_{i-1},v_{i}), \; 1 \leq i \leq n }[/math]. Говорят, что маршрут соединяет вершины [math]\displaystyle{ \,a }[/math] и [math]\displaystyle{ \,b }[/math] — концы маршрута. Очевидно, что в обыкновенном графе маршрут можно задать перечислением лишь его вершин [math]\displaystyle{ a = v_{0}, \, v_{1}, \ldots , \, v_{n} = b }[/math] или его ребер [math]\displaystyle{ e_{1}, \, e_{2}, \, \ldots , \, e_{n} }[/math]. Маршрут конечен, если число входящих в него ребер конечно, и бесконечен в противном случае. Бесконечный маршрут, имеющий только одну концевую вершину ([math]\displaystyle{ \,a }[/math] или [math]\displaystyle{ \,b }[/math]), называется односторонне-бесконечным маршрутом; Маршрут без концевых вершин называется двусторонне-бесконечным маршрутом.

2. Путь, используемый для перемещения информации из одного места в другое. В сети с коммутацией пакетов маршрутом является список узлов сети, по которым данный конкретный пакет (или группа пакетов) должен проследовать или проследовал.

См. также

• Ориентированный маршрут,
• Цепь,
• Замкнутый маршрут,
• Ориентированный маршрут,
• Остовный маршрут,
• Открытый маршрут,
• Циклический маршрут,
• [math]\displaystyle{ \,Y }[/math]-сводимый маршрут.

Литература

• Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.

• Оре О. Теория графов. — М.: Наука, 1968.

• Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.