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