В королевстве $%35$% городов. Некоторые из них соединены прямыми авиарейсами. Известно, что если между городами $%A$% и $%B$% есть прямой авиарейс, и между городами $%B$% и $%C$% есть прямой авиарейс, то между городами $%A$% и $%C$% нет прямого авиарейса. Какое наибольшее количество прямых авиарейсов могло быть в королевстве?

задан 2 Фев '18 18:30

10|600 символов нужно символов осталось
1

В условии рассматривается граф без треугольников на n=35 вершинах. Про максимальное число рёбер графов с таким свойством, всё следует из известной теоремы Турана (а также её частного случая). Если разбить множество вершин на две примерно равные доли (по n/2 вершин для чётного n, и (n-1)/2 и (n+1)/2 для нечётного), и построить двудольный граф, соединяя рёбрами вершины из двух разных доль, то треугольников в нём не будет. Количество рёбер при этом равно [n^2/4]; квадратные скобки означают целую часть. При n=35 получается 306 рёбер.

Приведём доказательство того, что такое число рёбер является максимально возможным. Различных способов доказательства здесь известно много, и на форуме часть из них рассматривалась. Обозначим через k максимальную степень вершины в графе без треугольников. Рассмотрим одну такую вершину v, и пусть она соединена с вершинами v(1), ... , v(k). Поскольку треугольников нет, между этими вершинами соединения отсутствуют. Это значит, что у любого ребра графа (включая уже рассмотренные соединения вида v-v(i)), хотя бы одна из вершин не находится в заданном списке из k вершин, то есть принимает не более n-k значений. Из каждой такой вершины выходит не более k рёбер. Значит, всего рёбер не более k(n-k). При таком способе оценки важно, что каждое ребро мы учли. Тот факт, что некоторые рёбра могли быть учтены дважды, не меняет значения оценки сверху.

Теперь осталось заметить, что k(n-k)=(n/2)^2-(k-n/2)^2<=n^2/4, откуда требуемая оценка следует.

ссылка

отвечен 2 Фев '18 18:58

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×552

задан
2 Фев '18 18:30

показан
712 раз

обновлен
2 Фев '18 18:58

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru