如题,1--2--3--4 和 4--3--2--1 视作同一种树。但 1--2--3--4 和 1--2--4--3 视作不同的树,要求一种算法使得生成每一种树的概率相等。
1--2--3--4
4--3--2--1
1--2--4--3
已经否定的两种方法:
每次随机加一条合法的边,在 n=4n=4n=4 时生成一种特定链的概率为 118\frac{1}{18}181,生成一种特定菊花图的概率为 112\frac{1}{12}121;
随机生成 nnn 个点完全图的边集排列,每次若一条边加入后合法则加入,不合法则跳过。上述概率变为 11180\frac{11}{180}18011 和 115\frac{1}{15}151。
如果不行的话,能否取得将 1--2--3--4 与 1--2--4--3 等树视作同一种情况(如同结点数的链都是同种情况,菊花图都是一种情况)时,使生成不同情况树的概率相等?