Две задачи на применение графов. Задача о кратчайшем пути между двумя пунктами

• Название: Задача о кратчайшем пути между двумя пунктами
• Анкор: Две задачи на применение графов
• Дата: 27.01.2021
• Размер: 240.88 Kb.
• Имя файла: Две задачи на применение графов.pdf
• Тип: Задача; #171701

Задача о кратчайшем пути между двумя пунктами.
Известна схема дорог (граф). Требуется перевезти груз из одного пункта в другой по маршруту минимальной длины.
Алгоритм действий.
1) Двигаясь от конечного пункта к начальному, каждой вершине припишем число по определенным правилам. Конечной вершине припишем число 0.
2) Если i-тая вершина в направлении от начального пункта к конечному пункту непосредственно соединена с вершинами j
1
, .., j
k
, которым приписаны числа r(j
1
), …, r( j
k
), то вершине i приписываем число r(i)= min(r( j
s
) + t(i, j
s
)), где t(i, j
s
) – длина ребра (i, j
s
).
Пусть этот минимум достигается для вершины j
m
, тогда ребро (i, j
m
) покажем двумя чертами со стрелкой от i до j
m
. (или жирной линией со стрелкой). Если таких j
m
несколько, то на этом шаге будет несколько двойных ребер.
3) Число, приписанное начальному пункту, полученное в конце, равно минимальной длине искомого маршрута. Это маршрут – движение от начального пункта по двойным (жирным) ребрам со стрелками.
Пример 1.
Найти маршрут минимальной длины при перевозке груза из пункта 1 в пункт 11.
Граф дорог с расстояниями изображен на рисунке. Населенные пункты пронумерованы.
Решение.
1) Припишем вершинам числа вместо номеров. Конечной вершине, то есть 11-той, припишем число 0 .
2) 11-ая вершина соединена с 8-ой, 9-ой, 10-ой, которым припишем соответственно числа:
0+5=5, 0+5 = 5, 0+4 =4. Все эти ребра (
11,8
), (
11,9
), (
11, 10
) покажем жирными чертами со стрелками.
11
1
4
3
2
6
5
10
9
8
7
7 1
7 5
7 4
6 2
5 5
8 8
4 4
2 3
3 6
0
5
5
4

3) По числам 8-ой и 9-ой вершин найдем число 5-ой вершины: min (5+7, 5+8)=12, следовательно, ребро (
5,8
) изобразим жирной линией со стрелкой.
4) По числам 9-ой и 10-ой вершин найдем число 6-ой вершины: min (5+7, 4+3)=7, следовательно, ребро (
6,10
) изобразим жирной линией со стрелкой:
5) По тем же числам 9-ой и 10-ой вершин найдем число 7-ой вершины: min (5+4, 4+6)=9, следовательно, ребро (
7,9
) изобразим жирной линией со стрелкой:
6) По числу 5-ой вершины определим число 2-ой вершины ( к ней идет один путь):
12+7=19, следовательно, ребро (
2,5
) изобразим жирной линией со стрелкой:
7) По числам 5-ой, 6-ой, 7-ой вершин определим число 3-ей вершины min (12+2, 9+2, 7+6) =11, следовательно, ребро (
3,7
) изобразим жирной линией со стрелкой:
5
0
5
4
12
5
0
5
4
12
7
5
0
5
4
12
7
9
5
0
5
4
7
9
12
19

8) По числам 6-ой и 7-ой вершин определим число 4-ой вершины min (7+3, 9+8) =10, следовательно, ребро (
4,6
) изобразим жирной линией со стрелкой:
9) По числам 2-ой, 3-ей и 4-ой вершин определим число 1-ой вершины min (19+1, 11+5, 10+4) =14, следовательно, ребро (
1,4
) изобразим жирной линией со стрелкой:
10) Пришли в начальную вершину
1
. Двигаясь из начальной вершины к конечной вершине по ребрам со стрелкой получим кратчайший маршрут (путь)
1 – 4 – 6 – 10 - 11
длины
14
Итоговый граф:
5
0
5
4
7
9
12
19
11
5
0
5
4
7
9
12
19
11
10
5
0
5
4
7
9
12
19
11
10
14
11
1
4
3
2
6
5
10
9
8
7
7 1
7 5
7 4
6 2
5 5
8 8
4 4
2 3
3 6

Пример 2. Найти маршрут минимальной длины при перевозке груза из пункта 1 в пункт 10. Граф дорог с расстояниями изображен на рисунке. Населенные пункты пронумерованы.
Ответ: два пути: 1 – 4 – 6 – 9 - 10 и 1 – 2 – 6 – 9 – 10 длиной 16.
Задача о построении коммуникационной сети минимальной длины.
Коммуникационная сеть минимальной длины или дерево кратчайших расстояний – это совокупность дуг сети, имеющая минимальную суммарную длину и обеспечивающая достижение всех узлов сети, то есть возможность попасть из любого узла в любой другой узел.
Алгоритм построения
1) Начинаем построение с любого узла и соединяем его (жирной линией) с ближайшим узлом.
Считаем, то это связные узлы, а все другие узлы несвязные.
(Две вершины связные, если существует путь, их соединяющий, то есть с концами в этих вершинах)
2) Определим несвязный узел, ближайший к одному из связных узлов. Если таких
«ближайших» узлов несколько, то выбираем любой. Добавим этот узел к связным. И т.д. до тех пор, пока есть несвязные узлы.
Пример 1. Университет установил компьютерную систему электронной почты, которая позволит передавать сообщения между деканатами восьми факультетов. Сеть возможных электронных связей между деканатами изображена графом.
Протяженность коммуникаций в километрах отмечена на ребрах. Требуется предложить проект системы связи, которая позволит всем восьми деканатам обеспечить доступ к системе электронной почты. Решение должно обеспечить минимально возможную общую длину коммуникаций.
10
1
2
3
4
6
7
9
8
5
8 3
8 9
3 8
2 7
4 1
6 6
2 4
8 2
3 8
1
4
3
2
6
7
8
5
3 2
1,2 2
0,5 3
3 4
1,6 4
2,5 1,5 5
1 1
1

Решение.
Рассмотрим узел 1. Ближайший к нему узел 2. Считаем, что 1 и 2 – связные узлы. Отметим это жирной линией.
Ближайшие несвязные узлы к одному из связных узлов 1 и 2 – это узлы 3 и 6. Пояснение: из 4 –
го и 3-го узлов ближайший к 1-му – это 3; из 3 –го и 6-го узлов ближайший ко 2-му – это 6.
Расстояние до них одинаковое и равное 3. Выберем любой из узлов 3 и 6, например, 3. Тогда ребро (1,3) выделяем жирной чертой и считаем узлы 1, 2, 3 связными.
Далее ищем ближайший несвязный узел к узлам 1, 2. 3. Это 7.
И т.д. В результате получаем минимальное дерево. Его длина равна сумме расстояний на ребрах. То есть 2 + 3 + 1 + 1 + 0,5 + 1 + 2 = 10,5 км.
6
6
1
4
3
2
7
8
5
3 2
1,2 2
0,5 3
4 1,6 4
2,5 1,5 5
1 1
1 3
1
4
3
2
7
8
5
3 2
1,2 2
0,5 3
4 1,6 4
2,5 1,5 5
1 1
1
6
3
1
4
3
2
7
8
5
3 2
1,2 2
0,5 3
4 1,6 4
2,5 1,5 5
1 1
1 3