Данная задача сводится к нахождению минимального остовного дерева в графе. Граф представляет собой отделы компании, а ребра графа – стоимость прокладки интернет-кабеля между отделами.
Шаги решения:
1. Построить граф, где вершинами будут отделы компании, а ребра – стоимость прокладки интернет-кабеля между отделами.
2. Применить алгоритм Краскала или Прима для нахождения минимального остовного дерева в графе.
3. Просуммировать стоимости всех выбранных ребер в минимальном остовном дереве.
4. Полученная сумма будет являться минимальным бюджетом, необходимым для прокладки интернет-кабеля между всеми отделами компании.
Например, если граф представлен таблицей:
| A | B | C
–+—+—+—
A | 0 | 1 | 2
B | 1 | 0 | 3
C | 2 | 3 | 0
Построим граф:
A — 1 — B
| |
2 3
| |
C ——–
Применяем алгоритм Краскала или Прима и получаем минимальное остовное дерево:
A — 1 — B
|
3
|
C
Суммируем стоимости выбранных ребер: 1 + 3 = 4.
Ответ: 4.
Таким образом, минимальный бюджет, необходимый для прокладки интернет-кабеля между всеми отделами компании, равен 4.