Задание по информатике Джеймс Бонд занимается организацией каналов связи для двадцати секретных агентов МИ-6. Ему нужно, чтобы
между любыми двумя секретными агентами было не более одного прямого канала связи (прямой канал – то есть, без передачи информации через других агентов)
он мог сообщить информацию любому агенту, и по каналам связи эта информация добралась до всех остальных (не обязательно напрямую, можно через агентов)
если каких-то двух агентов рассекречивали, то без них и каналов связи, в которых эти два агента участвовали, все равно сохранялась возможность передачи информации между любыми двумя оставшимися агентами (хотя бы по цепочке через остальных).
Какое наименьшее количество каналов связи нужно Джеймсу Бонду для организации такой системы?
Никто, кроме двадцати агентов, в передаче информации не участвует. Каналы, по которым информацию агентам передает сам Бонд, не считаем.
Задание по информатике Джеймс Бонд занимается организацией каналов связи для двадцати секретных агентов МИ-6. Ему нужно, чтобы
между любыми двумя секретными агентами было не более одного прямого канала связи (прямой канал – то есть, без передачи информации через других агентов)
он мог сообщить информацию любому агенту, и по каналам связи эта информация добралась до всех остальных (не обязательно напрямую, можно через агентов)
если каких-то двух агентов рассекречивали, то без них и каналов связи, в которых эти два агента участвовали, все равно сохранялась возможность передачи информации между любыми двумя оставшимися агентами (хотя бы по цепочке через остальных).
Какое наименьшее количество каналов связи нужно Джеймсу Бонду для организации такой системы?
Никто, кроме двадцати агентов, в передаче информации не участвует. Каналы, по которым информацию агентам передает сам Бонд, не считаем.
между любыми двумя секретными агентами было не более одного прямого канала связи (прямой канал – то есть, без передачи информации через других агентов)
он мог сообщить информацию любому агенту, и по каналам связи эта информация добралась до всех остальных (не обязательно напрямую, можно через агентов)
если каких-то двух агентов рассекречивали, то без них и каналов связи, в которых эти два агента участвовали, все равно сохранялась возможность передачи информации между любыми двумя оставшимися агентами (хотя бы по цепочке через остальных).
Какое наименьшее количество каналов связи нужно Джеймсу Бонду для организации такой системы?
Никто, кроме двадцати агентов, в передаче информации не участвует. Каналы, по которым информацию агентам передает сам Бонд, не считаем.
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для того, чтобы обеспечить выполнение всех условий задачи, достаточно построить полный граф Крейгора с вершинами, соответствующими секретным агентам. В таком графе каждая вершина соединена с другой ребром, а ребра не пересекаются.
Полный граф Крейгора с 20 вершинами имеет ${20 \choose 2} = 190$ рёбер. Таким образом, наименьшее количество каналов связи, которое нужно Джеймсу Бонду для организации такой системы, равно 190.