Элементы теории графов и их технические приложения - 49 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

49
1578)(),()(
221313
=+=+= xxxlx λλ ;
16151)(),()(
13131414
=+=+= xxxlx λλ ;
281612)(),()(
14141515
=
+=+= xxxlx λλ
;
231310)(),()(
12121616
=
+=+= xxxlx λλ ;
28235)(),()(
16161717
=+=+= xxxlx λλ
;
27243)(),()(
881818
=+=+= xxxlx λλ ;
31274)(),()(
18181919
=+=+= xxxlx λλ ;
322012)(),()(
10102020
=
+=+= xxxlx λλ ;
31283)(),()(
17172121
=+=+= xxxlx λλ .
Кратчайший путь (см. рис. 61) проходит через вершины
axx
n
=
=
21
,
17
x
;
16
x
;
12
x
;
3
x ;
5
x ;
1
x ; bx =
0
; длина его 31),(
=
bal .
Интерес к решению рассмотренной задачи объясняется, прежде всего,
потребностями практики. При изучении объектов и управлении ими формируются
определенные отношения соподчинения. В результате исследования первоначальная
система элементов вместе с установленными в ней связями образуют сеть.
Вершинами сети являются исходные объекты, а ребрами – установленные между
ними связи. Если появляется необходимость в построении
новых пунктов, то
возникает вопрос, как расположить эти пункты в сети с тем, чтобы расстояние до
них от первоначально заданных пунктов было минимальным. Подобные задачи
возникают при выборе наилучшего варианта транспортных, вентиляционных,
электрических сетей, при использовании тарифной системы на телефонных линиях,
определения границ территорий, имеющих различные темпы развития и многих
других
.
Методы, позволяющие решать разные задачи, сходные в некотором смысле по
своему критерию оптимальности тесно связаны с областью математики, известной
под названием сетевого планирования и управления, в основе, которой лежит теория
графов. Эти методы моно разделить на два основных класса: индексные и
матричные.
В основу индексных методов положен принцип индексации, т.
е. принцип
присвоения вершинам графа некоторых индексов, значения которых изменяются в
процессе решения. Эти величины в результате реализации алгоритма определяют
длину пути от фиксированной до рассматриваемой вершины.
Все матричные методы связаны с построением матрицы смежности весов,
элементами которой являются веса соответствующих дуг или ребер. Экстремальные
пути находятся последовательным преобразованием исходной матрицы
смежности.
И те и другие методы могут быть реализованы на ЭВМ.
10. Кратчайший путь на ориентированном графе.
В предыдущем пункте рассматривалась задача определения кратчайшего пути
на графе, ориентация дуг которого не имела определенного смысла. Прикладные
задачи порождают графы, в которых между вершинами существует определенная
зависимость, а ориентация дуг имеет первостепенное значение. Например, задача

Страницы