4624
правки
Маршрут: различия между версиями
Материал из WikiGrapp
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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. | |||
