В стране 31 город, некоторые из них соединены авиалиниями, принадлежащими трем авиакомпаниям. Известно, что даже если любая из авиакомпаний прекратит полеты, можно будет добраться из любого города в любой другой (возможно, с пересадками), пользуясь рейсами оставшихся двух компаний. Какое наименьшее количество авиалиний может быть в стране?
Рассмотрим 31 город как вершины графа, а авиалинии – как рёбра, приписанные одной из трёх авиакомпаний. Обозначим множества рёбер для каждой компании как E₁, E₂ и E₃. Общее число авиалиний есть |E₁| + |E₂| + |E₃|. Нам дано условие, что при исключении рёбер любой одной компании (например, отказ E₁) граф с рёбрами E₂ ∪ E₃ остаётся связным. То есть для каждой пары оставшихся компаний объединение их рёбер должно содержать связающее поддерево (охватывающее все 31 город) – то есть, как минимум, 30 рёбер. Аналогичные условия должны выполняться и для пар (E₁, E₃) и (E₁, E₂).
Таким обра...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
