ВОПРОС 6 ИЗ 6 Задание 5 (5 баллов) В защищенном контуре платежной системы расположено 10 серверов, между которыми проложено 23 физических соединения (кабеля). На каждом сервере размещен один критический сервис. Назовем два сервиса «соседями», если они размещены на серверах, соединенных кабелем. Для повышения безопасности принято решение о миграции: те же 10 сервисов нужно перераспределить по тем же 10 серверам (по одному на сервер). Удастся ли выполнить миграцию так, чтобы если до миграции два сервиса были соседями, то после нее они оказались на несвязанных серверах?

Пошаговое решение:

• Представим себе 10 серверов как вершины графа, а физические соединения между ними – как ребра. У нас есть 23 ребра.
• Допустим, что миграция невозможна. Это значит, что для каждой пары сервисов, которые были соседями до миграции, они должны остаться соседями и после миграции.
• Поскольку до миграции у нас 23 пары сервисов-соседей, то после миграции нужно обеспечить 23 соединения между этими парами.
• Для 10 серверов, чтобы каждая пара была соединена напрямую, потребовалось бы 10 * (10 - 1) / 2 = 45 соединений. У нас всего 23 соединения.
• Но если мы перераспределим сервисы так, что сервисы, бывшие соседями, не будут соседями после миграции, то условие задачи будет выполнено.