在数学中,将一个无向图按照某种分布随机分配边权后可得一个新图,后者的最小生成树便称为随机最小生成树。
此条目可参照外语维基百科相应条目来扩充。 (2016年12月8日) |
若给定的图是n个顶点的完全图,且边权的分布函数处处连续并在原点处导数D > 0,则随机生成树的边权总和有上界C,后者不随n的增长而增长。更精确地讲,n趋向于无穷大时,C趋向于ζ(3)/D,其中ζ为黎曼ζ函数,ζ(3)为阿培里常数。例如,若边权均匀分布于单位区间,则其导数为D = 1,n趋向于无穷大时,C恰趋向于ζ(3)。[1]
参考资料
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.