第9章 节 图 电子科大离散数学内部.ppt

离 散 数 学;第四篇 图论;引言;哥尼斯堡七桥问题和欧拉;基本博弈问题-囚徒的困境;教学目标;第9章 图;9.0 内容提要 ;9.1 本章学习要求;9.2 图的基本概念 ;例9.2.1（2）;例9.2.1（3）;基本思想 ;定义9.2.1;与边相关的几个概念;9.2.2 图的表示 ;例9.2.2;例9.2.2 分析;例9.2.2 解;例9.2.3 ;两种描述方法的优缺点;图的矩阵表示;定义9.2.2;例9.2.4;说明;例;9.2.3 图的操作 ;定义9.2.3（续）;9.2.4 邻接点与邻接边 ;例9.2.5;例9.2.5 分析;例9.2.5 解;9.2.5 图的分类 ;例9.2.6;说明;2. 按有无平行边分类 ;例9.2.7;3. 按边或结点是否含权分类 ;例9.2.8;例9.2.8 解;赋权图的一个应用;注;9.2.6 子图与补图 ;例9.2.9;定义9.2.9;例;定义9.2.10;例9.2.10;利用邻接矩阵描述补图 ;例9.2.11;证明;9.2.7 结点的度数与握手定理;例9.2.12;利用邻接矩阵描述 ;利用邻接矩阵描述;例9.2.12（续）;定理9.2.1(握手定理);推论9.2.1;定理9.2.2;定义9.2.12;例9.2.14;9.2.8 图的同构 ;定义9.2.13;两个图同构的必要条件;例9.2.14;另一组判断同构的例子;例9.2.15;9.2.9 图的难点 ;9.2.10 图的应用 ;通讯网络;9.3 通路、回路与连通性 ;9.3.1 通路与回路 ;定义9.3.1 （续）;定义9.3.1 ;说明;例9.3.1;例9.3.1 分析;例9.3.1 分析;例9.3.1 解;例9.3.1 解（续）;说明;定理9.3.1;定理9.3.1 分析;定理9.3.1 分析(续);定理9.3.1 分析(续);定理9.3.1 分析(续);定理9.3.1 分析(续);定理9.3.1 证明;例9.3.2;例9.3.2 解;例9.3.2 解(续);例9.3.2 解(续);例9.3.2 解(续);例9.3.2 解(续);定义9.3.2;说明;定理9.3.2;定理9.3.2 证明;几个结论;利用邻接矩阵判断可达;定理9.3.4;例9.3.3;例9.3.3 解;例9.3.3 解(续);定义9.3.3;说明;定理9.3.5;例9.3.4;例9.3.4 解 (续);例9.3.4 解 (续);9.3.2 无向图的连通性 ;定理9.3.6;定理9.3.6 证明;说明;定义9.3.5;例9.3.5;9.3.3 有向图的连通性;例9.3.6;定理9.3.7;利用A和P判断有向图的连通性;定义9.3.6;注;例9.3.7;例9.3.7 解;一个关系;三个定理;例;9.3.4 通路、回路与连通性的难点 ;9.3.5 通路、回路与连通性的应用 ;例9.3.7 解(续);例9.3.7 解(续);2、均分问题 ;例9.3.8 解 ;3、无向赋权图的最短通路 ;（1）求给定两结点间的最短通路—Dijkstra算法 ;算法9.3.1 Dijkstra算法 ;算法9.3.1 Dijkstra算法(续);说明;例9.3.9;例9.3.9 解;例9.3.9 解 (续);（2）求任意两结点间的最短通路——Floyd算法 ;Floyd算法;例9.3.10;例9.3.10 解;例9.3.10 解(续);例9.3.10 解(续);9.4 本章总结;1、主要知识点汇集;2、习题类型;3、解题分析和方法;作业;Thank You !