задача про случ.граф

dimkaL

найти среднее кол-ва треугольников в случайном графе.
выручите плз!

plugotarenko

Если ты напишешь, что такое случайный граф и как там распределены вероятности, то, возможно, тебе помогут. Без конкретики не понятно, что нужно сделать.

skin991

случайный граф это граф где ребра распределены по некоторым вероятностям,по моему любым.но если сложно то попробуйте решить там где все одинаково

plugotarenko

Если ребро есть с вероятностью p и с вероятностью 1-p ребра нет и все эти величины независимы, то тогда математическое ожидание числа треугольников С^3_n *p^3, где n число вершин графа.

natunchik

А почему так можно считать? Несколько смущает то, что на самом деле независимых случайных величин всего C^2_n, а используются они С^3_n * 3 раза, и каждый раз как будто они независимы.

plugotarenko

Математическое ожидание суммы равно сумме математических ожиданий. Независимость не при чем. Раскладываю искомую случайную величину в сумму индикаторов того, что появился данный конкретный треугольник. Всего треугольников C^3_n, а ожидание каждого индикатора в описанных мною условиях равна p^3.

skin991

объясните не грамотному что этот сомвол означает:С^3_n или это сочетание.а как будет если для каждого ребра вероятность будет разная.сумма по всем вероятностям что ли?
типа р(i)*p(j)*p(k)*(на какое-то сочетание(i,j,k

plugotarenko

C^3_n = \frac{n!}{3!(n-3)!} --- число сочетаний. в данном случае число треугольников в графе.
Если i,j,k --- это номера ребер в графе, то будет сумма по всем i<j<k p(i)*p(j)*p(k).

igor196505

Хочешь спецкурс нахаляву получить?
Оставить комментарий
Имя или ник:
Комментарий: