Question

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

Answer 1

Изначально было 30⋅29/2=435 дорог. Для того чтобы из каждого города можно было проехать в каждый достаточно оставить 29 дорог (например, все дороги ведущие из какого-то одного города). Поэтому можно закрыть 435−29=406 дорог.

Answer 2

Чтобы из каждого города можно было проехать в любой другой, необходимо, чтобы граф, представляющий соединения между городами, был связным. Связный граф - это граф, в котором есть путь между любой парой вершин.

В данном случае у нас 30 городов, и каждый город соединен с каждым другим дорогой. Это означает, что у нас полный граф. В полном графе на n вершинах количество ребер равно n * (n - 1) / 2.

Для данного случая с 30 городами количество дорог будет: 30 * (30 - 1) / 2 = 30 * 29 / 2 = 435

Теперь, чтобы определить, сколько дорог можно закрыть на ремонт, чтобы граф оставался связным, нужно посмотреть на минимальное количество ребер, которое нужно удалить, чтобы граф стал деревом. Дерево - это связный ациклический граф.

Для связного графа с n вершинами минимальное количество ребер, чтобы он стал деревом, равно n - 1.

В нашем случае, чтобы граф оставался связным, можно закрыть 30 - 1 = 29 дорог.

Итак, наибольшее количество дорог, которые можно закрыть на ремонт, чтобы из каждого города можно было проехать в любой другой, равно 29.