В центре обработки данных (дата-центре) имеется 18 серверов. Между любыми двумя серверами может быть установлено прямое сетевое соединение (прямой линк). В целях обеспечения требований к отказоустойчивости для любого имеющегося сервера S должны найтись три других, попарно не связанных между собой линками, но каждый связанный с S. Какое наибольшее число линков можно установить в дата-центре?
Для решения этой задачи давайте используем графовую теорию. Мы можем представить серверы как вершины графа, а сетевые соединения (линки) между ними как рёбра. Нам нужно выяснить, какое максимальное количество рёбер (линков) может быть в графе, удовлетворяющем определённым условиям.
Шаг 1: Определим требования к графу
Каждый сервер (вершина) должен иметь три соседа (связанных с ним), которые не имеют прямых соединений между собой. Это означает, что для каждой вершины
Шаг 2: Используем свойства графа
Пусть
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Не нашел нужную задачу?