Математическое моделирование на графах. Часть 1. Берцун В.Н. - 37 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

Глава 1. Основные понятия теории графов 37
пища
2
1
4
3
7
5
6
2
3
1
0
7
5
6
3
4
1
5
6
3
4
3
7
6
5
5
7
5
7
5
7
5
7
5
7
7
а
б
Рис. 1.42
С задачей о нахождении минимального остовного дерева (МОД),
которую можно решить с помощью «жадного» алгоритма Дейкстры
– Прима [23], тесно связана задача Штейнера о кратчайшем соеди-
нении (по сумме расстояний) точек на плоскости [16]. При решении
этой задачи разрешается к исходному графу добавлять новые вер-
шины (точки Штейнера) с целью обеспечения минимальной суммы
расстояний. Частным случаем этой постановки является задача Тор-
ричелли – Ферма: в треугольнике АВС найти точку Р такую, чтобы
сумма расстояний от Р до вершин А, В, С была минимальной [18].
Известно, что в этом случае все три угла в точке Р, образованные
прямыми РА, РВ, РС, равны 120°.

Страницы