资源描述：
《离散数学 教学课件 作者 刘贵龙 第八章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第八章图的基本概念图是一类相当广泛的实际问题的数学模型，有着极其丰富的内容，是数据结构等课程的先修内容.学习时应掌握好图论的基本概念、基本方法、基本算法；善于把实际问题抽象为图论的问题，然后用图论的方法解决问题.返回首页8/7/20211第一节图的概念本节介绍图的一些最常用的概念,主要有:无向图,有向图,边,顶点(或结点,点),弧(或有向边),顶点集,边集,n阶图,有限图,关联,多重图,简单图,完全图,二分图(或偶图),完全二分图,母图,子图,支撑子图(或生成子图),导出子图,补图,图的同构,入度,出度,度,孤立点等.主要定理:握手定理.返回本章首页8/7
2、/20212第二节路与回路(1)本节介绍图中有关路的基本概念，同时作为路在权图中的应用，我们给出求权图最短路的迪克斯特拉算法.1.基本概念有:路,路的起点,路的终点,路的长度,开路,闭路,简单路,回路,基本路,圈,连通,连通分支,连通图,两点间的距离,可达,强连通图,单向连通图,弱连通图,权图,权,迪克斯特拉算法等；返回本章首页8/7/20213第二节路与回路(2)2.主要结论:设G=(V,E)是图，且
3、V
4、=n,若存在结点u到v的路，则必存在u到v的长度不超过n-1的路.3.算法:迪克斯特拉(Dijkstra)算法,迪克斯特拉算法是图论中最基本的算法,应
5、很好地掌握.返回本章首页8/7/20214第三节矩阵与图本节主要考虑三种矩阵，即邻接矩阵，可达矩阵与关联矩阵.邻接矩阵反映的是顶点与顶点之间的关系；可达矩阵反映了图的联通情况；关联矩阵反映的是顶点与边（弧）的关系.分有向图与无向图来讨论.返回本章首页8/7/20215第四节关系与图在讨论集合的二元关系时，我们就给出了关系的图形表示，即关系图.这里用图论的方法给出关系图的严格定义.关系中的很多性质可以在关系图上反映出来,可以通过图来研究关系,也可以通过关系来研究图.返回本章首页8/7/20216第五节欧拉图(1)欧拉图是一类非常著名的图，之所以如此，不仅是因
6、为欧拉是图论的创始人，更主要是欧拉图具有对边（弧）的“遍历性”.1.概念有:欧拉路,欧拉图,半欧拉路,半欧拉图,割边等；返回本章首页8/7/20217第五节欧拉图(2)2.结论有:(1)无向连通图G是欧拉图的充要条件是G中每个顶点的度均为偶数；(2)设G是无向连通图，则G是半欧拉图的充要条件是G恰含有两个奇数度点.3.算法:在欧拉图中找欧拉路的Fleury算法.返回本章首页8/7/20218第六节哈密尔顿图(1)哈密尔顿图是一类实际背景很强的图论模型,与欧拉图不同，哈密尔顿图感兴趣的是遍历图中的诸顶点.1.主要概念:哈密尔顿路,半哈密尔顿图,哈密尔顿回路,
7、哈密尔顿图,图的闭包；2.主要结论:哈密顿图的判定，至今也还没有令人满意地结果.下面的一些哈密顿图的结果都只是充分条件或必要条件，而非充要条件.返回本章首页8/7/20219第六节哈密尔顿图(2)(1)设G=(V,E)是哈密尔顿图，则对V的任意非空子集S均有W(G-S)≦
8、S
9、,其中G-S表示在G中删除S中的点以及以S为端点的边后所构成的图；W(G-S)表示G-S的连通分支数;(2)设G=(V,E)是n阶无向简单图，若对G中任意不相邻的顶点u,v都有d(u)+d(v)≧n-1,则G存在哈密尔顿路，因此G是半哈密尔顿图；(3)设G是n阶简单图，则是哈密尔顿图
10、当且仅当其闭包是哈密尔顿图.返回本章首页8/7/202110第七节二分图(1)二分图也是一类实际背景很强的图论模型,在§1已给出了二分图的定义,二分图与图的匹配有密切关系.1.基本概念:二分图,匹配,最大匹配,饱和,非饱和,完美匹配,交错路,可扩路,邻集等;2.结论:(1)设G是无向简单图,则G是二分图的充要条件是它的所有回路的长度为偶数;返回本章首页8/7/202111第七节二分图(2)(2)图G的匹配M是最大匹配当且仅当G不含M的可扩路;(3)设G=(V,E)为二分图,顶点划分为V=V1∪V2,则G存在饱和V1的每个顶点匹配的充要条件是对任何SV1均有
11、
12、N(S)
13、≧
14、S
15、；3.算法：匈牙利算法，解决了二分图的匹配问题。返回本章首页8/7/202112本章小结本章我们仅讨论无向图与有向图、我们首先给出图的一些基本概念和术语，比如，路、回路、连通性、邻接矩阵、关联矩阵等；给出了图论中的一些常用算法（如迪克斯特拉算法，Fleury算法等），在此基础上讨论了三类特殊的图，即欧拉图、哈密顿图、二分图等，此三类图均有很强的实际应用背景.返回本章首页8/7/202113
