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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Граф G, описываемый тройкой вида
G = (X, A, С),
где Х = { x
i
}, i=1,2,3,...,n - множество вершин,
А = { a
i
}, i=1,2,3,...,m - множество дуг,
С = { c
i
}, i=1,2,3,...,m - множество характеристик дуг, называется графом со
взвешенными дугами.
Пример такого графа приведен на рис.27,а. При рассмотрении пути M,
представленного последовательностью дуг (а
1
, а
2
, ..., а
q
), за его вес (или длину,
или
стоимость) принимается число L (M), равное сумме весов всех дуг,
входящих в путь, то есть
L(M)=∑ c
i
для всех
a
i
∈M
Длиной (или мощностью) пути называется число дуг, входящих в него.
Чаще всего термин "длина" употребляется, когда все дуги, входящие в путь,
имеют веса, равные 1, то есть когда вес пути совпадает с его длиной
(мощностью).
x
2
x
1
x
3
x
4
a
7
/c
7
a
5
/c
6
a
3
/c
3
a
4
/c
4
a
1
/c
1
a
2
/
c
2
x
3
/v
3
x
1
/v
1
x
2
/v
2
x
1
/v
1
x
2
/
v
2
x
3
/v
3
x
4
/v
4
x
5
/v
5
a
8
/c
8
a
5
/c
5
a
7
/c
7
a
1
/c
a
2
/c
a
3
/c
3
a
4
/c
4
а)
б)
в)
Рис. 27. Взвешенные графы: а) граф со взвешенными
дугами; б) граф со взвешенными вершинами;
в) взвешенный граф 
  Граф G, описываемый тройкой вида
    G = (X, A, С),
    где Х = { xi }, i=1,2,3,...,n - множество вершин,
    А = { ai }, i=1,2,3,...,m - множество дуг,
    С = { ci }, i=1,2,3,...,m - множество характеристик дуг, называется графом со
взвешенными дугами.
     Пример такого графа приведен на рис.27,а. При рассмотрении пути M,
представленного последовательностью дуг (а1, а2, ..., аq), за его вес (или длину,
или стоимость) принимается число L (M), равное сумме весов всех дуг,

входящих в путь, то есть                                       L(M)=∑ ci   для всех        ai ∈M

      Длиной (или мощностью) пути называется число дуг, входящих в него.
Чаще всего термин "длина" употребляется, когда все дуги, входящие в путь,
имеют веса, равные 1, то есть когда вес пути совпадает с его длиной
(мощностью).




                          x2                                               x2/v2

                a1/c1                a2/c2
                           a4/c4
           x1                                   x3
                               a3/c3
                                                                 x1/v1
                                     a5/c6
                  a7/c7 x4                                                         x3/v3
                                                                            б)
                        а)
                                                       x2/v2

                                       a1/c
                                                          a2/c
                                     x1/v1     a3/c3
                                                                   x3/v3
                                               a4/c4
                                              a5/c5
                             a8/c8
                                              a7/c7
                                                           x4/v4
                                      x5/v5
                                       в)
            Рис. 27. Взвешенные графы: а) граф со взвешенными
            дугами;      б) граф со взвешенными вершинами;
            в) взвешенный граф

Страницы