Случайный графический модель

Question

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

Например, если вероятность составляет 0,5, означает, что мы можем просто добавить два ребра в график, потому что 0,5+0,5 = 1.

Answer 1

Предположим, вы хотите вычислить случайный график $ g (n, p) $, который является графом с вершинами $ n $, где каждый край добавляется с вероятностью $ p. $

Предположим, у вас есть монета, которая дает хвостам с вероятностью $ p $ и головы с вероятностью $ 1-p. $

Тогда то, что вы делаете $ {1, ..., n } $, чтобы быть набором вершины вашего графика и для каждой пары $ (i, j) in { {1, ldots, n } Выберите 2} $, вы переверните свою монету. Если это приходит хвосты, вы добавляете Edge $ (i, j) $ на свой график, иначе вы этого не делаете.

Answer 2

В модели случайной $ g (n, p) $, каждый из $ binom {n} {2} $ края добавляются к графику с вероятностью $ p $ независимо. Анкет Это означает, что если вы рассмотрите какие -либо два ребра, то оба находятся на графике с вероятностью $ P^2 $, а не $ 2P $.

Answer 3

В дополнение к тому, что сказано, что правильно, вы можете создать случайный график $ g (n, p) $ за $ 0 leq P leq 1 $ следующим образом:

Предположим, у вас есть набор вершин $ V $ и пустые края $ e $. За каждый $ V $ в $ V $: за каждый $ U $ в $ V $ (где $ U> V $ в отношении некоторого общего заказа среди узлов $ V $): генерируйте равномерное случайное число $ r $, где $ r in [0,1] $. Если ($ r leq p $) включите Edge $ (v, u) $ и $ (u, v) $ to $ e $.

Это генерирует случайный график $ g = (v, e) $ обозначен $ g (n, p) $, где $ | v | = n $. Это, однако, направленный график. Если вы хотите сделать это направленным графиком, который, как этот случай не следует определению, добавьте только график $ (v, u) $.