Задача о Тирексе, который строил сеть наугад
Будет полезна всем, кто хочет попрактиковаться в комбинаторике на графах и лучше понять, как устроены остовные деревья. Рассмотрим вероятностную модель связности для случайного подграфа фиксированной мощности.
Условие
Тирекс построил собственный дата-центр и теперь хочет объединить 15 серверов в одну сеть. Он не задумывается о надежности топологии, поэтому хочет использовать минимально возможное количество кабелей — 14.
Задача
Тирекс случайным образом проложил 14 проводов. С какой вероятностью все серверы будут соединены в одну сеть?
Соединять серверы можно только по доступным путям, то есть по заранее проложенным трассам — они заданы в виде неориентированного графа, где вершины — серверы, а ребра — возможные соединения. Все соединения — двусторонние, то есть провода не имеют направления.
Решение
На старте сеть можно представить в виде неориентированного графа: серверы — вершины, соединения — ребра. Тирекс хочет соединить все вершины с помощью 14 ребер — это минимальное возможное число для связной структуры из 15 вершин. Значит, он стремится (сознательно или нет) построить остовное дерево — связный подграф, который содержит все вершины (n) и ровно n − 1 ребер (в нашем случае: 15 − 1 = 14).
Однако подобных деревьев в рассматриваемой сети может быть много. Чтобы найти вероятность того, что случайный выбор ребер образует остов (остовное дерево), нужно осуществить несколько шагов.
- Посчитать количество подграфов.
- Определить общее количество подграфов с 14 ребрами (без учета связности).
- Разделить первое на второе.
Количество подграфов
Найдем общее число подграфов с 14 ребрами. Всего в графе 21 возможное соединение — каждое ребро можно либо выбрать, либо не выбрать. Нас интересуют только те варианты, где выбраны ровно 14 ребер. Это классическая задача на сочетания без повторений:
Количество остовных деревьев
Определить количество остовных деревьев — задача сложнее: граф слишком большой, чтобы высчитать их количество вручную. Однако заметим важную особенность: на схеме видно, что для любого дерева нужны определенные ребра — они обеспечивают связность между частями и всегда будут входить в остов. Отметим их красным.
В центре графа есть вершина, соединенная одним ребром с другими частями. Формально ее можно считать отдельной компонентой, но она всегда включается в остов через это единственное ребро. Для расчета остовов мы не выделяем отдельно: она «прилипает» к одной из трех компонент — и на итог это не влияет. Аналогично с ребром между второй и третьей компонентой.
Фиксируя общие ребра, мы «склеиваем» три компоненты в одно дерево. Значит, задача сводится к перемножению количества остовов внутри каждой компоненты. Разберем их по очереди.
Первая компонента — это полный граф на четырех вершинах, так как любые две вершины в ней соединены ребром. Количество остовных деревьев для полного графа можно найти с помощью формулы Кэли: T(Kn)=
.
Теорема Кэли о числе деревьев утверждает, что число деревьев с n пронумерованными вершинами равно
В нашем случае: T(K4) = 4⁴⁻².
Вторая компонента обладает произвольной структурой. Сперва для расчета построим матрицу.
Матрица Лапласа — важный инструмент в теории графов. Она лежит в основе спектральной кластеризации, графовых сверток, анализа связности и используется в ML, анализе сетей и распределенных систем.
- По диагонали — степени вершин (количество ребер, исходящих от них).
- Вне диагонали: −1, если вершины связаны, и 0 в остальных случаях.
Далее воспользуемся теоремой Кирхгофа, согласно которой количество остовов равно алгебраическому дополнению любого элемента матрицы. Возьмем его от элемента A_11, а далее — вычислим детерминант матрицы:
- det1 = 3*3*3+(-1)*(-1)*(-1)+(-1)*(-1)*(-1)-3*(-1)*(-1)-3*(-1)*(-1)-3*(-1)*(-1) = (27 — 1 — 1 — 3 — 3 — 3) = 16
- det2 = 3*3*(-1)+(-1)*(-1)*(-1)+0*(-1)*(-1)-3*(-1)*(-1)-3*0*(-1)-(-1)*(-1)*(-1) = -9 — 1 + 0 — 3 — 0 + 1 = -12
- det3 = (-1)*(-1)*(-1)+3*3*(-1)+0*(-1)*(-1)-(-1)*(-1)*(-1)-3*(-1)*(-1)-3*0*(-1) = -1 — 9 + 0 + 1 — 3 — 0 = -12
- det = 3 * 16 — 12 — 12 = 24
Ответ: 24 остова.
Третья компонента — цикл с пятью вершинами. Количество остовов в цикле из n вершин всегда равно n (удаляем по одному ребру, цикл становится деревом): T(C5) = 5.
Подсчитаем общий результат. Для этого перемножим общее количество остовов в каждой компоненте: Tобщий = 16 * 24 * 5 = 1 920. А значит, искомая вероятность равна 1 920/116 280 ≈ 0,0165 или 1,65%.
Ответ и заключение
Вероятность того, что случайно выбранные 14 ребер соединят все серверы — примерно 1,65%.
Подобные задачи полезны всем, кто работает с графами в практике: от инженеров по сетевой инфраструктуре до разработчиков алгоритмов кластеризации. Они помогают почувствовать фундаментальные принципы связности и понять, как устроены сложные распределенные системы. А матрица Лапласа, которая здесь выступает в роли вспомогательного инструмента, используется, например, в машинном обучении и анализе трафика.
