Маршрут

Материал из WEGA
Версия от 14:51, 19 ноября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Маршрут''' (''Sequence'') - 1. Чередующаяся последовательность <math>a = v_{0}, \, e_{1}, \, v_{...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Маршрут (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]-сводимый маршрут.

Литература

[Лекции],

[Оре],

[Словарь]