Задачка о генерации случайного связного графа

Дано
N - количество вершин (N>0)
M - количество ребёр (N-1<=M<=N*(N-1))
Необходимо написать функцию, сгенерирует случайный связный граф и заполнит два массива
int C[N] - количество соседей
int* E[N] - список соседей
Например для графа с 4мя вершинами {0,1,2,3} и ребрами {0-1,1-2,1-3,2-3} содержимое массивов C и E должно быть таким:
C={1,3,2,2}
E={
{1},//соседи 0й вершины
{0,2,3},//соседи 1й вершины
{1,3},//соседи 2й вершины
{1,2}//соседи 3й вершины
}
списки соседей упорядочивать не обязательно.

Для любого ребра вероятность попасть в граф должна быть одинаковой. Ребер начинающихся и заканчивающихся в одной и той же вершине быть не должно. Алгоритмом со сложностью O(N^2) задача решается легко, а можно ли решить её за O(N+M)?

 

Пусть A - множество вершин, уже связанных графом (в начале A == {}), а B - множество всех остальных вершин (в начале |B| = N).

Код (Text):

1. C := случайная вершина из B;
2. удали C из B;
3. добавь C в A;
4.  
5. while(B != {}) {
6.        C := случайная вершина из B;
7.        D := случайная вершина из A;
8.        свяжи C и D ребром;
9.        удали C из B;
10.        добавь C в A;
11. }
12.  
13. if(M > N-1) {
14.       repeat(M - N +1) {
15.             C := случайная вершина из A;
16.             D := случайная вершина из A, не равная C;
17.             свяжи C и D ребром;
18.       }
19. }

Обновление списка соседей будет частью "свяжи C и D ребром" и не влияет на алгоритм.

 

Stiver

Код (Text):

1.       repeat(M - N +1) {
2.             C := случайная вершина из A;
3.             D := случайная вершина из A, не равная C;
4.             свяжи C и D ребром;
5.       }

Между C и D уже может быть ребро. Тут самое интересное как определить этот факт без матрицы смежности вершин которая имеет размер NxN и при малых M её заполнение будет основную часть времени занимать.

 

Black_mirror

А, тогда я не совсем понял условие. Ребер начинающихся и заканчивающихся в одной и той же вершине быть не должно понял как "не должно быть петель, то есть ребер вида k-k".

Значит каждое ребро сохраняется в hash map и проверяется на существование. Это операция O(1), так что не влияет на скорость. Можно и матрицу смежности использовать, тоже O(1), только расход памяти больше (заполнение происходит одновременно с построением графа, поэтому ничего не стоит)

 

Stiver
Я имею ввиду что не может быть ребёр вида X-X, а между парой вершин X и Y может быть не более одного ребра(а может вообще не быть).
Алгоритм вида выбрать две вершины и попробовать соединить их ребром(если его еще нет) будет очень плохо работать когда в графе есть почти все ребра(по мере заполнения графа будет все больше неудачных попыток). А если мы построим множество всех возможных ребёр, и потом будем выбирать M-(N-1) ребёр из него (N-1 ребро у нас уже есть для обеспечения связности), то на построение потребуется N*N операций, то есть он плохо работает когда M близко к N-1.

 

Black_mirror

Если M > N*(N-1)/2, то можно перевернуть алгоритм и убирать ребра, вместо их добавления. Таким образом вероятность неудачной попытки будет всегда не больше 1/2, этого вполне хватит для O(N)

 

Stiver
Хорошее решение.
Только у меня в условии бага есть, я написал M<=N*(N-1), нужно еще на 2 поделить.

 

Black_mirror

Если ненаправленный граф, то да Если направленный, то не надо.

 

Есть еще одно решение без хеш таблицы или матрицы смежности, но с перебором всех возможных ребёр.
Если нам нужно добавить С ребер, а всего их может быть T, то можно сделать так:
for(i=0;C;i++,T--)
if(frand()<C/T){
//преобразуем i в номера вершин которые нужно соединить и соединяем
С--;
}
В принципе можно расчитать вероятность с которой мы пропустим X ребёр, прежде чем решим что нужно добавить ребро, у меня получилось
p(x)=(T-C)!*(T-X-1)!*C/T!/(T-C-X)!
и если придумать как генерировать числа от 0 до T-C с вероятностью p(x), то можно решить за С шагов. При это ребра мы будем получать в упорядоченном виде.

 

Black_mirror
Может быть будет проще представить вероятность p(x) в более компактном виде (и более понятном)

p(x)=B(T-X-1, C-1)/B(T,C), где B(N,K)=N!/(K!*(N-K)!) - биномиальный коэффициент.

 

crypto
Проще, только превратить равномерно распределённые числа в числа распределённые с вероятностью p(x) она мне и в таком виде не помогает. Видимо плохо математику учил.

 

Black_mirror
А это случаем не связано с отрицательным биномиальным распределением?
http://algolist.manual.ru/maths/matstat/negBinomial/index.php
Соответствующий способ генерации для него:
http://mylearn.ru/kurs/36/1788

 

crypto
Похоже что связано не с отрицательным, а с обычным.

Если через p0 обозначить вероятность того что первые X ребёр отсутствуют, и все C рёбер собрались в конце, то
При T=C+1, сумма вероятностей будет s1=p0*(C+1)/1 (вероятность того что первое ребро есть, в C раз больше вероятности что оно отсутствует и все рёбра в конце)
При T=C+2, s2=s1*(C+2)/2 (вероятность того что первое ребро есть, в C/2 раз больше вероятности что оно отсутствует и мы имеем дело с предыдущими ситуациями)
При T=C+2, s3=s2*(C+3)/3
...
При T=C+X, sX=s[X-1]*(C+X)/X
То есть sX=(C+X)!/C!/X!*p0

Теперь вопрос как найти обратную функцию?!

 

Black_mirror
Здесь наверное опечатка:

?
Должно быть
sX=p0*(C+X)!/(C!*X!).

Значит имеем sN=p0*(C+N)!/(C!*N!) = p0*B(C+N,N). И чем это не отрицательное биномиальное распределение?

 

Чего то я не понял чего вы паритесь? Строим любой связный граф с M ребрами, а затем генерируем случайную перестановку его вершин. Очевидно, что вероятности всех ребер будут одинаковыми.

 

halyavin

Случайно строим?

 

crypto

я именно это и имел ввиду, у меня просто одинаковый приоритет у "*" и "/".
sX у меня сумма вероятностей, которая должна быть равна 1. А вот p0 это вероятность того первые X рёбер отсутствуют, а все C ребёр оказались в самом конце, s1 - вероятность отсутствия первых X-1 рёбер, и так далее.

А геометрического распределения, чтобы его просуммировать и получить отрицательное биноминальное, я здесь не вижу.
Первое ребро у нас включается с вероятностью C/T, в этом случае вероятность включить второе ребро (C-1)/(T-1). Если первое ребро не включаем (вероятность этого события (T-C)/T), то вероятность включить второе ребро C/(T-1). Суммарная вероятность того что второе ребро попадёт в граф C/T*(C-1)/(T-1)+(T-C)/T*C/(T-1)= (C^2-C+TC-C^2)/T/(T-1)= C*(T-1)/T/(T-1)=C/T.
Здесь вероятность включить или не включить рёбро меняется в зависимости от того, сколько рёбер уже добавили, и в случае пропуска первых X рёбер вероятность включить ребро становится единичной.

 

Нет, как раз точно определенный. Для тех, кто не может представить:

Код (Text):

1. int count=0;
2. label: for (int i=0;i<n;i++)
3.      for (int j=i+1;j<n;j++)
4.      {
5.           count++;
6.           if (count==m)
7.                break label;
8.           addEdge(i,j);
9.      }

 

halyavin
Недостроенный полный граф. Перенумерацией всех вершин получаем изоморфный граф.
А случайность то здесь с какого боку?

 

А никто и не просил строить не изомофрные графы - требовалась лишь равновероятность ребер.