Провайдер планирует связать 12 домов микрорайона единой локальной сетью.
Все возможные варианты прокладки кабеля с указанием требуемой длины показаны на рисунке.
Для функционирования сети необходимо, чтобы к каждому дому был подведён по крайней мере один кабель.
Рис. 1. Схема сети
Какой может быть минимальная суммарная длина проложенного кабеля?
Решение
Для решения задачи может использоваться алгоритм Краскала.
Задания ЕГЭ
Скачать PDF