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