Маршрут: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Маршрут''' (''[[Sequence]]'') -
'''Маршрут''' (''[[Sequence]]'')
1. Чередующаяся последовательность
1. Чередующаяся последовательность


<math>a = v_{0}, \, e_{1}, \, v_{1}, \, e_{2}, \ldots , \, v_{n-1}, \,
:::<math>a = v_{0}, \, e_{1}, \, v_{1}, \, e_{2}, \ldots , \, v_{n-1}, \,
e_{n}, \, v_{n} = b</math>
e_{n}, \, v_{n} = b</math>


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


==См. также==  
==См. также==  
''[[Ориентированный маршрут]], [[Цепь]], [[Замкнутый маршрут]], [[Ориентированный маршрут]], [[Остовный маршрут]], [[Открытый маршрут]], [[Циклический маршрут]], [[Y-сводимый маршрут|<math>Y</math>-сводимый маршрут]].''
* ''[[Ориентированный маршрут]],''
* ''[[Цепь]],''
* ''[[Замкнутый маршрут]],''
* ''[[Ориентированный маршрут]],''
* ''[[Остовный маршрут]],''
* ''[[Открытый маршрут]],''
* ''[[Циклический маршрут]],''
* ''[[Y-сводимый маршрут|<math>\,Y</math>-сводимый маршрут]].''
==Литература==
==Литература==
[Лекции],  
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.


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


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

Текущая версия от 17:06, 3 мая 2011

Маршрут (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. Путь, используемый для перемещения информации из одного места в другое. В сети с коммутацией пакетов маршрутом является список узлов сети, по которым данный конкретный пакет (или группа пакетов) должен проследовать или проследовал.

См. также

Литература

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