Задача 071 — Задачи на Графы

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

Подсказка

Каждые два селения, не соединенные дорогой, соединим телеграфным проводом. По закону в графстве нет двух селений, каждое из которых соединено с остальными селениями дорогами.

Решение

Ответ: $\frac{1}{2} \cdot 100 \cdot 98=4900$ .
Решение. Оценка. Каждые два селения, не соединенные дорогой, соединим телеграфным проводом. По закону в графстве нет двух селений, каждое из которых соединено с остальными селениями дорогами. Значит, по крайней мере из 99 селений выходит хотя бы один телеграфный провод. Тогда имеется не менее 50 проводов, и количество дорог не больше разности чисел $\frac{1}{2} \cdot 100 \cdot 99=4950$ (число дорог в полном графе) и 50 (число проводов, которые заменяют собой некоторые «несостоявшиеся» дороги). Пример. Разобьем селения произвольным образом на пары, каждое селение соединим дорогами со всеми остальными, кроме парного ему.