Операция выполнена!
Закрыть
Хабы: Математика

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

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

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

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

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

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

Читать далее
Читайте также
СТАТЬ АВТОРОМ
НОВОСТИ

ПИШИТЕ

Техническая поддержка проекта ВсеТут

info@vsetut.pro