В стане есть 8 городов, некоторые из них связаны между собой дорогами. В стране есть два таких города, что из первого города во второй можно добраться минимум только через два других города. Какое наибольшее число дорог может быть в стране?
Ответы
Максимальное количество дорог между 8 городами равно числу сочетаний из 8 элементов по 2:
Рассмотрим условие о наличии двух городов таких, что из первого города во второй можно добраться минимум через два других города.
Обозначим эти города как А и В. Выясним, какие ограничения вводит это условие:
1) Прямой дороги из А в В не существует.
2) Для любого другого (кроме А и В) города Х хотя бы одна дорога из Х в А или из Х в В отсутствует. Это дает возможность утверждать, что никакой город Х не может быть единственным промежуточным на пути из А в В. Если мы приехали в этот город из А (из В), то уехать из него напрямую в В (в А) не получится.
Таким образом, для найденного максимального числа дорог между 8 городами учтем данные два условия:
1) Убираем дорогу АВ. Количество оставшихся дорог:
2) Убираем по одной дороге (или в А, или в В) в 6 других городах, не являющихся А или В:
Уточнение к пункту 2: "убираемые" дороги не могут одновременно все вести в А или все вести в В, иначе один из городов А или В будет отдельно стоящим. Но это уточнение больше относится не к наибольшему возможному числу дорог, а к структуре этих дорог.
Пример такой схемы (1 - есть дорога, 0, Х - нет дороги):
Ответ: 21