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

Материал из DISCOPAL
Перейти к: навигация, поиск
 
Строка 4: Строка 4:
 
;Hint: Сначала надо правильно решить [[MAX-CUT: вероятностное округление/Матожидание разреза]].
 
;Hint: Сначала надо правильно решить [[MAX-CUT: вероятностное округление/Матожидание разреза]].
  
[[Category:Задачи для желающих улучшить оценку]]
+
[[Категория:Задачи для желающих улучшить оценку]]
 
+
...решение Дыкало А....
+
 
+
Пусть дан граф 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) ⩾ <m>[n^2/c]+1</m>}
+
Это значит, что P{I(S)=1}=P{X(S) ⩾ <m>[n^2/c]+1</m>},
+
 
+
но также справедлива вложенность событий:
+
          {X(S) ⩾ <m>[n^2/c]+1</m>}={X(S)-M{X(S)}⩾<m>[n^2/c]+1</m>-M{X(S)}}⊆{|X(S)-M{X(S)}|⩾<m>[n^2/c]+1</m>-M{X(S)}}
+
 
+
    А следовательно и:
+
 
+
          P{X(S) ⩾ <m>[n^2/c]+1</m>}⩽P{|X(S)-M{X(S)}|⩾<m>[n^2/c]+1</m>-M{X(S)}} ⩽D^2/(<m>[n^2/c]+1</m>-M{X(S)})^2, где D^2-дисперсия СВ X(S).<br>Второе неравенство в двойном неравенстве объясняется неравенством Чебышева.
+
 
+
 
+
|S|=m, тогда
+
M{X(S)}=∑<sub>по всем количествам ребер разреза k=1,2,...m(n-m)</sub>(k*C(m(n-m),k)*p^(k)*(1-p)^(m(n-m)-k))={при p=1/2}=(1/2)^(m(n-m))∑<sub>по всем количествам ребер разреза k=1,2,...m(n-m)</sub>(k*C(m(n-m),k))=<m>(1/2)^{m(n-m)}*m(n-m)*2^{m(n-m)-1}</m>=<m>m(n-m)/2</m>
+
 
+
 
+
M{<m>X(S)^2</m>}=∑<sub>по всем количествам ребер разреза k=1,2,...m(n-m)</sub>(<m>k^2</m>*C(m(n-m),k)*p^(k)*(1-p)^(m(n-m)-k))=
+
 
+
D^2=M{<m>X(S)^2</m>} - <m>M{X(S)}^2</m>=(1/2)^(m(n-m))∑<sub>по всем количествам ребер разреза k=1,2,...m(n-m)</sub>(k(k-1)*C(m(n-m),k))=(1/4)*(m(n-m))(m(n-m)-1)
+
 
+
P{X(S) ⩾ <m>[n^2/c]+1</m>}⩽<m>{(1/4)*(m(n-m))(m(n-m)-1)}/{({[n^2/c]+1-m(n-m)/2})^2}</m>
+
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)}⩽
+
∑<sub>m=1,2,..,n-1</sub>  <m>({{C_n}^{m}\frac{{(1/4)(m(n-m))(m(n-m)-1)}}{({[n^2/c]+1-m(n-m)/2})^2})</m>=<br>
+
∑<sub>m=1,2,..,n-1</sub>  <m>{{C_n}^{m}\frac{1-\frac{1}{m(n-m)}}{(1-2{\frac{[n^2/c]+1}{m(n-m)}})^2})</m>
+

Версия 17:21, 4 октября 2020

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

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