Маршрут
Маршрут (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.