В лаборатории несколько узлов сети — известны их координаты. Некоторые соседние узлы надо соединить отрезком кабеля так, чтобы каждый был соединён хотя бы с одним другим.
Вот так, например, можно соединить узлы 1, 2, 4, 10, 11 и 12. Общая длина всех отрезков равна 5. Сократить её ещё невозможно.
С помощью отрезков соедини точки 1, 5, 7, 12 так, чтобы каждая соединялась хотя бы с одной другой. Суммарная длина отрезков должна быть минимальной. С помощью отрезков соедини точки 1, 3, 6, 8, 13.
Arnfinn изменил статус на опубликованный 09.02.2023
1 Ответ
У нашего эксперта получился вот такой ответ.
точки 1, 5, 7, 12
точки 1, 3, 6, 8, 13
точки 1, 4, 6, 8, 11, 13, 16
Arnfinn изменил статус на опубликованный 09.02.2023