Дан связный граф на 2016 вершин. За одну операцию можно выбрать две вершины на максимальном (по количеству ребер) расстоянии и соединить ребром. Может ли после N операций максимальное расстояние оказаться больше S при: а) N = 1, S = 1100; б) N = 2, S = 2000; в) N = 3, S = 805; г) N = 1, S = 1700?
Дан связный граф на 2016 вершин. За одну операцию можно выбрать две вершины на максимальном (по количеству ребер) расстоянии и соединить ребром. Может ли после N операций максимальное расстояние оказаться больше S при: а) N = 1, S = 1100; б) N = 2, S = 2000; в) N = 3, S = 805; г) N = 1, S = 1700?
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
а) Да, так как при одной операции максимальное расстояние увеличивается на 1, то после одной операции максимальное расстояние может быть максимум 2016-1=2015, что больше 1100.
б) Нет, так как после двух операций максимальное расстояние увеличивается на 2, то после двух операций максимальное расстояние может быть максимум 2016-2=2014, что меньше 2000.
в) Нет, так как после трех операций максимальное расстояние увеличивается на 3, то после трех операций максимальное расстояние может быть максимум 2016-3=2013, что меньше 805.
г) Да, так как при одной операции максимальное расстояние увеличивается на 1, то после одной операции максимальное расстояние может быть максимум 2016-1=2015, что больше 1700.