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

Question 1

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

Question 2

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

Trover_zn · Answer 1 · 2018-03-20T10:05:39+0000

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