树状图

数据树的图形表示形式

树状图，亦称树枝状图。树形图是数据树的图形表示形式，以父子层次结构来组织对象。是枚举法的一种表达方式。树状图也是初中学生学习概率问题所需要画的一种图形。

定义

为了用图表示亲缘关系，把分类单位摆在图上树枝顶部，根据分枝可以表示其相互关系，具有二次元和三次元。在数量分类学上用于表型分类的树状图，称为表型树状图（phenogram），掺入系统的推论的称为系统树状图（cladogram）以资区别。表型树状图是根据群析描绘的，系统树状图是根据一种模拟的假定的性状进化方向即用电子计算机描绘的。

树状图也是初中学生学习概率问题所需要画的一种图形。

画法

最小树形图，就是给有向带权图中指定一个特殊的点v，求一棵有向生成树T，使得该有向树的根为v，并且T中所有边的总权值最小。最小树形图的第一个算法是1965年朱永津和刘振宏提出的复杂度为O(VE)的算法。

判断是否存在树形图的方法很简单，只需要以v为根作一次图的遍历就可以了，所以下面的算法中不再考虑树形图不存在的情况。

在所有操作开始之前，我们需要把图中所有的自环全都清除。很明显，自环是不可能在任何一个树形图上的。只有进行了这步操作，总算法复杂度才真正能保证是O(VE)。

首先为除根之外的每个点选定一条入边，这条入边一定要是所有入边中最小的。所有的最小入边都选择出来了，如果这个入边集不存在有向环的话，我们可以证明这个集合就是该图的最小树形图。这个证明并不是很难。如果存在有向环的话，我们就要将这个有向环所称一个人工顶点，同时改变图中边的权。假设某点u在该环上，并设这个环中指向u的边权是in[u]，那么对于每条从u出发的边(u, i, w)，在新图中连接(new, i, w)的边，其中new为新加的人工顶点; 对于每条进入u的边(i, u, w)，在新图中建立边(i, new, w-in[u])的边。为什么入边的权要减去in[u]，这个后面会解释，在这里先给出算法的步骤。然后可以证明，新图中最小树形图的权加上旧图中被收缩的那个环的权和，就是原图中最小树形图的权。

上面结论也不做证明了。依据上面的结论，说明一下为什么出边的权不变，入边的权要减去in [u]。对于新图中的最小树形图T，设指向人工节点的边为e。将人工节点展开以后，e指向了一个环。假设原先e是指向u的，这个时候我们将环上指向u的边 in[u]删除，这样就得到了原图中的一个树形图。我们会发现，如果新图中e的权w'(e)是原图中e的权w(e)减去in[u]权的话，那么在我们删除掉in[u]，并且将e恢复为原图状态的时候，这个树形图的权仍然是新图树形图的权加环的权，而这个权值正是最小树形图的权值。所以在展开节点之后，我们得到的仍然是最小树形图。逐步展开所有的人工节点，就会得到初始图的最小树形图了。

如果实现得很聪明的话，可以达到找最小入边O(E)，找环 O(V)，收缩O(E)，其中在找环O(V)这里需要一点技巧。这样每次收缩的复杂度是O(E)，然后最多会收缩几次呢？由于我们一开始已经拿掉了所有的自环，我门可以知道每个环至少包含2个点，收缩成1个点之后，总点数减少了至少1。当整个图收缩到只有1个点的时候，最小树形图就不不用求了。所以我们最多只会进行V-1次的收缩，所以总得复杂度自然是O(VE)了。由此可见，如果一开始不除去自环的话，理论复杂度会和自环的数目有关。

例题

例1、随机掷两枚质地均匀的正方体骰子，骰子的六个面上分别刻有1到6的点数，则这两个骰子向上的一面点数都是奇数的概率为多少？

分析：本题中的事件是掷两枚骰子，看向上的一面点数，由此可确定本事件包括两个环节，掷第一枚骰子和掷第二枚骰子，所以树状图该画两层。第一枚骰子向上的一面的点数可能是1，2，3，4，5，6等6个的一个，所以第一层应画6个分叉；再看第二层，第二枚骰子，向上一面的点数可能是6个的一个，所以第二层应接在第一层的6个分叉上，每个小分支上，再有6个分叉。画出树状图，这样共得到6×6种情况，从中找出两个骰子向上的一面点数都是奇数的情况，再求出概率。

解：画出树状图，如图1。

由图中可以看出，两枚骰子向上的一面点数的可能性情况共36种，其中向上的一面点数都是奇数的情况有（1，1），（1，3），（1，5），（3，1），（3，3），（3，5），（5，1）（5，3）（5，5）共9种情况，从而得两个骰子向上的一面点数都是奇数的概率（记为事件A）为P（A）=9/36=1/4

点评：由本例看出，只要画好了树状图，就很容易求出概率。而画树状图的关键一是确定层数，二是确定每层分叉的个数。

例2、一个口袋中装有红、白、绿三只小球，另一只口袋中装有（除颜色外其余都相同）红、白两只小球。现从两只口袋中各取一只小球，求两只小球颜色一样的概率是多少？

分析：本题从两只口袋中各取一只小球，由此可见事件的环节共两个，树状图画两层。由于一只口袋中装有三只小球，所以此层应有三个分叉。另一只口袋中装有两只小球，拿一个球的可能性有两种，此层可能有两个分叉。各层的分叉要画对。至于两只口袋中哪只放上，哪只放下，可以随便画，不影响结果。

解：画出树状图如下图2（图3也正确）：

从图中可以看出，两只小球颜色的可能性共6种，而两只小球颜色一样的可能性只有（红，红），（白，白）共2种，所以两只小球颜色一样的概率（记为事件A）为P（A）=2/6=1/3

点评：本题与上题不同的是两个口袋的球数不等，所以各层的分叉要根据本层的可能情来确定，这是画树状图最不易掌握的知识点，大家要多加揣摩。

全国各地天气预报查询

上海市

市辖区

云南省