MAX-CUT: вероятностное округление/Задачи/Матожидание разреза

Ссылки сюда (2) →

Рассмотрим случайные графы

• из n вершин,
• ребро возникает между любой парой вершин с вероятностью ½.

Напишите формулу матожидания средней величины разреза по всем таким случайным графам из n-вершин.

Решение Кудрицкого К.В.: Пусть первый подграф S с мощьностью m, тогда второй = V\S.

Искомое матожидание: E(N_разрез) = E(Сумма(по всем i принадлежащим S(Сумма по всем j принадлежащим V/S(Индикатор того, что существует ребро между вершинами v_i и v_j))) = Сумма по всем i принадлежащим S(Сумма по всем j принадлежащим V/S( E(Индикатор того, что существует ребро между вершинами v_i и v_j))) = 1/2 * m*(n-m);

Ответ:1/2 * m*(n-m)

Стас Фомин 22:30, 25 December 2011 (MSK):формула должна зависеть только от n

..решение Дыкало А..Пусть (S,T)-разрез случайного графа G=G(V,E) такой, что |S|=m. {I(i,j)}_{i,j∈{1,2,..n}}-семейство бернулливских СВ с p=q=1/2. Событие {I(i,j)=1} <=> {(i,j)∈E}. Размер разреза:

   Size(S)=∑(i,j)∈E:i∈S,j∈TI(i,j)

искомая величина=(∑_{по возможным S}Size(S))/=(∑_{по возможным S})∑_{(i,j)∈E:i∈S,j∈T}I(i,j))/=

(1/(2^n-2))∑_m=1,2,n-1=(1/(2^n-2))∑_m=1,2,n-1

=(1/(2^{n+1}-4))n(n-1)∑_m=1,2,n-1=

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.