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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Маршрут''' (''Sequence'') - 1. Чередующаяся последовательность <math>a = v_{0}, \, e_{1}, \, v_{...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 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>),
называется односторонне-бесконечным маршрутом; '''М.''' без концевых вершин
называется [[односторонне-бесконечный маршрут|односторонне-бесконечным маршрутом]]; '''Маршрут''' без концевых вершин
называется двусторонне-бесконечным маршрутом.
называется [[двусторонне-бесконечный маршрут|двусторонне-бесконечным маршрутом]].


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


См. также ''Ориентированный маршрут, Цепь, Замкнутый маршрут, Ориентированный маршрут, Остовный маршрут, Открытый маршрут, Циклический маршрут, <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.