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