В теории графов, как и в других разделах математики, есть экстремальные проблемы. Они происходят как из практических задач, так и из эстетических соображений: найти оптимальное значение той или иной величины может быть и на практике необходимо, и просто любопытно. Многие из таких задач можно встретить на олимпиадах, кружках и экзаменах. Вот подборка задач, предлагавшихся в разные годы в ШАД. Решения этих и других задач ШАД есть в нашем задачнике.Задача 1. Дан граф без кратных ребер и петель с вершинами. Известно, что у любого ребра хотя бы одним из концов является вершина, из которой выходит не более других ребер. Какое наибольшее количество ребер может быть в этом графе?Задача 2. (Усиление теоремы Мантеля 8.) В графе вершин и рёбер, . Докажите, что в этом графе найдутся два треугольника с общим ребром.Задача 3. В стране городов. Некоторые пары городов соединены авиалиниями. Оказалось, что любые города соединены друг с другом не более чем четырьмя авиалиниями. Какое наибольшее количество авиалиний может быть в этой стране?Задача 4. В графе 40 вершин. Среди любых пяти найдётся одна, соединённая с четырьмя остальными. Какое наименьшее число рёбер в таком графе?В этой статье мы покажем очень красивое решение следующей задачи теории графов XX столетия. Некоторые задачи из ШАД являются её вариациями или просто близки по духу. Читать далее