Goldsborough Andrew M, Rautu S Alex, Römer Rudolf A
Department of Physics and Centre for Scientific Computing, The University of Warwick, Coventry CV4 7AL, United Kingdom.
Phys Rev E Stat Nonlin Soft Matter Phys. 2015 Apr;91(4):042133. doi: 10.1103/PhysRevE.91.042133. Epub 2015 Apr 27.
We study the leaf-to-leaf distances on one-dimensionally ordered, full and complete m-ary tree graphs using a recursive approach. In our formulation, unlike in traditional graph theory approaches, leaves are ordered along a line emulating a one-dimensional lattice. We find explicit analytical formulas for the sum of all paths for arbitrary leaf separation r as well as the average distances and the moments thereof. We show that the resulting explicit expressions can be recast in terms of Hurwitz-Lerch transcendants. Results for periodic trees are also given. For incomplete random binary trees, we provide first results by numerical techniques; we find a rapid drop of leaf-to-leaf distances for large r.
我们使用递归方法研究一维有序、完全且完整的m元树图上叶到叶的距离。在我们的公式中，与传统图论方法不同，叶沿着模拟一维晶格的线排序。我们找到了任意叶间距r的所有路径之和、平均距离及其矩的显式解析公式。我们表明，所得的显式表达式可以用赫维茨 - 勒尔奇超越函数来表示。还给出了周期树的结果。对于不完整的随机二叉树，我们通过数值技术给出了初步结果；我们发现对于大的r，叶到叶的距离会迅速下降。
