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

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 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.

Навигация