Индукция в графах и теорема Турана
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
В графе на 
вершинах любые два нечетных цикла не имеют общих ребер. Найдите максимальное количество ребер в таком
графе.
Подсказка 1
Оценить число ребер сверху легко в графе без треугольников: для этого есть теорема Турана! Тогда у нас есть предполагаемые ответы, и их нужно доказать. Как это можно сделать?
Подсказка 2
Верно! Применим индукцию по n>3. Для n = 1, 2, 3 значения просто находятся счётом, а для n = 4, 5, 6 проверяется непосредственно. Кроме того, в случае графа без треугольников оценка тоже верна. Допустим, что треугольник есть. Хотелось бы его убрать. Что можно сказать о вершинах треугольника, если его убрать?
Подсказка 3
Конечно! Очевидно, они будут в разных компонентах связности! А тогда для каждой компоненты можно применить предположение индукции. Как теперь доказать оценку для исходного графа?
Подсказка 4
Точно! На самом деле можно все компоненты, которые не содержали вершины исходного треугольника, соединить с нашими новыми тремя компонентами. Если a, b, c — количество вершин в наших новых компонентах. Тогда по предположению есть верхняя оценка на число ребер: (a²+3)/4, (b²+3)/4 и (c²+3)/4 соответственно(почему мы можем так усилить?). Добавив 3 удаленных ранее ребра, легко показать нужную оценку на число ребер и в нашем случае. Остается аккуратно разобрать все случаи и понять, какими будут примеры графов с такими числами ребер при каждом n!
Оценка. Обозначим через 
— максимальное количество ребер в таком графе на 
вершинах для каждого натурального 
Имеем
Индукцией по 
докажем, что
 |
База для 
проверяется непосредственно. Пусть оценка верна для всех 
Докажем ее для 
Пусть 
— произвольный граф на 
вершинах, удовлетворяющий условию задачи. Если в 
нет треугольников, то, по теореме
Турана, количество ребер в нем не больше, чем 
и 
для 
и 
соответственно, что дает требуемую
оценку.
Иначе, в 
существует треугольник 
Удалим из 
все его ребра. Заметим, что в полученном графе 
для любой пары вершин
верно, что они лежат в разных компонентах связности в 
иначе в 
существовал некоторый цикл нечетной длины, который
содержал их а так же имел общие ребра с 
, что невозможно.
Таким образом, 
можно разбить на 
подграфа так, что между любой парой подграфов нет ребер. Пусть количество вершин в
каждом из них 
соответственно. Тогда, поскольку
(неравенство при 
следует при непосредственной проверке найденных значений, и при 
из предположения индукции),
количество ребер в 
не превосходит
При 
для доказательства достаточно показать, что
что после раскрытия скобок и приведения подобных дает 
т.е. верно при 
При 
для доказательства достаточно показать, что
что после раскрытия скобок и приведения подобных дает 
т.е. верно при 
Пример. Для 
и 
примером является двудольный граф, разность числа вершин долей которого не превосходит 
Для
примером будет цикл на трех вершинах.
при 
при 
при 
при 
при 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
