|
|
(не показаны 4 промежуточные версии этого же участника) |
Строка 2: |
Строка 2: |
| <m>\frac{n^2}{c}</m>, где с<8), в случайных графах из n вершин с вероятностью зарождения ребра — ½. | | <m>\frac{n^2}{c}</m>, где с<8), в случайных графах из n вершин с вероятностью зарождения ребра — ½. |
| | | |
− | ;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>
| + | |