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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Граф со взвешенными вершинами - это граф, описываемый тройкой
G = ( X, А, V ),
где Х = { х
i
}, i=1,2,...,n - множество вершин графа,
А = { a
i
}, i=1,2,...,m - множество дуг графа,
V={v
i
}, i=1,2,...,n - множество характеристик вершин.
В качестве характеристик вершин могут выступать "стоимость", "мощность",
"вес" и т.п. Пример такого графа приведен на рис. 27,б. Для графа со
взвешенными вершинами в случае представления пути последовательностью
вершин, весом пути является сумма весов, входящих в этот путь вершин.
И наконец,
взвешенный граф определяется четверкой вида G = (Х, А, V,
С), то есть и дуги, и вершины этого графа имеют некоторые характеристики.
Область применения взвешенных графов в качестве моделей довольно
обширна: транспортные задачи, задачи оптимизации сети связи и системы
перевозок и др. Одной из известнейших оптимизационных задач является
нахождение кратчайших путей в графе со взвешенными
дугами.
. Упражнения к п. 5.3 .
1. На рисунке дан граф со
взвешенными дугами,
который представляет сеть
допустимых маршрутов для
некоторого судна. Каждая
дуга имеет пометку (a, b),
причем а равно выгоде,
получаемой при
обслуживании этого
маршрута, а b - времени
обслуживания маршрута.
Найти какой из
перечисленных путей
наиболее выгодный (в
терминах скорости оборота
капитала) путь судна.
1. A → B → C → D → E → A
2.
A → B → C → E → D → A
3.
A → D → B → C → E → A
4.
A → C → E → D → B → A
Решение:
Скорость оборота капитала n -ого пути судна найдем как суммарную
выгоду пути, деленную на суммарное время, то есть v
n
= Σa
i
/ Σb
i.
1.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. v
1
= . . . . .
(15,8
(15,9)
(8,8)
(10,3)
(
8
,
6
)
(1
,
2)
(14,4
(20,9
(3,2)
(6,9)
(
1,2
)
(4,9)
A
B
C
D
E
         Граф со взвешенными вершинами - это граф, описываемый тройкой
         G = ( X, А, V ),
         где Х = { хi }, i=1,2,...,n - множество вершин графа,
         А = { ai }, i=1,2,...,m - множество дуг графа,
         V={vi}, i=1,2,...,n - множество характеристик вершин.
         В качестве характеристик вершин могут выступать "стоимость", "мощность",
"вес" и т.п. Пример такого графа приведен на рис. 27,б. Для графа со
взвешенными вершинами в случае представления пути последовательностью
вершин, весом пути является сумма весов, входящих в этот путь вершин.
         И наконец, взвешенный граф определяется четверкой вида G = (Х, А, V,
С), то есть и дуги, и вершины этого графа имеют некоторые характеристики.
         Область применения взвешенных графов в качестве моделей довольно
обширна: транспортные задачи, задачи оптимизации сети связи и системы
перевозок и др. Одной из известнейших оптимизационных задач является
нахождение кратчайших путей в графе со взвешенными дугами.



.        Упражнения к п. 5.3                                                                            .
1. На рисунке дан граф со                                              A               (1,2)                   B
взвешенными дугами,
который представляет сеть                                 (20,9                            (1,2)
допустимых маршрутов для                                                                                              (6,9)
                                                                                  (10,3)
некоторого судна. Каждая                                                                                      (4,9)
                                                                  (15,9)
дуга имеет пометку (a, b),
причем а равно выгоде,                                                                     (3,2)
                                                                                                                        C
получаемой при                                                                                         (8,6)
обслуживании этого
                                                                               (8,8)
маршрута, а b - времени                               E
                                                                       (15,8
обслуживания маршрута.                                                                                      (14,4
Найти какой из
перечисленных путей                                                                                D

наиболее выгодный (в
терминах скорости оборота
капитала) путь судна.
    1.   A→B→C→D→E→A
    2.   A→B→C→E→D→A
    3.   A→D→B→C→E→A
    4.   A→C→E→D→B→A

Решение: Скорость оборота капитала n -ого пути судна найдем как суммарную
выгоду пути, деленную на суммарное время, то есть                                                vn = Σai / Σbi.
   1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. v1= . . . . .

Страницы