欢迎来到天天文库
浏览记录
ID：39706331
大小：381.31 KB
页数：11页
时间：2019-07-09
《教师培训课件：数学建模中的树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、重要的一类图－树重要的一类图－树连通无圈重要推论：边数＝点数-1(1)证明要点：必有悬挂点去掉一个悬挂点的与之关联的边，仍然是树，且保持关系（1）不断去悬挂点及与之相关联的边，直到只剩一条边树的充要条件连通，边数＝点数-1无圈，边数＝点数-1连通，但添加一条边，必有圈生成连通，但去掉一条边，必不连通从一点到另一点，有一条路且只有一条路相连一般图的生成树实践中树的例子：植物生态、河网水系、某些管理体系应用：用光缆连接各网点，连接各居民点的煤气管道、下水道生成树：保留所有点，保留部分边，所得图为树生成树：保留所有点，保留最少数目的边又保留连通性图的生成树的例子求图的生成树－破圈
2、法求图的生成树－破圈法（例）求图的生成树－染色法（点）求图的生成树－染色法（边）最小生成树应用：光缆总成本最少修改的找生成树方法：破圈时去掉最长边染色（边）时按边由短而长考虑取舍－Kruskal方法染色（点）时按连接已取点和未取点之间连边的最短者－Prim方法Prim算法求最小生成树
此文档下载收益归作者所有
