Математика. Курзина В.М - 232 стр.

UptoLike

ВУЗ: 

МГУЛ | Мытищи

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

Рубрика: 

232
Алгоритм решения
Начнем с любого узла и соединим его с ближайшим узлом сети. Со-
единенные два узла образуют связное множество, а остальные − несвязное.
Далее в несвязном множестве выберем узел, который расположен ближе
других к любому из узлов связного множества. Скорректируем связное и
несвязное множества и будем повторять процесс до тех пор,
пока в связное
множество не попадут все узлы сети. В случае одинаково удаленных узлов
выберем любой из них, что указывает на неоднозначность (альтернатив-
ность) "минимального дерева-остова".
Пример 8.5.1. Автопарк (узел 1) планирует введение автобусных
маршрутов для обслуживания пяти районов новостроек. Числа на ребрах
указывают длину маршрута. Отсутствие ребра между двумя узлами
озна-
чает, что соединение соответствующих новостроек невозможно. Найти та-
кое соединение автобусными маршрутами новостроек, чтобы общая длина
маршрута была минимальной.
3
2 5
1 9
1 5 3 8
7 4
5 10
4 3 6
Рис. 8.22. Условие задачи.
Решение: минимальная длина маршрута: 1 + 3 + 4 + 3 + 5 = 16.
3
2 5
1
1
5 3
4
5
3 6
4
Рис. 8.23. Решение задачи. 
                                                232

                                           Алгоритм решения

      Начнем с любого узла и соединим его с ближайшим узлом сети. Со-
единенные два узла образуют связное множество, а остальные − несвязное.
Далее в несвязном множестве выберем узел, который расположен ближе
других к любому из узлов связного множества. Скорректируем связное и
несвязное множества и будем повторять процесс до тех пор, пока в связное
множество не попадут все узлы сети. В случае одинаково удаленных узлов
выберем любой из них, что указывает на неоднозначность (альтернатив-
ность) "минимального дерева-остова".
      Пример 8.5.1. Автопарк (узел 1) планирует введение автобусных
маршрутов для обслуживания пяти районов новостроек. Числа на ребрах
указывают длину маршрута. Отсутствие ребра между двумя узлами озна-
чает, что соединение соответствующих новостроек невозможно. Найти та-
кое соединение автобусными маршрутами новостроек, чтобы общая длина
маршрута была минимальной.


                                                        3
                                    2                                            5
                  1                             9

              1                             5       3           8
                   7           4
                                   5                                    10

                           4                            3                        6



                                   Рис. 8.22. Условие задачи.

     Решение: минимальная длина маршрута: 1 + 3 + 4 + 3 + 5 = 16.


                                                                    3
                                                2                            5
                                       1

                       1
                                        5                   3
                                                4
                                                        5
                                                                    3            6
                                                4




                                           Рис. 8.23. Решение задачи.

Страницы