MAX-CUT: вероятностное округление/Задачи/Верхняя оценка разреза в случайном графе

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

Оцените сверху матожидание числа «больших» разрезов (разрезов, больше чем , где с<8), в случайных графах из n вершин с вероятностью зарождения ребра — ½.

Hint

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

...решение Дыкало А....

Пусть дан граф G: G=G(V,E), |V|=n. Рассмотрим некоторый разрез графа G, определяемый множествами S и T такой, что |S|=m, 0<m<n). Введем для каждого такого разреза случайную величину X(S)=|{(t,s) из E:s из S, t из T}|. Или словами: X(S)-это случайная величина равная размеру разреза. Введем в рассмотрение еще одну случайную величину для каждого разреза: I(S)=1, если разрез "большой" в указанном в условии смысле и 0, если иначе.

Таким образом, для данной реализации случайного графа количество "больших" разрезов равно:

    ∑I(S), где сумма берется по всем существующим разрезам (S,T).

Очевидно, в силу определения случайных величин X(S) и I(S), что

         {I(S)=1} <=> {X(S) ⩾ }

Это значит, что P{I(S)=1}=P{X(S) ⩾ },

но также справедлива вложенность событий:

         {X(S) ⩾ }={X(S)-M{X(S)}⩾-M{X(S)}}⊆{|X(S)-M{X(S)}|⩾-M{X(S)}}

    А следовательно и:

         P{X(S) ⩾ }⩽P{|X(S)-M{X(S)}|⩾-M{X(S)}} ⩽D^2/(-M{X(S)})^2, где D^2-дисперсия СВ X(S).
Второе неравенство в двойном неравенстве объясняется неравенством Чебышева.

|S|=m, тогда M{X(S)}=∑_{по всем количествам ребер разреза k=1,2,...m(n-m)}(k*C(m(n-m),k)*p^(k)*(1-p)^(m(n-m)-k))={при p=1/2}=(1/2)^(m(n-m))∑_{по всем количествам ребер разреза k=1,2,...m(n-m)}(k*C(m(n-m),k))==

M{}=∑_{по всем количествам ребер разреза k=1,2,...m(n-m)}(*C(m(n-m),k)*p^(k)*(1-p)^(m(n-m)-k))=

D^2=M{} - =(1/2)^(m(n-m))∑_{по всем количествам ребер разреза k=1,2,...m(n-m)}(k(k-1)*C(m(n-m),k))=(1/4)*(m(n-m))(m(n-m)-1)

P{X(S) ⩾ }⩽ M{I(S)}=0*P{I(S)=0} + 1*P{I(S)=1} = P{I(S)=1}

Количество разных разрезов (S,T) таких, что |S|=m равно С(m,n) Таким образом:

M{∑I(S),где сумма берется по всем возможным разрезам (S,T)}={∑M{I(S)},где сумма берется по всем возможным разрезам (S,T)}⩽ ∑_m=1,2,..,n-1 =
∑_m=1,2,..,n-1

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

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

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