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