Noname
Гений
(69519)
4 года назад
Для начала каким-нибудь образом выберем из графа некоторое количество вершин. Все вершины, что мы выбрали, назовем "набор вершин S" (ну или подмножество, мне удобнее набор).
Теперь рассмотрим все оставшиеся вершины, которые мы не выбрали.
Возьмем из всех не выбранных нами вершин первую. Назовем ее вершина A1. Теперь найдем из нашего набора S вершину, которая будет находится ближе всех к вершине А1. Найдем расстояние от этой самой близкой вершины до вершины А1. Запишем это расстояние в переменную M1.
Теперь возьмем из всех не выбранных нами вершин вторую. Проделаем с ней то же самое. Получим расстояние M2.
И так далее, для 3й, 4й вершины, пока не переберем все вершины, которые мы не выбрали.
Получили набор расстояний M1,M2,M3,М4....
По условию еще было задано кое-какое число. Поместим его в переменную L. Так вот, если мы из нашего графа выбрали вершины правильным образом, должно должно оказаться так, что M1<L и M2<L и M3<L и M4<L и т. д.
Уж не знаю, как проще. Разве что рисунок рисовать... Надеюсь понятно объяснил.