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