Привет, это мой первый вопрос. Я встретил домашнюю работу по алгоритму и вероятности, что я не могу найти ключ для вычисления.Как рассчитать ожидаемое значение генерации случайного графа
Вопрос: Вычисление числа треугольников в графе: для неориентированного графа G = (V, E) треугольник в G является кликой размера 3 (формально множество узлов {u, v, w } является треугольником в G, если (u, v), (v, w), (u, w) - все ребра из G). Рассмотрим следующий алгоритм для аппроксимации числа треугольников в графе. Сначала построим выборочный граф G '= (V, E') следующим образом. Множество вершин G 'такое же, как и для G. Для любого e ∈ E положим e в E' с вероятностью p (вспомните p как, скажем, 0,1). В этом новом выборочном графе G 'подсчитайте количество треугольников и пусть T' - число треугольников в G '(предположим, что вы дали подпрограмму черного ящика, чтобы подсчитать количество треугольников в G'). Тогда выведите T = T '/ p. Показать, что ожидаемое значение T = T, T - число треугольников исходного графа G.
Я сбиваю с толку, что ребро в G или G ', чтобы сформировать треугольник, не является независимым, поскольку два смежных треугольника в G могут разделите край. И не все пары вершин из G могут образовать ребро в G ', только те ребра в G будут присутствовать в G' с p. Мне трудно думать о соотношении числа ребер и числа треугольников в G или G '.
Надеюсь, что кто-то может дать мне несколько советов, даже не все решение в порядке.
_ «Для каждого e ∈ E положите e в E 'с вероятностью p (считайте p как, скажем, 0,1) «Что означало бы, что ребро имеет вероятность p? Вероятность чего? Какова будет случайная величина? Постоянна ли для всех ребер в E? –
ОК, я думаю, я понял, это вероятность того, что e будет включен в E? Таким образом, для каждого ребра e в E, вероятность p его является частью E '? –
p некоторого ребра e является тем, что для одного ребра e ∈ E вероятность этого ребра также присутствует в G '. И мы хотим получить ожидаемое значение T, T определяется как T '/ p. Здесь T '- число треугольников в G'. –