离散数学及其应用--第2版 课件汇总 第7--12章 高级计数技术---格和布尔代数.pptx

第7章高级计数技术;第7章高级计数技术;7.1递推方程;例题;例题（续）;例题;例题（续）;常系数线性齐次递推方程的求解;常系数线性齐次递推方程的求解;定理;;定理;例题;定理;例题;例题（续）;常系数线性非齐次递推方程的求解;;例题;例题（续）;7.2生成函数;牛顿二项式系数与牛顿二项式定理;定理;生成函数的定义及其性质;例题;生成函数的性质;生成函数的性质(续）;例题;例题;生成函数的应用;例题（续）;指数型生成函数;例题;定理;例题;例题;第8章图论;图论;第8章图;A;最早引入图论处理的问题就是哥尼斯堡七桥问题。

1736年，瑞士数学家L.Eluer（欧拉）在他发表的“哥尼斯堡七座桥”的著名文章中阐述了解决这个问题的观点，从而被誉为图论之父。;Euler将四块陆地表示成四个结点，凡陆地间有桥相连的，便在两点间连一条边。;欧拉断言这样的回通路是不存在的。;8.1图的基本概念;无向图和有向图;有向图;图的术语;图的术语;图的术语;度的概念

;顶点的度数(续);握手定理;定理7.1.2;图的度数列;图的度数列;例题;实例;实例;图的分类;图的应用;完全图(1);完全图(2);定理;例题;例题（续）;正则图;正则图;环图和轮图;方体图;方体图;二分图;带权图;8.1.5子图与补图;例题;子图;例题;补图;补图;补图;例题;8.1.6图的同构;判断两个图同构的必要条件;判断两个图同构的必要条件;例题;例题;自互补图;8.2通路与回路、连通的概念;定义7.2.1给定图G=（V，E）中，以v0为起点，vn为终点的由结点和边交替出现的序列v0e1v1e2v2…vn-1envn称为从结点v0到vn的长度为n的通路。G是无向图时，其中的边ei的端点是vi-1和vi（i=1，2，?n）；G是有向图时，其中的有向边ei的起点是vi-1，终点是vi（i=1，2，?n）。

;通路与回路;例题;例题;说明;说明(续);定理;推论;定理;短程线与距离;通路的应用;8.2.2连通的概念;定理;点割集和边割集;说明;例题;有向图的连通性及其分类;有向连通图;实例;顶点集上的互相可达关系对于u，v?V，u与v有关系，当且仅当从u可达v，并且从v可达u。

顶点集上的互相可达关系是等价关系。

利用互相可达关系可将顶点集V划分为V1，V2，…,Vw,每个Vi的任两个顶点都是互相可达的.

所以每个Vi导出的子图Gi是强连通的,称为G的一个强分图.;有向图的强连通分支.;有向图的应用;资源分配图;8.3图的表示;定义列出图的每一个结点和它的所有邻接结点的表称为邻接表。

例1用邻接表表示无向简单图。

例2用邻接表表示有向简单图。

;8.3.2邻接矩阵;例题;有向图中的通路数与回路数;有向图中的通路数与回路数(续);实例(续);无向图的邻接矩阵;例题;例题;例题;8.3.3可达矩阵;例题;由可达矩阵求强连通分支;125;例题;定义设图G=(V,E)是无向图，V={v1,v2,…,vn},E={e1,e2,…,em}.

令mij为vi与ej的关联次数,称(mij)n?m为G的关联矩阵,记为

M(G).mij的可能取值为:0,1,2

;性质;例题;例题;例题;例题（续）;例题（续）;例题（续）;;图的运算;;8.4独立集、覆盖和支配集;例题;覆盖和覆盖集;例题;定理;例题;推论1;推论2;例题;支配和支配集;例题;定理;边独立集;边覆盖;例题;第9章特殊图;第9章特殊图;9.1欧拉图与哈密顿图;欧拉图;例题;欧拉图的判断;定理9.1.1证明;定理9.1.2证明;例题;欧拉有向图;欧拉有向图的判断;例题;9.1.2哈密顿图;哈密顿图;哈密顿图存在的必要条件;哈密顿图存在的必要条件;例题;哈密顿图存在的充分条件;定理9.1.6证明（续1）;定理9.1.6证明（续2）;定理9.1.6证明（续3）;哈密顿图的充分条件;例题;应用1;应用2-格雷码;格雷码;格雷码;9.2带权图;9.2.1旅行商问题;旅行商问题;9.2.2最短路径问题;Dijkstra算法;Dijkstra算法;Dijkstra算法;Dijkstra算法步骤;Dijkstra算法;9.2.3中国邮路问题;中国邮路问题;中国邮路问题;中国邮路问题;中国邮路问题;中国邮路问题;9.2.4关键路径;AOE网;关键活动;关键活动;例题;例题（续）;9.2.5网络与网络流;网络与网络流;网络流图;最大流;最小割;定理;定理;最大流的标号算法(Ford,Fulkerson);最大流的标号算法(Ford,Fulkerson);9.3匹配和二分图;例题;M交错