（二） 树与图的最小生成树

学习重难点：树图的定义、最小生成树的定义，最小生成树算法：避圈法和破圈法

在地下管道铺设等问题中，经常涉及到费用最小的问题：从天然气管道铺设问题提出，作为信息与计算科学专业，要更具有环境保护意识，加强清洁能源使用意识，为国家社会的建设发展出自己的一份力，一种简单的最小费用管道铺设就是最小的树图。

树图的结构与我们的家族族谱，铁路沿线分支等结构一致。中国文化源远传承，家谱象征了中国人的血脉相承，家是社会的细胞，每一个小家组成大的国，每个人都要为祖国的强大和繁荣贡献自己的热血和青春的责任与义务，教育学生要认真读书，勤奋学习，为建设美丽的组合和家乡奉献自己的力量，培养学生深深的家国情怀，而高铁的建设，中国交通的飞速发展与每个建设一线的工作者的爱国情怀都有着莫大的关系，是他们的精益求精，是他们的追逐创新所成就的。

下面一起学习下树图如何来进行定义的，又如何来寻找一个图的最小生成树呢？

最小生成树算法：

避圈法算法思想：

这种方法就是在已给的图中，每步选出一条尽可能小的边使它与已选边不构成圈，直到选够n-1条边为止. 这种方法可称为“避圈法”或“加边法”。

破圈法算法思想：

   这种方法就是从已给的图中任取一回路，去掉这个回路中权重最大的一条边，得到一网络子图.在中再任取一回路，去掉回路中权重最大的一条边，得。如此继续下去，一直到剩下的子图中不再包含回路为止。这种方法可称为“破圈法”或“减边法”。

树与图的最小生成树

注：本视频片段剪辑来源于哔哩哔哩睿智课堂发布

最小生成树算法matlab实现

注：本视频引自哔哩哔哩数学建模BOOM发布

完成实验作业六，并上传至对应作业模块。