In a complete graph with $n$ vertices there are $n^{n-2}$ trees.
In my research I'm analyzing trees in the following way (each edge has a weight):
- Get a tree.
- Build a complete graph, by the following rule: the edge from the vertex $i$ to the vertex $k$ has the weight that is equal to the product of the weights from $i$ to $j$ and $j$ to $k$.
- Take the weights that correspond to the weights from the first vertex, form a vector.
- Divide vector by the sum of its elements.
- Do it for all the trees.
- Form a matrix whose columns are vectors for each tree, the dimension of this matrix is $n-1\times n^{n-2}$.
- For each row find the sum of absolute differences of weights between any two elements. Let it be function $f$.
- Find a minimum of the values obtained on the previous step (let it be function $g$).
In general, if $i$-th tree is denoted as $T_i$, then what I do is $g\left(f(T_1),f(T_2),\ldots,f(T_{n^{n-2}})\right)$.
The problem is that $n^{n-2}$ is a pretty big number.
And I want to use a sample to approximate the true result.
I have done some simulation and it appeared that linear sample suffices (in this case the error is about 5%) when $g$ function is not $\operatorname{min}$, but the average of numbers. It doesn't matter what the function $f$ is.
I have the following questions.
- Are there any researches/proofs regarding this topic? I mean how all this behaves with respect to a sampling technique and the choice of the functions $f$ and $g$.
- It is clear that all trees produce excessive information. Is there some "smart" sampling technique that will allow to reduce the sample size to the polynomial (cubic, quadratic, or even linear!) without restricting $f$ and $g$?
- Is there a proof that if $g$ is a mean function, then it doesn't matter what $f$ is. All we need is a sample linear in number of vertices.
As far as I know, if the sample is random, then the sample size should be exponential in the number of vertices, but here all trees are related, so one can possibly decrease this number.
Thank you.
