关于随机生成一棵树的问题
  • 板块学术版
  • 楼主chenxi2009
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/10/10 21:21
  • 上次更新2024/10/10 23:45:26
查看原帖
关于随机生成一棵树的问题
1020063
chenxi2009楼主2024/10/10 21:21

如题,1--2--3--44--3--2--1 视作同一种树。但 1--2--3--41--2--4--3 视作不同的树,要求一种算法使得生成每一种树的概率相等。

已经否定的两种方法:

  • 每次随机加一条合法的边,在 n=4n=4 时生成一种特定链的概率为 118\frac{1}{18},生成一种特定菊花图的概率为 112\frac{1}{12}

  • 随机生成 nn 个点完全图的边集排列,每次若一条边加入后合法则加入,不合法则跳过。上述概率变为 11180\frac{11}{180}115\frac{1}{15}

如果不行的话,能否取得将 1--2--3--41--2--4--3 等树视作同一种情况(如同结点数的链都是同种情况,菊花图都是一种情况)时,使生成不同情况树的概率相等?

2024/10/10 21:21
加载中...