Маршрут

Материал из WikiGrapp
Перейти к:навигация, поиск

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

a = v_{0}, \, e_{1}, \, v_{1}, \, e_{2}, \ldots , \, v_{n-1}, \,
e_{n}, \, v_{n} = b

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

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

См. также

Литература

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