The second moment of the complexity of a graph
The second moment of the complexity of a graph
复制标题
DOI：
10.1112/s0025579300004290
复制
发表时间：
1964-12
期刊：
影响因子：
0.8
通讯作者：
J. Moon
中科院分区：
文献类型：
--
作者：
J. Moon
图由一组顶点组成，其中一些顶点对通过一条边连接起来。树是一种图，其属性是每对顶点都通过一条路径精确连接，即由边连续连接的一系列不同顶点。具有 n 个顶点和 k 个边的图 G(n, k) 的复杂度 c 是具有 n 个顶点的树的数量，这些树是 G(n, k) 的子图。 c 在所有图 G(n, k) 的类上的分布具有物理意义，因为它揭示了经典的多体问题。 （参见，例如[9]。）Ford 和 Uhlenbeck [3] 给出的数值数据表明，如果 k 接近，则 c 的分布随着 n 的增加而趋于正态分布。一般情况下，没有比第一个更高的时刻是已知的，他们在 [4] 中评论说，即使是“第二个也值得了解”。本文的主要目的是推导 c 的二阶矩的公式。
A graph consists of a set of vertices some pairs of which are joined by a single edge. A tree is a graph with the property that each pair of vertices is connected by precisely one path, i.e. , a sequence of distinct vertices joined consecutively by edges. The complexity c of a graph G(n, k) with n vertices and k edges is the number of trees with n vertices which are subgraphs of G(n, k) . The distribution of c over the class of all graphs G(n, k) is of physical interest because it throws light on the classical many-body problem. (See, e.g. [9].) Ford and Uhlenbeck [3] gave numerical data which suggested that the distribution of c tends to normality for increasing n if k is near No moments higher than the first were known in general and they remarked in [4] that even “the second would be worth knowing”. The main object in this paper is to derive a formula for the second moment of c .