Question

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

Answer 1

Максимальное количество дорог между 8 городами равно числу сочетаний из 8 элементов по 2:

$C_8^2=\dfrac{8\cdot7}{2} =28$

Рассмотрим условие о наличии двух городов таких, что из первого города во второй можно добраться минимум через два других города.

Обозначим эти города как А и В. Выясним, какие ограничения вводит это условие:

1) Прямой дороги из А в В не существует.

2) Для любого другого (кроме А и В) города Х хотя бы одна дорога из Х в А или из Х в В отсутствует. Это дает возможность утверждать, что никакой город Х не может быть единственным промежуточным на пути из А в В. Если мы приехали в этот город из А (из В), то уехать из него напрямую в В (в А) не получится.

Таким образом, для найденного максимального числа дорог между 8 городами учтем данные два условия:

1) Убираем дорогу АВ. Количество оставшихся дорог:

$28-1=27$

2) Убираем по одной дороге (или в А, или в В) в 6 других городах, не являющихся А или В:

$27-6=21$

Уточнение к пункту 2: "убираемые" дороги не могут одновременно все вести в А или все вести в В, иначе один из городов А или В будет отдельно стоящим. Но это уточнение больше относится не к наибольшему возможному числу дорог, а к структуре этих дорог.

Пример такой схемы (1 - есть дорога, 0, Х - нет дороги):

$\left[\begin{array}{ccccccccc}&A&X_1&X_2&X_3&X_4&X_5&X_6&B\\A&X&1&0&0&0&0&0&0\\X_1&1&X&1&1&1&1&1&0\\ X_2&0&1&X&1&1&1&1&1\\ X_3&0&1&1&X&1&1&1&1\\ X_4&0&1&1&1&X&1&1&1\\ X_5&0&1&1&1&1&X&1&1\\ X_6&0&1&1&1&1&1&X&1\\ B&0&0&1&1&1&1&1&X\\\end{array}\right]$

Ответ: 21