下载文档原格式
最小生成树的构造离散数学
最小生成树的构造是离散数学技术的重要组成部分，用于解决图形中的最小树问题。
能够有效地构造最小生成树，有助于我们解决复杂的网络优化等问题。
最小生成树是指一个边数最少的连接结点的树，即所有点之间只建立最少的边，使得所有点都连接在一起，称为一棵生成树。
最小生成树建立在图上，是多重图G（V，E）的一棵子树，它满足以下三个条件：1、包含G中的所有n个结点；2、只包含G中m-n+1条边；3、权值最小。
使用最小生成树的边，可以把n个节点连接成一个树，所有边的权重总和最小。
最小生成树的步骤是：1、选择一个结点作为树的根，将它加入到树中；2、以选定的结点为根，从剩余结点中选择权值最小的边，加入到树中；3、继续重复步骤2，直到n-1条边全部加入到树中，从而完成树的构造。
最小生成树有多种构造方式，如Prim和Kruskal算法、动态规划算法等，可以快速和有效地构建最小生成树。
Prim算法从图中原始结点出发，每一步都把一条最短边加入进去；Kruskal算法从图中原始边出发，每次都把一条最短边加入进去；动态规划算法是在Graph-MST网络上使用的，可以用来解决复杂的路径优化等问题。
总之，最小生成树的构造是离散数学的重要技术，能够有效地构建最小生成树，从而解决复杂的网络优化问题。
最小生成树的构造有不同的方法，要想更好地理解和使用，就需要深刻掌握其原理和实现方法。
最小生成树解法
最小生成树(Minimum Spanning Tree, MST)是指一棵图的生成树，其所有边的权值之和最小。
在计算最小生成树问题时，切图算法(Prim)和克鲁斯卡尔算法(Kruskal)是两种常用的解法。
切图算法从一个源点开始，依次将与源点相连的边加入树中，同
时将与该边相连的节点加入集合，然后在新集合中选取一条连接已选
节点和未选节点的最短边加入树，并将新的节点也加入集合中。
直至
所有节点都被加入树中。
克鲁斯卡尔算法则是将边按照权值从小到大排序，依次取边加入
树中，在加入前需判断该边是否会形成环，若不会则加入树中，并将
该边的两个节点视为已连接。
直至所有节点都被加入树中。
两种算法时间复杂度均为O(ElogE)，其中E为边数。
但Prim算法更适合求解稠密图，而Kruskal算法则比较适合求解稀疏图。
最小树与最小树形图（数学建模）讲解一、最小树的定义及性质1. 定义：最小树，又称最小树，是指在给定的带权无向图中，包含图中所有顶点的一个树形结构，且树中所有边的权值之和最小。
2. 性质：（1）最小树中不存在回路；（2）对于最小树中的任意两个顶点，它们之间有且仅有一条路径；（3）最小树中边的数量等于顶点数量减一；（4）在最小树中添加任意一条边，都会形成一条回路；（5）最小树不唯一，但权值之和相同。
二、求解最小树的方法1. Prim算法Prim算法是一种贪心算法，其基本思想是从图中的一个顶点开始，逐步添加边和顶点，直到形成最小树。
具体步骤如下：（1）初始化：选择一个顶点作为最小树的起点，将其加入最小树集合；（2）迭代：在最小树集合和非最小树集合之间，寻找一条权值最小的边，将其加入最小树集合；（3）重复步骤2，直到所有顶点都加入最小树集合。
2. Kruskal算法Kruskal算法同样是一种贪心算法，其基本思想是将图中的所有边按权值从小到大排序，然后依次选择权值最小的边，判断是否形成回路，若不形成回路，则将其加入最小树集合。
具体步骤如下：（1）初始化：将所有顶点视为独立的树；（2）按权值从小到大排序所有边；（3）迭代：选择权值最小的边，判断其是否形成回路，若不形成回路，则将其加入最小树集合；（4）重复步骤3，直到所有顶点都在同一棵树中。
三、最小树形图的定义及求解方法1. 定义：最小树形图，又称最优树形图，是指在给定的有向图中，找到一个包含所有顶点的树形结构，使得树中所有边的权值之和最小。
2. 求解方法：朱刘算法（Edmonds' Algorithm）朱刘算法是一种用于求解最小树形图的算法，其基本思想是通过寻找图中的最小权值环，进行收缩和扩展操作，最终得到最小树形图。
具体步骤如下：（1）寻找最小权值环；（2）对最小权值环进行收缩操作，将环中的顶点合并为一个新顶点；（3）在新图中寻找最小树形图；（4）将新图中的最小树形图扩展回原图，得到原图的最小树形图。
详解图的应用（最小生成树、拓扑排序、关键路径、最短路径）1.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树1.1 问题背景：假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。
这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。
在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。
n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢?1.2 分析问题（建立模型）：可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。
对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。
即无向连通图的生成树不是唯一的。
连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。
图G5无向连通图的生成树为(a)、(b)和(c)图所示：G5G5的三棵生成树：可以证明，对于有n 个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1 条边。
1.3最小生成树的定义：如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。
最小生成树的性质：假设N=(V,{ E}) 是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中，则必存在一棵包含边（u,v）的最小生成树。
1.4 解决方案：两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。
他们都利用了最小生成树的性质1.普里姆（Prim）算法：有线到点，适合边稠密。
时间复杂度O(N^2)假设G＝（V，E）为连通图，其中V 为网图中所有顶点的集合，E 为网图中所有带权边的集合。
第7章：有向图很多应用问题涉及有向图。
有向图除了有与（无向）图类似的性质之外，还有一些在图中所不具备的特殊性质。
本章除介绍有向图的基本概念外，着重介绍有向树、有向网络及其应用等问题。
§7.1有向图概述1. 基本概念定义7.1 一个有向图D 是指一个序偶><E V ，，其中V 是一个非空集合，称为D 的点集，其中的元称为D 的顶点。
E 是笛卡儿集V V ⨯的某个多重子集，称为D 的边集，其中的每一个元素均是序偶><v u ，，称为有向边，而u 称为边的始点，v 称为边的终点。
通常记>=<E V D ，，)(D V V =，)(D E E =。
从有向图的定义来看，它与上一章定义的（无向）图是相似的，最关键的区别在于有向边是有方向的，而（无向）边是无方向的。
在（无向）图中， )(v u ，和)(u v ，表示同一条边（不考虑多重边情况），但在有向图中，><v u ，和><u v ，表示的却是两个不同的边，称为对称边，虽然这两条边的端点一样。
对无向图G 的每条无向边指定一个方向，由此得到的有向图D ，称为G 的定向图。
反之，如果把一个有向图D 的每条有向边的方向去掉，由此而得到的无向图G ，称为D 的底图。
把一个有向图D 的每一条有向边反向，由此而得到的有向图称为D 的逆图，记为D ~在有向图中，两个顶点之间若有两条或两条以上的边，并且方向相同，则称为平行边，它强调了边的方向性。
有向图中的其它一些概念，像重数、圈、带圈图、无圈图、多重图、简单图、)(q p ，图、图的阶、平凡图、零图、有限图、无限图、赋权图、邻接、关联、孤立点、孤立边等等，都与（无向）图中相应概念的定义一样，这里不再重复。
在有向图中有如下的度数定义。
定义7.2 设>=<E V D ，是有向图， V v ∈，E 中以v 为起始点的有向边的个数称为v 的出度，记作)(v d +；E 忠以v 为终点的有向边的个数称为v 的入度，记作)(v d -。
【算法】关于图论中的最⼩⽣成树（MinimumSpanningTree）详解什么是图(network)什么是最⼩⽣成树 (minimum spanning tree)最⼩⽣成树的算法这⾥的图当然不是我们⽇常说的图⽚或者地图。
通常情况下，我们把图看成是⼀种由“顶点”和“边”组成的抽象⽹络。
在各个“顶点“间可以由”边“连接起来，使两个顶点间相互关联起来。
图的结构可以描述多种复杂的数据对象，应⽤较为⼴泛，看下图：为了更好地说明问题，下⾯我们看⼀个⽐较⽼套的通信问题：在各⼤城市中建设通信⽹络，如下图所⽰，每个圆圈代表⼀座城市，⽽边上的数字代表了建⽴通信连接的价格。
那么，请问怎样才能以最⼩的价格使各⼤城市能直接或者间接地连接起来呢？我们需要注意两点：最⼩的价格各⼤城市可以是直接或者间接相连的稍稍留⼼可以发现，题⽬的要求是，城市只需要直接或者间接相连，因此，为了节省成本，我们稍稍优化⼀下上述⽅案如下：可以看到，我们砍掉了原先在AD，BE之间的两条道路，建设价格⾃然就降下来了。
当然这个⽅案也是符合我们题⽬的要求的。
按照国际惯例，这⾥要说蛋是了。
上⾯的实例由于数据很简单，优化的⽅案很easy就看出来了。
但在实际中，数据量往往是⾮常庞⼤的。
所以，我们更倾向于设计⼀种⽅法，然后利⽤计算机强⼤的运算能⼒帮我们处理这些数据得出最优的⽅案。
那么，针对上述问题，我们⼀起来看看如何应⽤图的相关知识来实现吧。
为了直观，还是⽤图⽚给⼤家解释⼀下：对于⼀个图⽽⾔，它可以⽣成很多树，如右侧图2，图3就是由图1⽣成的。
从上⾯可以看出⽣成树是将原图的全部顶点以最少的边连通的⼦图，对于有n个顶点的连通图，⽣成树有n-1条边，若边数⼩于此数就不可能将各顶点连通，如果边的数量多于n-1条边，必定会产⽣回路。
对于⼀个带权连通图，⽣成树不同，树中各边上权值总和也不同，权值总和最⼩的⽣成树则称为图的最⼩⽣成树。
基本思想：假设有⼀个⽆向带权图G=(V,E)，它的最⼩⽣成树为MinTree=(V,T)，其中V为顶点集合，T为边的集合。
