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