Хакерранк головоломка. Сколько ребер необходимо, чтобы случайный граф стал связным

Question

Это загадка интервью:

У нас есть страна, содержащая N городов.Каждый день мы выбираем 2 города так, чтобы между ними не было дороги, и строим дорогу между ними.Мы выбираем каждую пару несмежных городов с равной вероятностью.Пусть X будет количеством дней, прежде чем мы получим подключенную страну.Каково ожидаемое значение X?Выведите целую часть ответа.

Они действительно спрашивают, какое количество ребер m нужно (в среднем), чтобы случайный граф G (n, m) стал связным.

После написания программы, которая фактически выполняла эксперимент, я придумал это «решение», которое проходит 9/10 тестов

$f = fopen('php://stdin', 'r');
$n = intval(fgets($f));
echo round(1.25 * $n * log($n, 10));

Так можно ли решить его с помощью одной формулы?Как правильно найти вероятность связности случайного графа?

Answer 1

Вам следует ознакомиться с классической статьей Эрдоса и Реньи 1960 года, озаглавленной "Об эволюции случайных графов" .Он содержит полные вероятностные оценки для числа компонентов, размера самых крупных компонентов и т. Д.

Вот немного математических настроек, с которых можно начать.

Пусть G(n,m) будетпростой случайный граф на n вершинах с m ребрами.Пусть X_k будет количеством добавленных ребер, пока есть k подключенных компонентов, пока не будет k-1 подключенных компонентов.Например, изначально есть n подключенных компонентов, поэтому добавление первого ребра приводит к n-1 подключенным компонентам, таким образом X_n = 1.Аналогично, второе ребро также удаляет компонент (хотя это происходит одним из двух способов), так что X_n-1 = 1 также.Определите

X = X_n + X_n-1 + ... + X_2

Цель состоит в том, чтобы вычислить E(X), ожидаемое значение X.По аддитивности у нас есть

E(X) = E(X_n) + E(X_n-1) + ... + E(X_2) 

Нетрудно показать, что вероятность того, что добавленное ребро при наличии k компонентов уменьшает число компонентов, имеет нижнюю границу (k-1)/(n-1).Поскольку X_k является случайной величиной с вероятностью успеха, заданной этой величиной, нижняя граница дает верхнюю границу для ожидания X_k:

E(X_k) <= (n-1)/(k-1)

Объединяя это, мы получаем асимптотическую верхнюю границудля E(X) на n log n.

Немного больше работы и некоторые подсказки из статьи Эрдош-Реньи, и вы, вероятно, сможете получить точную формулу.

Answer 2

ОП - отличное решение, и с небольшой модификацией формулы оно всегда будет проходить.

$f = fopen('php://stdin', 'r');   
$n = intval(fgets($f));  
echo round(1.249 * $n * log($n, 10));// constant factor is changed