离散数学 图论-树

在离散数学中，图是一个由点和边组成的抽象数学模型。

其中，树是一种特殊的图，它是一个无环连通图。

在图论中，树扮演了重要的角色，它具有许多有趣的性质和应用。

而生成树则是树的一个特殊子集，它由给定图中的所有顶点和部分边构成。

本文将介绍图的树的基本概念，并探讨生成树的计数方法。

首先，让我们来看看图的树。

树是一种无环连通图，其中任意两个顶点之间存在唯一一条路径。

它具有以下性质：1.n个顶点的树有n-1条边。

这可以通过归纳法证明：当n=1时，结论成立；假设n=k时成立，那么n=k+1时，只需要添加一个顶点和一条边，即可构成n=k+1个顶点的树。

因此，结论成立。

2.连接树上任意两个顶点的边都是桥。

即如果一条边被删除，那么树就会变成两个或更多个不相连的子树。

3.树是一个高度平衡的结构。

对于一个n个顶点的树，任意两个叶子结点之间的路径长度至多相差1。

4.树的任意两个顶点之间有唯一一条路径，路径长度为顶点之间的边数。

接下来，让我们来讨论生成树的计数方法。

生成树是树的一个特殊子集，它是由给定图中的所有顶点和部分边构成。

生成树的计数在图论中具有重要的意义和应用。

对于一个具有n个顶点的连通图来说，其生成树的个数可以通过Cayley公式计算得到。

Cayley公式是由亚瑟·凯利于1889年提出的，它给出了完全图的生成树数目。

据此，我们可以得到生成树的计数公式为：T = n^(n-2)，其中T表示生成树的个数。

此外，还有一种常见的计数方法是基于度数矩阵和邻接矩阵的矩阵树定理。

矩阵树定理由高斯于1847年提出，它提供了一种计算图的生成树个数的方法。

根据矩阵树定理，一个无向图G的生成树数目等于该图度数矩阵的任意一个(n-1)阶主子式的行列式的值。

其中，度数矩阵是一个对角矩阵，它的对角线上的元素为各个顶点的度数。

邻接矩阵则是一个关于顶点间连接关系的矩阵，其中1表示相邻顶点之间存在边，0表示不存在边。

除了数学方法，还存在一种基于图的遍历的计数方法，称为Kirchhoff矩阵树定理。

离散数学是计算机科学中的重要学科，其中生成树是一个重要的概念。

在图论中，生成树是一棵树，它包含了图中的所有顶点，并且是由图边组成的无环连通子图。

生成树在图论中有着重要的应用，特别是在计算机网络、运筹学和电路设计等领域。

生成树的概念与基础就是组成它的边是有限的，并且连接图中的所有顶点，但没有形成圈回到起点。

生成树通常是用来描述一个系统的最小连接方式。

生成树可以应用于计算机网络的设计中，用于构建最小生成树算法，以便在网络中选择最小的数据传输路径。

此外，在运筹学中，生成树被用于求解最小生成树问题，即为一个加权图找到一棵包含所有顶点的生成树，使得树中边的权重之和最小。

在离散数学中，生成树计数是一个重要的研究分支。

生成树计数是指对给定图，计算其生成树的数目。

生成树计数的问题可以通过使用基于图论和组合数学的算法来解决。

通常，生成树计数的问题与相应图的特性和性质密切相关。

对于一个简单图来说，如果图中任意两点之间至少有一条边，那么该图一定存在生成树。

对于有 n 个顶点的连通图来说，它的生成树数量可以通过Cayley公式计算得到。

Cayley公式表明，一个有 n 个标号的顶点的完全图的生成树数量等于 n^(n-2)。

而对于非完全图，生成树的计数问题则较为困难。

在处理非完全图的生成树计数问题时，可以使用基于递归和动态规划的算法来解决。

一个常见的方法是使用Kirchhoff矩阵树定理，它将生成树计数的问题转化为计算矩阵的行列式的问题。

Kirchhoff矩阵树定理提供了一种计算给定图的生成树数目的有效算法，通过计算图的基尔霍夫矢量的一个特征值，可以得到图的生成树的数目。

另一个常见的方法是使用Prufer编码，它是一个用于描述无环连通图的序列。

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

通过对无向图进行Prufer编码，我们可以计算出生成树的数目，并且可以根据生成树的数目来确定该无向图的种类和特征。

离散数学图论（图、树）常考考点知识点总结图的定义和表示1.图：一个图是一个序偶＜V , E ＞，记为G =< V ，E >，其中：① V ={V1,V2,V3,…, Vn}是有限非空集合，Vi 称为结点，V 称为节点集② E 是有限集合，称为边集，E中的每个元素都有V中的结点对与之对应，称之为边③与边对应的结点对既可以是无序的，也可以是有序的表示方法集合表示法，邻接矩阵法2.邻接矩阵：零图的邻接矩阵全零图中不与任何结点相邻接的结点称为孤立结点，两个端点相同的边称为环或者自回路3.零图：仅有孤立节点组成的图4.平凡图：仅含一个节点的零图无向图和有向图5.无向图：每条边都是无向边的图有向图：每条边都是有向边的图6.多重图：含有平行边的图(无向图中，两结点之间包括结点自身之间的几条边；有向图中同方向的边)7.线图：非多重图8.重数：平行边的条数9..简单图：无环的线图10.子图，真子图，导出子图，生成子图，补图子图：边和结点都是原图的子集，则称该图为原图的子图真子图（该图为原图的子图，但是不跟原图相等）11.生成子图：顶点集跟原图相等，边集是原图的子集12.导出子图：顶点集是原图的子集，边集是由顶点集在原图中构成的所有边构成的图完全图（任何两个节点之间都有边）13.完全图：完全图的邻接矩阵主对角线的元素全为0，其余元素都是114.补图：完全图简单图15.自补图：G与G的补图同构，则称自补图16.正则图：无向图G=<V,E>,如果每个顶点的度数都是k，则图G称作k-正则图17.结点的度数利用邻接矩阵求度数：18.握手定理：图中结点度数的总和等于边数的两倍推论：度数为奇数的结点个数为偶数有向图中，所有结点的入度=出度=边数19.图的度数序列：出度序列+入度序列20.图的同构：通俗来说就是两个图的顶点和边之间有双射关系，并且每条边对应的重数相同（也就是可任意挪动结点的位置，其他皆不变）21.图的连通性及判定条件可达性：对节点vi 和vj 之间存在通路，则称vi 和vj 之间是可达的22.无向图的连通性：图中每两个顶点之间都是互相可达的23..强连通图：有向图G 的任意两个顶点之间是相互可达的判定条件：G 中存在一条经过所有节点至少一次的回路24.单向连通图：有向图G 中任意两个顶点之间至少有一个节点到另一个节点之间是可达的判定条件：有向图G 中存在一条路经过所有节点25.弱连通图：有向图除去方向后的无向图是连通的判定条件：有向图邻接矩阵与转置矩阵的并是全一的矩阵26.点割：设无向图G=<V,E>为联通图，对任意的顶点w  V,若删除w及与w相关联的所有边后，无向图不再联通，则w称为割点；27.点割集：设无向图G=<V,E>为连通图，若存在点集 ，当删除 中所有顶点及与V1顶点相关联的所有边后，图G不再是联通的；而删除了V1的任何真子集 及与V2中顶点先关的所有边后，所得的子图仍是连通图，则称V1是G的一个点割集设无向图G=<V,E>为连通图，任意边e  E,若删除e后无向图不再联通，则称e 为割边，也成为桥28.边割集：欧拉图，哈密顿图，偶图（二分图），平面图29.欧拉通路（回路）：图G 是连通图，并且存在一条经过所有边一次且仅一次的通路（回路）称为拉通路（回路）30.欧拉图：存在欧拉通路和回路的图31.半欧拉图：有通路但没有欧拉回路32.欧拉通路判定：图G 是连通的，并且有且仅有零个或者两个奇度数的节点欧拉回路判定：图G 是连通的，并且所有节点的度数均为偶数有向欧拉图判定：图G 是连通的，并且所有节点的出度等于入度33.哈顿密图：图G 中存在一条回路，经过所有点一次且仅一次34..偶图：图G 中的顶点集被分成两部分子集V1,V2，其中V1nV2= o ,V1UV2= V ，并且图G 中任意一条边的两个端点都是一个在V1中，一个在V2中35.平面图：如果把无向图G 中的点和边画在平面上，不存在任何两条边有不在端点处的交叉点，则称图G 是平面图，否则是非平面图36.图的分类树无向树和有向树无向树：连通而不含回路的无向图称为无向树生成树：图G 的某个生成子图是树有向树：一个有向图，略去所有有向边的方向所得到的无向图是一棵树最小生成树最小生成树：设G -< V . E 是连通赋权图，T 是G 的一个生成树，T 的每个树枝所赋权值之和称为T 的权，记为W ( T . G 中具有最小权的生成树称为G 的最小生成树最优树（哈夫曼树）设有一棵二元树，若对所有的树叶赋以权值w1,w2… wn ，则称之为赋权二元树，若权为wi 的叶的层数为L ( wi )，则称W ( T )= EWixL ( wi ）为该赋权二元树的权，W ）最小的二元树称为最优树。

离散数学树
离散数学中的树(Tree)是一种常见的图论结构，它是一种无向、连通且没有简单回路的无向图，或者是一个有向连通图，其中每个节点都只有唯一一个父节点（除了根节点）。

树形结构中的每一个节点都可以视为一个子树的根节点，因为它下面连接了若干个子节点，这样就形成了一棵向下生长的树状结构。

树形结构还有一个重要的特点就是它具有很好的递归性质，因为每个节点下面都可以再建立一棵子树，这样就可以逐层递归地构建出整棵树。

在离散数学中，树被广泛应用于算法设计、数据结构以及对计算机网络和信息系统进行建模等领域。

树的深度和广度优先遍历、树的一些基本性质(如高度、度、叶子节点等)以及树的遍历应用在图的搜索算法、排序、哈夫曼编码、抽象语法树等算法中都有广泛的应用。

树分解定理树分解定理（Tree decomposition theorem）是离散数学中一项重要的定理，它与图的分解和图的算法密切相关。

树分解定理描述了任意图都可以根据其边集的某个树分解表达。

首先，我们来介绍一下树分解的概念。

树分解是对一个无向图进行分解的一种方法。

给定一个无向图G=(V,E)，其中V表示图的顶点集，E表示图的边集。

树分解是将图G分解成一些子图的集合，这些子图采用树的结构组织，且满足如下条件:1. 每个子图都是图G的子图。

2. 每个顶点都属于一个或多个子图。

3. 任意两个子图之间要么没有公共顶点，要么有且只有一个公共顶点。

根据树分解的定义，我们可以得到一个关键结论：每个子图都可以用一个包含该子图所有顶点的集合作为标记。

这就是树分解的核心思想。

树分解定理指出，对于任意的无向图G=(V,E)，存在一个树分解{(B_x, X_x)}，其中B_x是一个子图，X_x是子图B_x的标记集合，满足以下三个条件：1. 图G的每个顶点都属于某个子图，即图G中所有的顶点在树分解的所有子图的标记集合中都有。

2. 图G的每条边都关联于某个子图，即图G中所有的边连接的顶点在树分解的某两个子图的标记集合中都有。

3. 任意的顶点v在树分解的所有子图中的标记集合的交集，称为顶点v的袋，即B_v = ∩{X_x|v∈X_x}。

树分解的每个子图袋的大小要小于等于某个常数k，即B_x ≤ k。

树分解定理的证明非常复杂，可以依靠递归的方法得到。

首先，我们定义以v为根的子图B_v和相应的标记集合X_v。

然后，我们选择树G的深度最大的顶点u，将其从图中删除并得到一个新的图G'。

此时，原图G的每个顶点都属于G'的一个子图，并形成一个包含u的袋B_u。

我们再次选择G'中深度最大的顶点，重复上述操作，直到最后得到只包含一个顶点并且没有边的子图。

这样就得到了一个树分解。

树分解的主要应用领域是图算法和计算理论。

离散数学图论第五节树、有向树、有序树定义连通而不含回路的无向图称为无向树、树。

非循环的连通无向图定理若G=<V,E>为n阶无向图，则下列等价1) G是连通的和非循环的；2) G无自圈，且当v,v’∈V时，皆有唯一一条从v到v’的基本路径；3) G连通，且当v,v’∈V时，e=(v,v’)∈E，G+{e}有唯一的一回路4) G连通，当e∈E 时，G-e是非连通的5) G连通，且n(E)=n-1;6) G是非循环的，且n(E)=n-1定理阶大于1的树至少有两个端点定义每个分支都是树的无向图称为森林定理若森林有n个顶点，m条边和k个分支，则m=n-k定义若树T是无向图G的生成子图，则称T 为G的生成树；T中的边称为树枝，G中不属于T的边称为弦若森林F是无向图G的生成子图，则称F为G的生成森林定理每个无向图都有生成森林，无向图G有生成树当且仅当G连通。

定理设T是连通无向图G=<V,E>的生成树，则在T上添加任一弦e可产生唯一的一个G中只含弦e其余边都是枝的圈。

求连通无向图G的生成树的方法：破圈法、避圈法。

破圈法：找出G的一个回路，删除回路上一条边，此过程一直进行到图中不再含有回路为止。

最后得到的不含回路的连通图就是G的生成树。

例求下图的最小生成树定义设G是无向连通加权图，T为G的生成树，T的所有枝的权之和称为T的权，记为w(T)。

G中权最小的生成树称为G的最小生成树。

1 Kruskal 算法设无向连通图G=<V,E>， G中边e 1,…,e m以按权的递增次序排列，即w(e 1) ≤…≤w(e n)。

第1步：置T为空集,j=1;}不含回路，则第2步：若T∪{ejT←T ∪{e j}，转第3步；否则转第3步第3步：j=j+1。

若j≤m，转第2步；否则结束。

上述算法也可用于求一般无向连通图的生成树，只要将各边的权当作1。

也称为避圈法。

2 Prim算法第1步：置T为空集；第2步：在V中任选一个顶点t，令M={t};第3步：在E中选取权尽可能小的边(u,v)，其中u∈M，v ∈ V-M，将(u,v)放进T，v放进M;第4步：若M≠V，转第3步；否则结束例求下图的最小生成树例下加权图表示7个城市及架起城市间直接通信线路的预测造价，使给出一个设计方案使得各城市间能够通信且总造价最小定义一个有向图D，若不考虑有向边的方向所得的无向图为无向树，称D为有向树。