ВУЗ:
Составители:
56
а
1
а
6
а
5
а
9
(2.3)
а
1
а
6
а
5
а
9
а
10
а
6
а
4
(2.4)
В множестве возможных путей графа можно выделить специ-
фические подмножества. Ориентированной цепью (орцепью) назы-
вают такой путь, в который каждая дуга входит не более одного
раза. Пути (2.2) и (2.3) являются орцепями, а путь (2.4) − нет, т.к.
дуга а
6
встречается в нем два раза. Простой орцепью принято назы-
вать такой путь, в котором каждая вершина используется не более
одного раза. Например, путь (2.3) – это простая орцепь, а пути (2.2),
(2.4) таковыми не являются.
Маршрут есть неориентированный «двойник» пути. Это поня-
тие используется в тех случаях, когда можно пренебречь направле-
нием
дуг в графе. Если в графе G=<X,U> пренебречь направлением
дуг, то получим неориентированный граф, который обозначают
⎯G=<X,
⎯
U>, и в этом случае дуги называются ребрами. Таким обра-
зом, маршрут есть последовательность инцидентных ребер. Точно
также как были определены орцепи и простые орцепи, можно опре-
делить цепи и простые цепи.
Петлей называется дуга, начальная и конечная вершины кото-
рой совпадают. На рис. 2.21 дуги а
2
и а
5
– петли.
Путь а
1
,а
2
… а
n
называют замкнутым,
если в нем начальная вершина дуги а
1
сов-
падает с конечной вершиной дуги а
n
.
На рис. 2.21 следующие последова-
тельности дуг - замкнутые пути:
а
3
а
6
а
11
; (2.5)
а
11
а
3
а
4
а
7
а
1
а
12
а
9
; (2.6)
а
3
а
4
а
7
а
10
а
9
а
11
. (2.7)
Рис. 2.21
а
5
а
4
а
3
а
1
а
2
а
6
а
7
а
8
а
9
а
10
а
11
а
12
х
1
х
2
х
3
х
6
х
4
х
5
Страницы
- « первая
- ‹ предыдущая
- …
- 58
- 59
- 60
- 61
- 62
- …
- следующая ›
- последняя »
