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