Решение:
1. Определим, что задача сводится к нахождению минимального остовного дерева в графе, где вершины представляют собой отделы, а ребра — стоимость прокладки кабеля между ними.
2. Составим список всех отделов и стоимости прокладки кабеля между каждой парой отделов. Например, пусть у нас есть отделы A, B, C и D, и таблица с их стоимостями:
A-B: 10
A-C: 15
A-D: 20
B-C: 25
B-D: 30
C-D: 35
3. Выберем алгоритм для нахождения минимального остовного дерева. Например, можно использовать алгоритм Краскала или алгоритм Прима. В данном случае воспользуемся алгоритмом Краскала.
4. Отсортируем все ребра по возрастанию стоимости:
1. A-B: 10
2. A-C: 15
3. A-D: 20
4. B-C: 25
5. B-D: 30
6. C-D: 35
5. Начнем добавлять ребра в остовное дерево, начиная с самого дешевого, проверяя, не образуют ли они цикл.
— Добавляем A-B (стоимость 10).
— Добавляем A-C (стоимость 15).
— Добавляем A-D (стоимость 20).
— Ребра B-C, B-D и C-D не добавляем, так как они образуют циклы.
6. Теперь у нас есть соединенные отделы A, B и C, но отдел D также должен быть соединен. Мы добавляем A-D, так как это единственное ребро, которое соединяет D с остальными отделами.
7. Считаем общую стоимость: 10 (A-B) + 15 (A-C) + 20 (A-D) = 45.
8. Таким образом, минимальный бюджет для прокладки интернет-кабеля, чтобы все отделы были связаны, составляет 45.
Ответ: 45