离散数学辅导图论部分.doc

离散数学辅导——图论部分 关于图论 图论最早起源于一些数学游戏的难题研究，如欧拉所解决的柯尼希斯堡七桥问题，以及在民间广泛流传的一些游戏难题，如迷宫问题、匿门博奕问题、棋盘上马的行走路线问题等。这些古老的难题，当时吸引了很多学者的注意，在这些问题研究的基础上又继续提出了著名的四色猜想，汉米尔顿（环游世界）数学难题。 1847年，图论由于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，显示出越来越大的效果。我们这门课程只是介绍一些基本概念和原理，以及一些典型的应用实例，目的是在今后对计算机有关学科的学习研究时，可以图论的基本知识作为工具。 [知识点] 1、 图、完全图、子图、母图、支撑子图、图的同构 2、 关联矩阵、相邻矩阵 3、 权图、路、最短路径，迪克斯特拉算法（Dijkstra） 4、 树、支撑树、二叉树 5、 权图中的最小树，克鲁斯卡尔算法（Kruskal） 6、 有向图、有向树 本章重点内容： 权图的最短路、二叉树的遍历、权图中的最优支撑树 [疑难解析] 1.本章的概念较多，学习时需要认真比较各概念的含义，如：图、子图、有向图、权图；树、支撑树、二叉树、有向树；路、简单路、回路等，这些都是图的基本概念，今后将在数据结构、数据库、计算机网络等课程中用到。 2. 权图中的最短路 严格执行迪克斯特拉（Dijkstra）算法步骤，从起点起，到每一点求出最短路，然后进行仔细比较，最后到达终点，算出最小权和。 3. 权图中的最优支撑树 权图中的最优支撑树是图中所带权和最小的支撑树，使用克鲁斯卡尔（Kruskal）算法。 [典型例题] 1、 在具有n个顶点的完全图Kn中删去多少条边才能得到树？ 解：n个顶点的完全图Kn中共有n′（n-1）/2条边， n个顶点的树应有n-1条边， 于是，删去的边有：n′（n-1）/2-（n-1）=（n-1）′（n-2）/2 2、 一棵树有两个节点度数为2，一个节点度数为3，三个节点度数为4，问它有几个度数为1的节点？ 解：我们知道一个有限图中，各点的度数总和是边数的2倍；而树中的边数为点数减1。 根据这两点，可知树中各点的度数总和=2*（树中点数-1），设树叶有x个， 于是，2*2+3+3*4+x=2*（2+1+3+x-1） 得，x=9。 上例可推广为“一棵树有n2个节点度数为2，n3个节点度数为3，…，nk个节点度数为k，问它有几个度数为1的节点？”请同学们思考。 3、 利用Kruskal算法求一棵最小生成树。 解：按照Kruskal给出的在权图中求最优支撑树的算法，可生成下面的最优支撑树：（权和为11） 生成的结果不唯一，又如：（权和为11）也是最优支撑树。  4、 求下面有限图中点u到各点间的最短路。（图上数字见教材P231，第3题。） 其中最左节点为u，最右节点为v，其余从左至右，从上至下，依次为u1，u2，…，u5，…，u8）