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

StasFomin: Массовая правка: добавление Категория:Теоретические задачи

2023-05-04T06:50:49Z

Массовая правка: добавление Категория:Теоретические задачи

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

2020-10-06T19:12:40Z

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

StasFomin в 17:39, 4 октября 2020

2020-10-04T17:39:34Z

Maintwister в 14:22, 27 декабря 2011

2011-12-27T14:22:18Z

Новая страница

Рассмотрим случайные графы
* из <tt>n</tt> вершин,
* ребро возникает между любой парой вершин с вероятностью ½.

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

[[Category:Задачи для желающих улучшить оценку]]

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

Искомое матожидание: E(Nразрез) = E(Сумма(по всем i принадлежащим S(Сумма по всем j принадлежащим V/S(Индикатор того, что существует ребро между вершинами vi и vj))) = Сумма по всем i принадлежащим S(Сумма по всем j принадлежащим V/S( E(Индикатор того, что существует ребро между вершинами vi и vj))) = 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)}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)

искомая величина=(∑по возможным SSize(S))/<m>2^n-2</m>=(∑по возможным S)∑(i,j)∈E:i∈S,j∈TI(i,j))/<m>2^n-2</m>=
=(1/(2^n-2))∑m=1,2,n-1<m>{{C_n}^m}(1/2)(m(n-m))</m>=(1/(2^n-2))∑m=1,2,n-1<m>{{C_{n-2}}^{m-1}}(1/2)n(n-1)</m>=
=(1/(2^{n+1}-4))n(n-1)∑m=1,2,n-1<m>{{C_{n-2}}^{m-1}}</m>=<m>n(n-1)\frac{2^{n-2}}{2^{n+1}-4}</m>

← Предыдущая		Версия 06:50, 4 мая 2023
Строка 6:		Строка 6:

	[[Категория:Решенные задачи]]		[[Категория:Решенные задачи]]
		+	[[Категория:Теоретические задачи]]

@@ Строка 5: / Строка 5: @@
 Напишите формулу матожидания средней величины разреза по всем таким случайным графам из <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>

← Предыдущая	Версия 19:12, 6 октября 2020
(нет различий)