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

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показаны 2 промежуточные версии этого же участника)
Строка 5: Строка 5:
 
Напишите формулу матожидания средней величины разреза по всем таким случайным графам из <tt>n</tt>-вершин.
 
Напишите формулу матожидания средней величины разреза по всем таким случайным графам из <tt>n</tt>-вершин.
  
−
[[Category:Задачи для желающих улучшить оценку]]
+
[[Категория:Решенные задачи]]
−
 
+
[[Категория:Теоретические задачи]]
−
 
+
−
'''Решение Кудрицкого К.В.''':
+
−
Пусть первый подграф S с мощьностью m, тогда второй = V\S.
+
−
 
+
−
Искомое матожидание: E(N<sub>разрез</sub>) = E(Сумма(по всем i принадлежащим S(Сумма по всем j принадлежащим V/S(Индикатор того, что существует ребро между вершинами v<sub>i</sub> и v<sub>j</sub>))) = Сумма по всем i принадлежащим S(Сумма по всем j принадлежащим V/S( E(Индикатор того, что существует ребро между вершинами v<sub>i</sub> и v<sub>j</sub>))) = 1/2 * m*(n-m);
+
−
 
+
−
Ответ:1/2 * m*(n-m)
+
−
 
+
−
{{remark|[[User:StasFomin|Стас Фомин]] 22:30, 25 December 2011 (MSK):формула должна зависеть только от n}}
+
−
 
+
−
'''..решение Дыкало А..'''Пусть (S,T)-разрез случайного графа G=G(V,E) такой, что |S|=m. {I(i,j)}<sub>i,j∈{1,2,..n}</sub>-семейство бернулливских СВ с p=q=1/2. Событие {I(i,j)=1} <=> {(i,j)∈E}.
+
−
Размер разреза:
+
−
    Size(S)=∑<sub>(i,j)∈E:i∈S,j∈T</sub>I(i,j)
+
−
 
+
−
искомая величина=(∑<sub>по возможным S</sub>Size(S))/<m>2^n-2</m>=(∑<sub>по возможным S</sub>)∑<sub>(i,j)∈E:i∈S,j∈T</sub>I(i,j))/<m>2^n-2</m>=
+
−
=(1/(2^n-2))∑<sub>m=1,2,n-1</sub><m>{{C_n}^m}(1/2)(m(n-m))</m>=(1/(2^n-2))∑<sub>m=1,2,n-1</sub><m>{{C_{n-2}}^{m-1}}(1/2)n(n-1)</m>=
+
−
=(1/(2^{n+1}-4))n(n-1)∑<sub>m=1,2,n-1</sub><m>{{C_{n-2}}^{m-1}}</m>=<m>n(n-1)\frac{2^{n-2}}{2^{n+1}-4}</m>
+

Текущая версия на 06:50, 4 мая 2023

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

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

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

Источник — «https://discopal.ispras.ru/index.php?title=MAX-CUT:_вероятностное_округление/Задачи/Матожидание_разреза&oldid=25713»