В стране есть 3 мегаполиса и 6 городков. Авиакомпания хочет составить расписание полётов между этими населенными пунктами. Руководитель ставит перед собой следующие задачи: необходимо обеспечить возможность добраться от любого населённого пункта до любого другого (как прямыми рейсами, так и с пересадками); если существует рейс из пункта A в пункт B, то должен быть и рейс из пункта B в пункт A; из двух мегаполисов можно улететь ровно в три населённых пункта, а из одного - в четыре; из каждого городка можно улететь ровно в один населённый пункт. Сколько различных способов можно организовать такое расписание?
Математика 10 класс Комбинаторика математика 10 класс задачи на комбинаторику расписание полётов графы в математике мегаполисы и городки авиаперевозки комбинации пересадки количество способов математическая задача Новый
Для решения задачи давайте проанализируем условия и шаг за шагом разберёмся, как можно организовать расписание полётов.
Условие:
Шаги решения:
Определим связи городков с мегаполисами:
Определим связи мегаполисов:
Распределим связи:
Обеспечим двусторонние рейсы:
Рассмотрим комбинации связей:
Проверим связность:
Подсчитаем количество способов:
Таким образом, количество различных способов организовать такое расписание будет равно количеству способов выбрать 3 городка из 6 для связи с мегаполисом A, что равно 20.
Таким образом, ответ: 20 способов.