图与网络模型.doc

《图与网络模型.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、课题第五章图与网络模型§5.1图与网络的基本知识§5.2树教学内容1、图与网络的基本概念，连通图，图的矩阵表示，欧拉图与中国邮路问题；2、树的基本概念和性质，图的生成树，最小生成树问题，根树及其应用；教学目标1、理解图、顶点的次、子图、网络、连通图、欧拉图、树以及生成树的概念；2、掌握欧拉定理及其推论，并且会利用欧拉定理解决实际问题；3、掌握寻找最优环游的两种方法：“Fleury”算法和“奇偶点图上作业法”；4、掌握寻找最小生成树的两种方法：“Kruskal算法”和“破圈法”；5、会利用给定权构造“Huffman树”；教学重点1、欧拉定理及其推论，并且会利用欧

2、拉定理解决实际问题；2、掌握寻找最优环游的两种方法：“Fleury”算法和“奇偶点图上作业法”；3、掌握寻找最小生成树的两种方法：“Kruskal算法”和“破圈法”；4、会利用给定权构造“Huffman树”；教学难点1、寻找最优环游的两种方法：“Fleury”算法和“奇偶点图上作业法”；2、寻找最小生成树的两种方法：“Kruskal算法”和“破圈法”；3、会利用给定权构造“Huffman树”；双语教学内容、安排Graph图，connectedgraph连通图，sub-graph子图，tree树network网络，Spanningtree生成树Bipartite

3、二部图minimumspanningtree最小生成树教学手段、措施以板演为主，以多媒体和课堂讨论为辅作业、后记讨论题：P135:T2、T3、T5教学过程及教学设计备注§5.0图论发展史第一阶段：瑞士数学家欧拉（E.Euler）在1736年发表了一篇题为“依据几何位置的解题方法”的论文，有效地解决了哥尼斯城堡“七桥难题”，从此开创了图论的历史新纪元；所谓“七桥难题”是指：18世纪的哥尼斯堡有条普莱格尔河,它有两条支流在城市中心汇合后流入波罗的海。这条河将城市分割成四块:A、C两个小岛和B、D两块陆地（如图5-1）。为通行方便，在四块陆地之间建了七座桥，每到节、

4、假日或傍晚，都有许多居民和大学生来此散步。久而久之,人们发现并热衷于讨论这样一个问题:能否从四块陆地之一出发,走遍每座桥一次且仅一次然后回到出发地?自然有不少人作过实地尝试,但一直未能实现，但同时又不能说明这种方法不存在。1735年,有大学生写信把问题告诉了欧拉,请他帮助解决。欧拉从大家的失败中进行抽象的数学思考,从数学角度成功地解决了问题。欧拉将这个问题归结为如图5-2所示的问题。他用A,B,C,D四点表示河的两岸和小岛，用两点间的连线表示桥。七桥问题变为：从A,B,C,D任意点出发，能否通过每条边一次且仅一次，再回到原点？欧拉证明了这样的走法不存在，并给出

5、了这类问题的一般结论。图5-1图5-2第二阶段：1847年，数学家基尔霍夫（Kirchhoff）运用图论解决了电路理论中的求解联立方程的问题，他引入了“树”的概念，可惜由于他的思想超出了时代的发展而长期未被重视；到1857年，英国数学家凯莱（Cayley）又从化学的角度进一步扩展了“树”的概念，从此图论又有了新的发展。第三阶段：1857年，英国数学家哈密尔顿（Hamilton）发明了一种游戏，他用一个实心正12面体象征地球，正12面体的20个顶点分别表示世界上20座名城，要求游戏者从任一城市出发，寻找一条可经由每个城市一次且仅一次再回到原出发点的路，这就是“环

6、球旅行”问题。如图5-3所示，要在图中找一条经过每个点一次且仅一次的路，能成为哈密尔顿回路。哈密尔顿根据这个问题的特点，给出了一种解法如图5-4所示。第四个阶段：20世纪以后，随着计算机的不断发展，图论也有了突飞猛进的进展，广泛应用于各科领域：如物理、化学、信息论，博弈论，计算机网络，等等；目前图论已经发展成完整的一个数学分支，并且越来越多的数学爱好者倾向于研究图论。§5.1图与网络的基本概念一、图与网络的基本概念1、图的相关概念及其分类引例：在一次聚会中有五位代表其中与，与，与，与，与是朋友，则我们可以用一个带有五个顶点、五条边的图形来表示这五位代表之间的朋

7、友关系（图5-5）:定义1、设是一个非空有限集合，是与不相交的有限集合，一个图是指一个有序二元组，其中称为图的顶点集，称为的边集；，.如引例中五位代表之间的朋友关系可以用图来表示，，，其中：，，，，.定义2、两个端点重合的边称为环；两点之间多于一条边的，称为多重边；不含有环和多重边的图称为简单图。边与顶点的关系有如下几种典型情况：定义3、任意两个顶点之间都有边相连的无向简单图称为完全图，有个顶点的完全图。定义4、图的点集可以分为两个非空子集即：，使得中每一条边的两个端点必有一个端点属于，另一个端点属于，则称为二部图（偶图），记作：。2、顶点的次定义5、以点为端

8、点的边数叫做顶点的次（度），记作:。例