Семинар в ШАД Хелпер: экстремальные задачи на графы

Автор статьи: Канунников Андрей, к. ф.-м. н., преподаватель ШАДХелпер.

В теории графов, как и в других разделах математики, есть экстремальные проблемы. Они происходят как из практических задач, так и из эстетических соображений: найти оптимальное значение той или иной величины может быть и на практике необходимо, и просто любопытно. Многие из таких задач можно встретить на олимпиадах, кружках и экзаменах.

Вот подборка задач, предлагавшихся в разные годы в ШАД. Решения этих и других задач ШАД есть в нашем задачнике.

Задача 1. Дан граф без кратных ребер и петель с вершинами. Известно, что у любого ребра хотя бы одним из концов является вершина, из которой выходит не более других ребер. Какое наибольшее количество ребер может быть в этом графе?

Задача 2. (Усиление теоремы Мантеля 8.) В графе вершин и рёбер, . Докажите, что в этом графе найдутся два треугольника с общим ребром.

Задача 3. В стране городов. Некоторые пары городов соединены авиалиниями. Оказалось, что любые города соединены друг с другом не более чем четырьмя авиалиниями. Какое наибольшее количество авиалиний может быть в этой стране?

Задача 4. В графе 40 вершин. Среди любых пяти найдётся одна, соединённая с четырьмя остальными. Какое наименьшее число рёбер в таком графе?

В этой статье мы покажем очень красивое решение следующей задачи теории графов XX столетия. Некоторые задачи из ШАД являются её вариациями или просто близки по духу.

Основная задача. Какое наибольшее число рёбер может быть в графе на вершинах, в котором нет попарно соединённых вершин, то есть нет -клики?
-клика графа — это полный подграф в .)

Случай тривиальный: тогда в графе вообще не должно быь рёбер. Обсудим вначале подробно случай , то есть запретим в графе треугольники.

Важный класс графов, в котором заведомо нет треугольников, образуют двудольные графы. Так называются графы, вершины которых можно разбить на две группы (доли) так, что рёбрами соединяются только вершины из разных групп. Двудольный граф с долями с и вершин, в котором любые две вершины из разных долей соединены, обозначается и называется полным двудольным графом. Примеры:

Задача 5. Сколько рёбер в графе ?

Решение

Каждая из вершин соединяется с каждой из вершин — всего рёбер.

Ответ: .

Задача 6. В классе 20 человек. На 8 марта каждый мальчик подарил каждой девочке цветок. Какое наибольшее число цветов могло быть подарено?

Решение

Если девочек и мальчиков поровну — по 10, то согласно предыдущей задаче, подаренных цветов всего . Если бы мальчиков и девочек было, скажем, 9 и 11, то цветов было бы , что меньше. Перебирать все возможные случаи смысла нет. Пусть мальчиков , тогда девочек , а цветов

Ответ: .

ЗАМЕЧАНИЕ. Сравните с задачей о поиске наибольшей площади среди прямоугольниов с фиксированным периметром.

Задача 7. Обобщите задачу 6, доказав, что среди двудольных графов на вершинах наибольшее число рёбер, равное , имеет граф при чётном и граф при нечётном .

Решение

Покажем другое рассуждение. Достаточно доказать, что при фиксированной сумме произведение принимает наибольшее значение, когда числа и отличаются не более чем на 1. Предположим противное. Пусть, скажем, . Тогда произведение увеличится, если увеличить на 1, а уменьшить на 1:

Из этой задачи ещё не вытекает теорема Турана при , так как если в графе нет треугольников, то это не значит, что он двудольный. Пример: цикл нечётной длины.

ЗАМЕЧАНИЕ. Несложно показать, что граф двудольный, если и только если в нём нет циклов нечётной длины.

Задача 8. Теорема Мантеля (1907). Наибольшее число рёбер в графе на вершинах, в котором нет треугольников, равно и реализуется на графе из задачи 7.

Доказательство Эрдёша.

Пусть — данный граф на вершинах , в котором нет треугольников. Можно считать, что — вершина наибольшей степени и что соединена с вершинами , назовём их красными. Остальные вершины (включая ) назовём синими. Красные вершины не соединены рёбрами, иначе в был бы треугольник вида .

Пусть — число рёбер с синими концами, — число рёбер с разноцветными концами. Тогда , а сумма степеней всех синих вершин, с одной стороны, не больше , а с другой, равна . Отсюда
для общего числа рёбер имеем оценку

Первое неравенство обращается в равенство в точности при , то есть — двудольный граф, поэтому мы вправе воспользоваться задачей 7.

Перейдём к случаю любого . Итак, нам надо соединить вершин максимальным числом рёбер так, чтобы не было попарно соединённых вершин. Аналогично случаю треугольников, заведомо подойдёт -дольный граф при , то есть граф, вершины которого можно разбить на групп так, что вершины внутри групп не соединены.
В самом деле, -дольный граф не может содержать полного подграфа по принципу Дирихле (в противном случае две вершины из должны были бы оказаться в одной доле, что невозможно по определению -дольного графа.

Полный -дольный граф — это -дольный граф с долями из вершин, в котором любые две вершины из разных долей соединены. Пример:

Задача 9. Сколько рёбер в графе ?

Ответ

.

Задача 10. Докажите, что при фиксированной сумме число рёбер в графе максимально в точности тогда, когда числа {it почти равны}, то есть любые два из них отличаются не более чем на 1.
В этом случае граф называется графом Турана и обозначается (числа определены однозначно, так как равны , где и — неполное частное и остаток от деления на

Примеры: , , .

Решение

Предположим, что для некоторых и . Перекинув одну вершину из -й доли в -ю, мы увеличим число рёбер на

Задача 11. Докажите, что число рёбер в графе Турана равно

Переходим к самому интересному.

Теорема Турана (1941). Среди всех графов на вершинах, не содержащих полного подграфа , наибольшее число рёбер имеет граф Турана .

Можно провести доказательство Эрдёша так же, как в теореме Мантеля 8, но мы проведём изумительное по красоте доказательство Зыкова.

Доказательство Зыкова теоремы Турана.

Пусть — граф с наибольшим числом рёбер среди всех графов на вершинах, не содержащих . Нам достаточно доказать, что граф многодольный: тогда в нём не более долей, а среди -дольных графов максимальное число рёбер достигается на графе Турана в силу задачи 10 (в которой какие-то из могут быть нулями).

Многодольный граф характеризуется тем, что «не смежность его вершин» транзитивна, то есть если вершины и не соединены с , то они не соединены и друг с другом.

Задача 12. Если это не очевидно, проведите подробное рассуждение.

Решение

Последовательно докажем, что граф обладает свойствами:

любые две несмежные вершины в имеют одинаковую степень;

«несмежность вершин» в транзитивна ( граф многодольный).

Предположим, что неверно, то есть в есть две не смежные вершины и и . Заменим вершину копией вершины (то есть удалим все рёбра, выходящие из и вместо них проведём рёбра из во все вершины, смежные с ):

Легко видеть, что в полученном графе рёбер больше, а -клики не появилось, что противоречит максимальности числа рёбер в .

Задача 13. Докажите аккуратно, что -клики не появилось.

Решение

Если бы в новом графе появилась -клика, то она обязательно содержала бы вершину (так как новые рёбра появились только из ), а тогда не содержала бы (так как и не соединены, а в клике все вершины соединены). Но поскольку и в соединены с одними и теми же вершинами, то в клике можно заменить на и получить клику уже в . Противоречие.

Итак, любые две не смежные вершины в имеют одинаковую степень. Докажем теперь свойство .

Предположим, что в графе есть такие вершины , что не соединена с и , но и соединены между собой. Заменим и копиями вершины :

Число рёбер увеличится на 1, а -клики не появится (проведите подробное рассуждение как в задаче 13). Противоречие.

Источник: habr.com