Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 52 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

5.Пути и циклы в графах
5.1.Пути и маршруты
Путем в орграфе называется последовательность дуг, в которой конечная
вершина всякой дуги, кроме последней, является начальной вершиной
следующей дуги.
Например
, для графа на рис.25 последовательности дуг
M
1
: a
6
, a
5
, a
9
, a
8
, a
4
M
2
: a
1
, a
6
, a
5
, a
9
, a
7
M
3
: a
1
, a
6
, a
5
, a
9
, a
10
, a
6
, a
4
являются путями. Пути могут быть различными.
Орцепью (или простым путем) называется такой путь, в котором каждая
дуга используется не более одного раза.
Так пути M
1
и M
2
являются орцепями, а M
3
нет, поскольку дуга а
6
используется дважды.
Простой орцепью (или элементарным путем) называется путь, в котором
каждая вершина используется не более одного раза.
Простой орцепью является путь M
2.
Для неориентированного графа понятия
маршрута, цепи и простой цепи
аналогичны понятиям пути, орцепи и простой орцепи в орграфе. (В определениях
следует заменить слово "дуга" на слово "ребро").
Путь или маршрут можно изображать также последовательностью вершин.
Так путь M
1
можно представить последовательностью вершин x
2
, x
5
, x
4
, x
3
, x
5
, x
6
и
такое представление часто оказывается более полезным.
x
1
x
2
x
3
x
4
x
6
x
5
a
1
a
10
a
2
a
4
a
5
a
9
a
8
a
3
a
7
a
6
Рис. 25. Орграф 
                                           5.Пути и циклы в графах
                                            5.1.Пути и маршруты


      Путем в орграфе называется последовательность дуг, в которой конечная
вершина   всякой   дуги,    кроме            последней,      является         начальной   вершиной
следующей дуги.
      Например, для графа на рис.25 последовательности дуг
                                             M1: a6, a5, a9, a8, a4
                                             M2: a1, a6, a5, a9, a7
                                            M3: a1, a6, a5, a9, a10, a6, a4
являются путями. Пути могут быть различными.

                                 x2           a10     x3
                                                            a9
                           a1                   a7
                   x1                                              x4
                                 a3
                                                    a6 a8
                            a2                              a5
                                      x6       a4     x5


                                           Рис. 25. Орграф



      Орцепью (или простым путем) называется такой путь, в котором каждая
дуга используется не более одного раза.
      Так пути M1 и M2 являются орцепями, а M3 нет, поскольку дуга а6
используется дважды.
      Простой орцепью (или элементарным путем) называется путь, в котором
каждая вершина используется не более одного раза.
      Простой орцепью является путь M 2.
      Для неориентированного графа понятия маршрута, цепи и простой цепи
аналогичны понятиям пути, орцепи и простой орцепи в орграфе. (В определениях
следует заменить слово "дуга" на слово "ребро").
      Путь или маршрут можно изображать также последовательностью вершин.
Так путь M1 можно представить последовательностью вершин x2, x5, x4, x3, x5, x6 и
такое представление часто оказывается более полезным.

Страницы