В некоторой стране есть семь городов, соединённых дорогами. Рассмотрим граф: пусть города — это вершины графа. Будем соединять две вершины ребром, если два соответствующих города соединены дорогой. Какое минимальное количество дорог надо закрыть, чтобы хотя бы из трёх городов нельзя было никуда добраться?
15
Пошаговое объяснение:
Непонятно какой граф. Будем считать, что простой полный неориентированный. Тогда закроем 6 дорог из первого города, 5 дорог из второго (шестая - из города 1 в город 2 - была закрыта на предыдущем шагу) и 4 дороги из третьего.