Navespro.ru

Копия http://community.livejournal.com/ru_math/746403.html?thread=6964643#t6964643 плюс программа. Результаты довольно интересные. Например, средняя валентность - 3.76, как у реального графа Эрдёша. Пост довольно длинный, поскольку под кат переносить я не умею.

Я подумал, что можно сымитировать рост компоненты Эрдёша следующим образом. Начинаем с какого-нибудь нетривиального графа, и фиксируем два числа 0 < q < < p < 1. Фиксируем также некое натуральное число k, скажем 5. Далее на каждом шагу во-первых с вероятностью q (соотв. 1-q) выбираем - или +. Если выбрали -, то присваиваем какой-то (случайно выбранной) вершине статус "dead". Если выбрали +, то с вероятностью p (соотв. 1-p) выбираем 0 или 1. Если 0, то добавляем одну вершину к графу, и соединяем ее ребром с одной из живых вершин. Если 1, то соединяем две случайные живые вершины на расстоянии < k новым ребром. Смысл числа k в том, что обычно если люди становятся соавторами, то расстояние между ними и так не очень большое. Это похоже на процесс конденсации, так что я не удивлюсь, если мат.физики уже подобные процессы рассматривали.

Вот программа на Maple-12 с комментариями.

with(networks):with(combinat): with(GraphTheory):
# Call packages "networks" and "combinatorics" and "GraphTheory"

V:={1,2,3}:N:=3: EE:={{1,2},{2,3}}:
# Initial graph with 3 vertices and two edges.

for i from 1 to 1000 do

# 1000 iterations

a:=rand() mod 100;

# the probability of death is 1/100

if a=0
# if a vertex must die

then x:= (rand() mod nops(V))+1; V:=V minus {x}

# Choose a random vertex (among alive vertices) and remove it from the set of alive vertices V.

else
b:=rand() mod 2;

# If all vertices survive, choose whether to add a vertex or add an edge. The probability of adding a vertex is 1/2.

if b=0 then x:= (rand() mod nops(V))+1; V:=V union {N+1}; N:=N+1; EE:=EE union {{N, x}};

# In case we need to add a vertex, choose a random alive
#vertex x, add the new vertex N+1, and connect N+1 and x.
#N=N+1 is the new number of all vertices

else G1:=InducedSubgraph(Graph(EE),V);
G2:=GraphPower(G1,3):
UU:=Edges(G2):

# If we need to add an edge, find the set UU of pairs of alive vertices at distance at most 3.

u:= (rand() mod nops(UU))+1: EE:=EE union {UU[u]}; fi: fi:
od:

# choose a random pair of vertices in UU and add an edge connecting these vertices. The cycle ends.

G:=graph({seq(i,i=1..N)}, EE): print("diameter", diameter(G)); Vdead:={seq(i, i=1..N)} minus V: print("dead vertices", Vdead): av:=evalf(sum(degreeseq(G)[ii],ii=1..N )/N):print("average degree", av, "total number of vertices", N);

> #printing diameter, the set of dead vertices, the average degree of a vertex, the total number of vertices.

Вам это будет интересно!

Последние новости