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