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

Наибольшее число дорог — 21.

Пояснение: Чтобы два города (назовём их A и B) находились на расстоянии не менее 3, они не должны быть соединены напрямую, и у них не должно быть общих соседей. Значит, каждый из остальных 6 городов может быть соединён не более чем с одним из этих двух. Если разбить 6 городов на две группы — соседей A и соседей B, то все рёбра внутри групп, между группами и от A к его соседям, от B к его соседям можно провести. Это даёт 21 дорогу. Больше 21 нельзя, так как из полного графа (28 рёбер) пришлось бы удалить минимум 7 рёбер.

0 0 Пожаловаться