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