Si parte disegnando un nodo. Di volta in volta si traccia un ramo uscente da un nodo scelto a caso tra quelli già disegnati con egual probabilità. Supponendo di fare questo procedimento per un numero molto elevato di volte in modo da distribuire per bene la probabilità, quanti sono in media i nodi aventi grado $k$ in proporzione al totale di nodi disegnati?
PS: non so se è la sezione giusta, ma mi sembrava la più appropriata.
Albero random
Re: Albero random
non sono del tutto sicuro ma penso di esser riuscito a dare una limitazione asintotica alla proporzione, ovvero i nodi di grado k (dove il nodo di partenza ha grado 0) rispetto al totale sono al più $\displaystyle\frac{(\ln n)^k}{n}$, ovviamente con qualche costante moltiplicativa.
Ha un senso?
Ha un senso?
Re: Albero random
A meno che dietro quella stima non c'è qualche trucco analitico profondo direi di no xD
Ma forse c'è qualche problema di interpretazione. Cioè il nodo di partenza non può avere grado 0 (come nessun nodo del resto).
Per grado intendo il numero di rami uscenti da esso, non il numero di nodi padre.
Il risultato dovrebbe venire in una forma decisamente pulita (anche se ho dato per buono che i rapporti convergono
)
Ma forse c'è qualche problema di interpretazione. Cioè il nodo di partenza non può avere grado 0 (come nessun nodo del resto).
Per grado intendo il numero di rami uscenti da esso, non il numero di nodi padre.
Il risultato dovrebbe venire in una forma decisamente pulita (anche se ho dato per buono che i rapporti convergono
)Re: Albero random
Ok c'era un grosso problema di interpretazione XD io per grado intendevo la "distanza" dal nodo radice o la profondità per dirla in altro modo