Задача на графы Дан связный граф на 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?
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
а) Нет, так как при каждой операции расстояние между выбранными вершинами уменьшается не менее чем на 1.
б) Нет, так как после первой операции максимальное расстояние будет не более 1007 (так как новое ребро соединит две вершины, находящиеся на расстоянии не более 1006), а значит после второй операции максимальное расстояние не превысит 2013.
в) Да, возможно. Например, в начальный момент можно соединить вершины на максимальном расстоянии, затем провести две операции на других вершинах, не влияющих на максимальное расстояние.
г) Нет, так как после первой операции максимальное расстояние между вершинами будет не более 1007 (аналогично случаю б), а значит не сможем получить расстояние больше 1700.