• В
    Курляндии 34 города, причем каждый с каждым соединен дорогой. Какое наибольшее
    количество дорог можно закрыть на ремонт, чтобы из каждого города по прежнему
    можно было проехать в каждый?

Ответы 1

  • Имеем полный граф с 34 вершинами. Количество дорог равно количеству рёбер такого графаN=\frac{34\cdot(34-1)}2=17\cdot33=561Для того, чтобы из каждого города можно было проехать в каждый, нужно оставить всего 33 дороги. Например, путь из первого города в 34-й будет проходить через все города со второго до 33-го.Значит, максимально можно закрыть на ремонт 561-33 = 528 дорог.
  • Добавить свой ответ

Войти через Google

или

Забыли пароль?

У меня нет аккаунта, я хочу Зарегистрироваться

How much to ban the user?
1 hour 1 day 100 years