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