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

Ход решения:

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