An empirical study of the structure of the shortest path tree - Bloznelis, Mindaugas; Radavičius, Irmantas (Lietuvos matematikos rinkinys, 2008)
We consider a complete graph on n vertices. Edges of the graph are prescribed random positive weights X1, X2, . . ., Xm. Here m = (n/2). We assume that these random variables are independent and have the common probability distribution with density function f (x), x ≥ 0. Given a vertex v let T denote the shortest path tree with root v. Let T1, T2, . . . ⊂ T denote the trees that are obtained from T after removal of the root v. Let N1 ≥ N2 ≥ N3 ≥ . . . denote (ordered) sequence of sizes of these trees. We study statistical properties of this sequence for various densities f and large n.