Random minimum spanning tree (original) (raw)
在数学中，将一个无向图按照某种分布随机分配边权后可得一个新图，后者的最小生成树便称为随机最小生成树。 若给定的图是n个顶点的完全图，且边权的分布函数处处连续并在原点处导数D > 0，则随机生成树的边权总和有上界C，后者不随n的增长而增长。更精确地讲，n趋向于无穷大时，C趋向于ζ(3)/D，其中ζ为黎曼ζ函數，ζ(3)为阿培里常数。例如，若边权均匀分布于单位区间，则其导数为D = 1，n趋向于无穷大时，C恰趋向于ζ(3)。 的随机生成树在多孔介质中液态流体的模型以及算法中都有所应用。
| Property | Value |
|---|---|
| dbo:abstract | In mathematics, a random minimum spanning tree may be formed by assigning random weights from some distribution to the edges of an undirected graph, and then constructing the minimum spanning tree of the graph. When the given graph is a complete graph on n vertices, and the edge weights have a continuous distribution function whose derivative at zero is D > 0, then the expected weight of its random minimum spanning trees is bounded by a constant, rather than growing as a function of n. More precisely, this constant tends in the limit (as n goes to infinity) to ζ(3)/D, where ζ is the Riemann zeta function and ζ(3) is Apéry's constant. For instance, for edge weights that are uniformly distributed on the unit interval, the derivative is D = 1, and the limit is just ζ(3). In contrast to uniformly random spanning trees of complete graphs, for which the typical diameter is proportional to the square root of the number of vertices, random minimum spanning trees of complete graphs have typical diameter proportional to the cube root. Random minimum spanning trees of grid graphs may be used for invasion percolation models of liquid flow through a porous medium, and for maze generation. (en) 在数学中，将一个无向图按照某种分布随机分配边权后可得一个新图，后者的最小生成树便称为随机最小生成树。 若给定的图是n个顶点的完全图，且边权的分布函数处处连续并在原点处导数D > 0，则随机生成树的边权总和有上界C，后者不随n的增长而增长。更精确地讲，n趋向于无穷大时，C趋向于ζ(3)/D，其中ζ为黎曼ζ函數，ζ(3)为阿培里常数。例如，若边权均匀分布于单位区间，则其导数为D = 1，n趋向于无穷大时，C恰趋向于ζ(3)。 的随机生成树在多孔介质中液态流体的模型以及算法中都有所应用。 (zh) |
| dbo:wikiPageID | 1270875 (xsd:integer) |
| dbo:wikiPageLength | 2991 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1032091995 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Spanning_tree dbr:Riemann_zeta_function dbr:Undirected_graph dbr:Invasion_percolation dbr:Complete_graph dbr:Apéry's_constant dbr:Cumulative_distribution_function dbr:Distance_(graph_theory) dbr:Maze_generation dbr:Minimum_spanning_tree dbr:Unit_interval dbr:Uniform_spanning_tree dbr:Grid_graph |
| dbp:wikiPageUsesTemplate | dbt:Combin-stub dbt:Math dbt:Mvar dbt:Reflist |
| dct:subject | dbc:Spanning_tree |
| rdfs:comment | 在数学中，将一个无向图按照某种分布随机分配边权后可得一个新图，后者的最小生成树便称为随机最小生成树。 若给定的图是n个顶点的完全图，且边权的分布函数处处连续并在原点处导数D > 0，则随机生成树的边权总和有上界C，后者不随n的增长而增长。更精确地讲，n趋向于无穷大时，C趋向于ζ(3)/D，其中ζ为黎曼ζ函數，ζ(3)为阿培里常数。例如，若边权均匀分布于单位区间，则其导数为D = 1，n趋向于无穷大时，C恰趋向于ζ(3)。 的随机生成树在多孔介质中液态流体的模型以及算法中都有所应用。 (zh) In mathematics, a random minimum spanning tree may be formed by assigning random weights from some distribution to the edges of an undirected graph, and then constructing the minimum spanning tree of the graph. In contrast to uniformly random spanning trees of complete graphs, for which the typical diameter is proportional to the square root of the number of vertices, random minimum spanning trees of complete graphs have typical diameter proportional to the cube root. (en) |
| rdfs:label | Random minimum spanning tree (en) 随机最小生成树 (zh) |
| owl:sameAs | wikidata:Random minimum spanning tree dbpedia-zh:Random minimum spanning tree https://global.dbpedia.org/id/4tgtN |
| prov:wasDerivedFrom | wikipedia-en:Random_minimum_spanning_tree?oldid=1032091995&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Random_minimum_spanning_tree |
| is dbo:wikiPageDisambiguates of | dbr:Spanning_tree_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Random_minimal_spanning_tree |
| is dbo:wikiPageWikiLink of | dbr:Apéry's_constant dbr:Spanning_tree_(disambiguation) dbr:Christina_Goldschmidt dbr:Random_minimal_spanning_tree |
| is foaf:primaryTopic of | wikipedia-en:Random_minimum_spanning_tree |