В некоторой стране 30 городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в каждый?
В некоторой стране 30 городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в каждый?
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Чтобы из каждого из 30 городов можно было проехать в каждый, необходимо, чтобы граф был полносвязным. В полносвязном графе между n вершинами всего n(n-1)/2 ребер.
Для 30 городов это будет (30*29)/2 = 435 дорог.
Если закрыть 434 дороги, то из каждого города все равно можно будет проехать в каждый остальной, так как граф останется связным.