离散数学中的图的树与生成树的计数

离散数学组合计数
离散数学中的组合计数是指研究一定范围内的元素选取，计算选
取方式总数的方法。

它主要包括排列、组合、二项式定理、斯特林数、欧拉数、生成函数等内容。

其中，排列是指从一组元素中选取若干个不同的元素，然后按一
定的顺序排列的方法数；组合是指从一组元素中选取若干个不同的元素，不考虑其顺序的选取方式总数。

二项式定理是组合计数中的基本
公式，它描述了任意两个数的幂与二项式系数之间的关系。

斯特林数
和欧拉数则是描述排列和组合问题中的一些性质和规律的重要工具，
而生成函数则是描述组合计数问题的一种通用方法。

组合计数在离散数学中起着重要的作用，它不仅在数学理论研究
中具有广泛的应用，还在计算机科学、统计学、物理学等学科中发挥
着重要的作用。

在离散数学中，生成树（Spanning Tree）是一个图（Graph）的子图，它包含图中的所有顶点，并且是一个树（Tree）。

生成树的一个重要性质是它不包含任何环（Cycle）。

求一个给定图的生成树个数是一个经典问题，通常使用矩阵树定理（Matrix Tree Theorem）来解决。

矩阵树定理给出了一个图的生成树个数的计算公式，它基于图的拉普拉斯矩阵（Laplacian Matrix）的行列式。

拉普拉斯矩阵是一个方阵，其大小为图的顶点数，矩阵的元素定义如下：•如果i和j是不同的顶点，则矩阵的第i行第j列的元素是顶点i和j之间的边的权重（如果存在边的话），否则是0。

•对于每个顶点i，矩阵的第i行第i列的元素是顶点i的度（即与顶点i相邻的边的数量）的负值。

矩阵树定理指出，图的生成树个数等于其拉普拉斯矩阵的任何一个n-1阶主子式的行列式值的绝对值。

n是图的顶点数，n-1阶主子式意味着去掉矩阵中的一行和一列后得到的矩阵。

下面是一个简单的例子，说明如何使用矩阵树定理计算生成树的个数：假设有一个包含4个顶点的简单图，其边和权重如下：A -- 2 -- B| |1 3 1| |C -- 4 -- D1 -3 1 00 1 -3 40 0 1 -4主子式的行列式值。

去掉第一行和第一列后，我们得到：1 01 -3 40 1 -4x3矩阵的行列式，我们得到：1 * 1) - (0 * 0) = 12 - 1 = 11过程可能涉及复杂的行列式计算，特别是对于大型图来说。

在实际应用中，通常会使用专门的数学软件或库（如Python中的NumPy或SciPy）来进行这些计算。

此外，还有一些算法（如Kruskal算法和Prim算法）可以用来构造生成树，但它们并不直接计算生成树的总数。

这些算法通常用于找到图的一个生成树，而不是计算所有可能的生成树的数量。

离散树知识点总结一、基本概念1. 什么是树树是一种特殊的图，它是一种没有回路的无向图。

树是由 n 个节点和 n-1 条边组成的连通图。

2. 树的特点树是一个具有以下特点的无向图：- 无环。

树中不存在回路，即不存在从一个节点出发经过若干条边再回到出发点的路径。

- 连通。

树是一个连通图，即从树的任意一个节点出发，都可以到达树的所有其他节点。

- n 个顶点和 n-1 条边。

树由 n 个顶点和 n-1 条边组成。

3. 树的术语- 节点（Node）：树中的每一个元素都称为节点。

- 父节点（Parent）：在树中，每个节点都有一个父节点，除了根节点没有父节点。

- 子节点（Children）：一个节点的子节点是指它的相邻节点。

- 根节点（Root）：树中从哪个节点开始，就是根节点。

- 叶子节点（Leaf）：没有子节点的节点称为叶子节点。

- 度（Degree）：一个节点的子节点的个数称为该节点的度。

- 高度（Height）：树中的最长路径的边数。

4. 树的表示树可以用多种方式表示，最常用的方式有：孩子表示法、双亲表示法、孩子兄弟表示法和层次表示法。

5. 树的应用树在计算机科学中有广泛的应用，例如用于构建数据结构，构建层次化的目录结构等。

常见的树结构有二叉树、二叉搜索树（BST）、平衡二叉树（AVL）、红黑树、B树、B+树等。

二、树的遍历1. 深度优先遍历（DFS）深度优先遍历是一种递归的遍历方式，它分为先序遍历、中序遍历和后序遍历三种方式。

- 先序遍历（Preorder）先序遍历的顺序是先遍历根节点，然后递归地遍历左子树和右子树。

- 中序遍历（Inorder）中序遍历的顺序是先递归地遍历左子树，然后遍历根节点，最后递归地遍历右子树。

- 后序遍历（Postorder）后序遍历的顺序是先递归地遍历左子树和右子树，然后遍历根节点。

2. 广度优先遍历（BFS）广度优先遍历是一种逐层遍历的方式，它从根节点开始，按照层次遍历树的节点。

图论中的生成树计数算法在图论中，生成树是指一个无向连通图的一个子图，它包含图中的所有顶点，并且是一个树。

生成树计数算法是指计算一个无向连通图中生成树的数量的方法。

本文将介绍图论中的一些常见生成树计数算法。

1. Cayley公式Cayley公式是最简单的生成树计数算法之一，它适用于完全图。

完全图是指图中的任意两个不同顶点之间都有一条边相连。

假设完全图有n个顶点，那么生成树的数量为n^(n-2)个。

Cayley公式的证明可以利用普鲁夫树（Prüfer Tree）的概念，这里不再详述。

2. Kirchhoff矩阵树定理Kirchhoff矩阵树定理是另一种生成树计数算法，它适用于任意连通图。

矩阵树定理的原理是利用图的拉普拉斯矩阵（Laplacian Matrix）的性质。

图的拉普拉斯矩阵定义为：对于一个n个顶点的图，其拉普拉斯矩阵L的定义为：L=D-A，其中D是一个对角矩阵，对角线上的元素是该顶点的度数，A是图的邻接矩阵。

根据Kirchhoff矩阵树定理，一个图的所有生成树的数量等于该图的任意一个n-1阶主子式的行列式的绝对值。

主子式是指原矩阵去掉若干行和列后形成的子矩阵。

基于这个定理，我们可以通过计算图的拉普拉斯矩阵的主子式来得到生成树的数量。

3. Prufer编码Prufer编码是一种用序列表示带标号图中生成树的方法。

给定一个有n个顶点的生成树T，Prufer编码可以将T转化为一个长度为n-2的序列，该序列的元素由图中的顶点标号组成。

具体的编码方法如下：- 第一步：选择标号最小的叶子节点，并将与之相邻的节点记录下来。

- 第二步：删除该叶子节点，并将该叶子节点的标号记录下来。

- 重复以上两步，直到所有顶点都被删除为止。

通过Prufer编码，我们可以将生成树的计数问题转化为序列的计数问题。

在给定n个顶点的情况下，长度为n-2的Prufer序列的数量为n^(n-2)。

除了上述介绍的几种生成树计数算法外，还有其他更复杂的算法，如Chow定理、Matrix-Tree定理等。

离散数学知识点
离散数学是数学中的一个分支，它主要涉及离散对象和离散结构的研究。

下面将介绍离散数学的一些主要知识点。

1. 集合论：集合是离散数学中的基础概念，集合论研究集合的性质与运算。

它包括集合的定义、运算、关系、等价关系、函数和逆映射等概念。

2. 图论：图论是研究图及其性质的数学分支。

图是由节点（或称为顶点）和边组成的数学模型。

它的重点包括图的分类、图的遍历、最短路径、生成树、染色问题等。

3. 逻辑学：逻辑学是研究推理和论证的学科，在离散数学中应用广泛。

逻辑学包括命题逻辑、谓词逻辑、组合逻辑、模态逻辑等多个分支。

4. 组合数学：组合数学是研究离散结构中离散对象的组合方式的数学分支。

它包括组合计数、排列组合、生成函数、递归等概念。

5. 离散数学在计算机科学中的应用：离散数学在计算机科学中应用广泛，例如计算机算法、图像处理、密码学、编译器等领域都有着重要的应用。

以上是离散数学的主要知识点，它们都有着广泛的应用和研究领域，对于理解和
应用离散数学具有重要作用。

在离散数学中，图是研究的重要对象之一。

图由节点和连边组成，可以用来描述许多实际问题，比如社交网络、交通网络等等。

在图的研究中，连通分量和最小生成树是两个重要的概念。

首先，我们来介绍连通分量。

在一个图中，如果任意两个节点之间存在路径，那么这个图被称为是连通的。

如果一个连通图的任意两个节点之间不存在路径，并且如果将其中的任何一个节点移除后，剩下的子图也不再连通，那么这个图的连通部分被称为是连通分量。

连通分量可以将一个复杂的图分割为若干个互不相交的子图，每个子图都是一个连通图。

连通分量在许多应用中有着重要的意义。

例如，在社交网络中，每个人可以看做是一个节点，而他们之间的关系可以用边来表示。

如果某个社交圈的人之间相互认识，那么他们就属于同一个连通分量。

通过分析连通分量，可以了解社交网络中的人际关系、信息传递等情况。

另一个重要的概念是最小生成树。

最小生成树是指一个连通图的最小权重的生成树，其中每个节点都连接在一起，并且总权重达到最小。

生成树是保留了原图中部分边的子图，该子图包含了原图的所有节点，但是其中的边数比原图少一。

最小生成树则是在所有生成树中权重最小的一种。

最小生成树可以用来优化资源分配、路径规划等问题。

最小生成树的算法有很多种，其中一种常用的算法是Prim算法。

Prim算法从一个起始节点开始，逐步扩展生成树的边。

每次选择与已经生成的树相连的边中权重最小的边。

然后，继续选择与生成树相连的边中权重最小的边，直到生成树包含了所有的节点。

另一个常用的算法是Kruskal算法。

Kruskal算法从边的权重最小的边开始，依次将未加入生成树中且不会形成环的边加入生成树中。

然后，继续选择权重次小的边，直到生成树包含了所有的节点。

最小生成树可以用来解决一些实际问题。

例如，在一个城市的交通网络中，每个路口可以看成是一个节点，而道路可以看成是边。

通过最小生成树算法，可以找到将所有路口连接起来的最短路径，从而优化城市交通的规划。

《离散数学》第九章树讲稿9.1 无向树及生成树一、本节主要内容无向树、森林树枝、弦、余树生成树基本回路与基本回路系统基本割集与基本割集系统最小生成树无向树二、教学内容无向树(树): 连通而无回路的无向图，用T表示.平凡树: 平凡图森林: 每个连通分支都是树的非连通的无向图树叶: 树中度数为1的顶点分支点: 树中度数≥2的顶点右图为一棵12阶树.声明:本章中所讨论的回路均指简单回路或初级回路无向树的性质定理9.1 设G=是n阶m条边的无向图，则下面各命题是等价的：（1）G是树(连通无回路);（2）G中任意两个顶点之间存在惟一的路径;（3）G中无回路且m=n-1;（4）G是连通的且m=n-1;（5）G是连通的且G中任何边均为桥;（6）G中没有回路, 但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈.无向树的性质(续)例题例1 已知无向树T中, 有1个3度顶点, 2个2度顶点, 其余顶点全是树叶. 试求树叶数, 并画出满足要求的非同构的无向树.解用树的性质m=n-1和握手定理.设有x片树叶，于是n=1+2+x=3+x,2m=2(n-1)=2?(2+x)=1?3+2?2+x解出x=3，故T有3片树叶.T的度数列为1, 1, 1, 2, 2, 3有2棵非同构的无向树, 如图所示例题例2 已知无向树T有5片树叶, 2度与3度顶点各1个, 其余顶点的度数均为4. 求T的阶数n, 并画出满足要求的所有非同构的无向树.解设T的阶数为n, 则边数为n-1, 4度顶点的个数为n-7. 由握手定理得2m=2(n-1)=5?1+2?1+3?1+4(n-7)解出n=8, 4度顶点为1个.T的度数列为1,1,1,1,1,2,3,4有3棵非同构的无向树生成树生成树的存在性定理任何无向连通图都有生成树.证用破圈法. 若图中无圈, 则图本身就是自己的生成树.否则删去圈上的任一条边, 这不破坏连通性, 重复进行直到无圈为止,剩下的图是一棵生成树.推论1 设n阶无向连通图有m条边, 则m≥n-1.推论2 设n阶无向连通图有m条边, 则它的生成树的余树有m-n+1条边.基本回路与基本回路系统定义设T是n阶m条边的无向连通图G的一棵生成树，设e1', e2', … , e'm-n+1为T的弦. 设Cr为T添加弦er' 产生的G中惟一的圈(由er'和树枝组成), 称Cr为对应弦er'的基本回路或基本圈, r=1, 2, …, m-n+1. 称{C1,C2, …, Cm-n+1}为对应T的基本回路系统.求基本回路的算法: 设弦e=(u,v), 先求T中u到v的路径Γuv, 再并上弦e, 即得对应e的基本回路.基本割集与基本割集系统定义设T是n阶连通图G的一棵生成树, e1', e2', …,e'n-1为T的树枝，Si是G的只含树枝ei', 其他边都是弦的割集, 称Si为对应生成树T由树枝ei'生成的基本割集, i=1, 2, …, n-1. 称{S1, S2, …, Sn-1}为对应T的基本割集系统.求基本割集的算法: 设e '为生成树T 的树枝, T -e '由两棵子树T1与T2组成, 令Se '={e | e ∈E(G)且e 的两个端点分别属于T1与T2}则Se '为e '对应的基本割集.实例例图中红边为一棵生成树,求对应它的基本回路系统与基本割集系统解弦e,f,g 对应的基本回路分别为Ce=e b c, Cf=f a b c, Cg=g a b c d,C 基={Ce, Cf, Cg}.树枝a,b,c,d 对应的基本割集分别为Sa={a, f, g}, Sb={b, e, f, g}, Sc={c, e, f g}, Sd={d, g},S 基={Sa, Sb, Sc, Sd}.无向图与最小生成树对无向图或有向图的每一条边e 附加一个实数w(e), 称作边e 的权. 图连同附加在边上的权称作带权图, 记作G=.设G '是G 的子图, G '所有边的权的和称作G '的权, 记作W(G ').最小生成树: 带权图权最小的生成树求最小生成树的算法——避圈法 (Kruskal)设G=, 将非环边按权从小到大排序：e1, e2, …, em.(1) 取e1在T 中(2) 检查e2, 若e2与e1不构成回路, 则将e2加入T 中, 否则弃去e2.(3) 检查e3,…, 重复进行直至得到生成树为止.实例例求图的一棵最小生成树9.2根树及其应用一、本节主要内容有向树根树、树根、树叶、内点、分支点家族树、根子树、有序树r元树（r元有序树）r元正则树（r元有序正则树）r元完全正则树（r元有序完全正则树）最优2元树与Huffman算法前缀吗与最佳前缀吗中序行遍法、前序行遍法、后续行遍法波兰符号法与逆波兰符号法二、教学内容有向树与根树的定义有向树: 基图为无向树的有向图根树: 有一个顶点入度为0, 其余的入度均为1的非平凡的有向树树根: 有向树中入度为0的顶点树叶: 有向树中入度为1, 出度为0的顶点内点: 有向树中入度为1, 出度大于0的顶点分支点: 树根与内点的总称顶点v的层数: 从树根到v的通路长度树高: 有向树中顶点的最大层数根树(续)根树的画法:树根放上方,省去所有有向边上的箭头如右图所示a是树根b,e,f,h,i是树叶c,d,g是内点a,c,d,g是分支点a为0层;1层有b,c; 2层有d,e,f;3层有g,h; 4层有i.树高为4家族树定义把根树看作一棵家族树:(1) 若顶点a 邻接到顶点b, 则称b 是a 的儿子, a 是b 的父亲;(2) 若b和c为同一个顶点的儿子, 则称b和c是兄弟;(3) 若a b且a可达b, 则称a是b的祖先, b是a的后代. 设v为根树的一个顶点且不是树根, 称v及其所有后代的导出子图为以v为根的根子树.根树的分类有序树: 将根树同层上的顶点规定次序r元树:根树的每个分支点至多有r个儿子r元正则树: 根树的每个分支点恰有r个儿子r元完全正则树: 树叶层数相同的r元正则树r元有序树: 有序的r元树r元正则有序树: 有序的r元正则树r元完全正则有序树: 有序的r元完全正则树最优2元树求最优树Huffman算法:给定实数w1, w2, …, wt,①作t片树叶, 分别以w1, w2, …, wt为权.②在所有入度为0的顶点(不一定是树叶)中选出两个权最小的顶点, 添加一个新分支点, 以这2个顶点为儿子, 其权等于这2个儿子的权之和.③重复②, 直到只有1个入度为0 的顶点为止.W(T)等于所有分支点的权之和实例例求带权为1, 1, 2, 3, 4, 5的最优树.解题过程由下图给出，W(T)=38前缀码设α =α1α2…αn-1αn是长度为n的符号串α的前缀: α1α2…αk , k=1,2,…,n-1前缀码: {β1, β2,…, βm}, 其中β1, β2, …, βm为非空字符串, 且任何两个互不为前缀2元前缀码: 只出现两个符号(如0与1)的前缀码如{0,10,110, 1111}, {10,01,001,110}是2元前缀码{0,10,010, 1010} 不是前缀码前缀码(续)一棵2元树产生一个二元前缀码:对每个分支点, 若关联2条边, 则给左边标0, 右边标1;若只关联1条边, 则可以给它标0(看作左边), 也可以标1(看作右边). 将从树根到每一片树叶的通路上标的数字组成的字符串记在树叶处, 所得的字符串构成一个前缀码.如右图所示最佳前缀码例在通信中，设八进制数字出现的频率如下：0：25% 1：20% 2：15% 3：10%4：10% 5：10% 6：5% 7：5%采用2元前缀码, 求传输数字最少的2元前缀码(称作最佳前缀码), 并求传输10n(n≥2)个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的(长为3) 的码字传输需要多少个二进制数字?解用Huffman算法求以频率(乘以100)为权的最优2元树. 这里w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25. 最优2元树如图所示.编码:0---011---112---0013---1004---1015---00016---000007---00001传100个按比例出现的八进制数字所需二进制数字的个数为W(T)=285.传10n(n≥2)个所用二进制数字的个数为2.85?10n, 而用等长码(长为3)需要用3?10n个数字.波兰符号法与逆波兰符号法行遍(周游)根树T : 对T 的每个顶点访问且仅访问一次.行遍2元有序正则树的方式：①中序行遍法: 左子树、根、右子树②前序行遍法: 根、左子树、右子树③后序行遍法: 左子树、右子树、根例如, 对图所示根树按中序、前序、后序行遍法访问结果分别为：b a (f d g)c e a b (c (d f g) e) b ((f g d)e c) a带下划线的是(子)树根, 一对括号内是一棵子树波兰符号法与逆波兰符号法(续)用2元有序正则树表示算式: 最高层次运算放在树根上, 然后依次将运算符放在根子树的根上, 数放在树叶上, 规定被除数、被减数放在左子树树叶上.例如, 右图表示算式((b+(c+d))*a)÷((e*f)-(g+h)*(i*j))波兰符号法与逆波兰符号法(续)波兰符号法(前缀符号法): 按前序行遍法访问表示算式的2元有序正则树, 其结果不加括号, 规定每个运算符号与其后面紧邻两个数进行运算.例如, 对上页中树的访问结果为÷*+ b + c d a -* e f * + g h * i j逆波兰符号法(后缀符号法): 按后序行遍法访问,规定每个运算符与前面紧邻两数运算.例如, 对上页中树的访问结果为b c d + + a * e f * g h + i j **-÷。