不相交数据结构中森林的组合

Question

是一种不相交的数据结构，一般情况下很难进行分析.最小的问题是，答案取决于如何定义平均值(关于工会运作)。例如，在下面给出的森林中。为了便于描述，每棵树都用set来表示。

{0}，{1}，{2}，{3}，{4，5，6,8 }

我们可以说，由于有五棵树，所以5*4= 20是下一次联合的结果(因为任何两棵不同的树都可以联合起来)。当然，这个模型的含义是，只有2/5的可能性下一次联合将涉及到大树。

另一种模型可能会说，在不同的树中，任意两个元素之间的所有结合都是相同的，因此一个更大的树比一个较小的树更有可能参与下一个联合。在上面的示例中，有8/11可能涉及到下一次合并，因为(忽略对称性)有6种方法可以合并{1、2、3、4}中的两个元素，还有16种方法可以将{5、6、7、8}中的元素与{1、2、3、4}中的元素合并。目前仍有更多的模式，而且没有就哪一种是最好的达成一致意见。平均运行时间取决于模型；对于三种不同的模型，O(m)、O( more n)和O(mn)的界实际上已经显示出来，尽管后者的界被认为是更现实的。

本文来自Wessis的算法和数据分析。

我在组合数学方面很差，所以我不理解上面的问题，在这里我需要帮助回答以下问题。

在以上的description?

• How中，如何得到2/5，在上面我们得到了8/11，description?

• Author只描述了两种模型，但是在段落的末尾提到了不同的模型，第三种模式是什么？

谢谢你的帮忙

Answer 1

以下是前两个问题的答案：

1. 给出了五棵树A，B，C，D，E，E在随机选择的树中包含的概率是多少？

由于可能有10对(AB，AC，AD，AE，BC，BD，BE，CD，CE，DE)，其中4对(AB，AC，AD，AE)包含A，则概率为4/10 =2/5。

• 给出了五棵树A={a}，B={b}，C={c}，D={d}，E={e，f，g，h}，在随机选择的两个项目中包含E元素的概率是多少？

项目有22对(ab、ac、ad、ae、af、ag、ah、bc、bd、be、bf、bg、bh、cd、ce、cf、cg、ch、de、df、dg、dh)，其中16对包括(e，f，g，h)之一，概率为16/22 =8/11。