В школу No207 привезли новые компьютеры. Их установили в разных кабинетах и теперь необходимо их соединить в общую школьную локальную сеть. Для этого учитель с учениками составили карту расстановки компьютеров. Получилась схема на рисунке.Расстояние между узлами сетки равняется 100 метров. Каждый компьютер нужно подключить хотя бы к одному другому компьютеру, а кабель необходимо прокладывать вдоль линий сетки учителю посчитать минимально возможную длину кабеля, который нужно приобрести, чтобы все компьютеры подключить к сети. В ответ укажите одно число. Например –1234.
Для нахождения минимального остовного дерева существует несколько алгоритмов, одним из которых является алгоритм Прима.
Шаги решения задачи:
1. Начинаем с произвольной вершины графа, например, A.
2. Помещаем вершину A в остовное дерево.
3. Находим ребро минимального веса, которое связывает вершину A уже включенную в остовное дерево с вершиной, еще не включенной в остовное дерево. Пусть это ребро соединяет вершины A и B.
4. Добавляем вершину B в остовное дерево.
5. Повторяем шаги 3-4 до тех пор, пока все вершины не будут включены в остовное дерево.
6. Вычисляем сумму весов всех выбранных ребер - это и будет минимальной длиной кабеля, который нужно приобрести.
Применяя алгоритм Прима к данной задаче, мы исключаем ребра, которые создают циклы, и соединяем все компьютеры между собой, минимизируя длину кабеля.
На рисунке, приведенном в условии, представлено 9 вершин-компьютеров. Следовательно, нам необходимо двигаться от одной вершины к другой, чтобы их соединить. Изначально выберем произвольную вершину, например, вершину A.
Применяя алгоритм Прима, получим следующие шаги:
1. Начинаем с вершины A.
2. Выбираем ребро минимального веса из A. Пусть это будет ребро A-B.
3. Переходим к вершине B.
4. Выбираем ребро минимального веса из B. Возможные варианты - B-D или B-E. Пусть выбрано ребро B-D.
5. Переходим к вершине D.
6. Выбираем ребро минимального веса из D. Возможные варианты - D-F или D-G. Пусть выбрано ребро D-F.
7. Переходим к вершине F.
8. Выбираем ребро минимального веса из F. Единственный вариант - F-I.
9. Переходим к вершине I.
10. Выбираем ребро минимального веса из I. Ребро I-H.
11. Переходим к вершине H.
12. Выбираем ребро минимального веса из H. Единственный вариант - H-C.
13. Переходим к вершине C.
14. Выбираем ребро минимального веса из C. Единственный вариант - C-E.
15. Переходим к вершине E.
16. Выбираем ребро минимального веса из E. Ребро E-G.
17. Переходим к вершине G.
18. Выбираем ребро минимального веса из G. Ребро G-B.
Теперь мы соединили все компьютеры сети с помощью минимальной длины кабеля. Осталось только посчитать сумму весов выбранных ребер.
Weight(A-B) = 100
Weight(B-D) = 100
Weight(D-F) = 100
Weight(F-I) = 100
Weight(I-H) = 100
Weight(H-C) = 100
Weight(C-E) = 100
Weight(E-G) = 100
Weight(G-B) = 100
Сумма весов всех ребер равна 100 + 100 + 100 + 100 + 100 + 100 + 100 + 100 + 100 = 900.
Ответ: минимально возможная длина кабеля, которую нужно приобрести, равна 900.