Олимпиадная задача по теории графов для 8–10 классов от Федорова Р. М.
Задача
В стране 15 городов, некоторые из них соединены авиалиниями, принадлежащими трём авиакомпаниям. Известно, что даже если любая из авиакомпаний прекратит полеты, можно будет добраться из каждого города в любой другой (возможно, с пересадками), пользуясь рейсами оставшихся двух компаний. Какое наименьшее количество авиалиний может быть в стране?
Решение
Обозначим количество линий у авиакомпаний через a, b и c. Если мы закроем последние c авиалиний, то граф останется связным, поэтому a + b ≥ 14 (см. задачу 131098 г). Аналогично, b + c ≥ 14, c + a ≥ 14. Складывая эти неравенства, получаем: 2(a + b + c) ≥ 42, то есть у трёх компаний в сумме не менее 21 авиалинии.
Осталось привести пример с 21 авиалинией. Годится любой из примеров, показанных на рисунках.
Ответ
21 авиалиния.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь