离散数学第七章图论习题课件.pptxVIP

离 散 数 学河南工业大学信息科学与工程学院第7章 图 论习题课第一页，共四十八页。复 习 时 注 意准确掌握每个概念灵活应用所学定理注意解题思路清晰证明问题时，先用反向思维(从结论入手)分析问题，再按正向思维写出证明过程。第二页，共四十八页。图论的结构图 图 图的矩阵表示 通路与回路 欧拉图 图的连通性 汉密尔顿图 平面图的判断 平面图的基本性质 欧拉公式 平面图的对偶图 无向树及其性质 无向树及其性质 无向树及其性质 地图着色与平面图着色 根树及其应用第三页，共四十八页。第四页，共四十八页。一、无向图与有向图1、基本概念。有向图与无向图的定义；有向边,无向边,平行边,环, 孤立结点关联与邻接(相邻)；结点的度数；结点的度, 结点的出度, 结点的入度, 图的最大度Δ(G),最小度δ(G),零图与平凡图；简单图与多重图；完全图；子图，生成子图，补图；图的同构。2、运用。(1) 灵活运用握手定理及其推论，(2) 判断两个图是否同构，(3) 画出满足某些条件的子图，补图等。第五页，共四十八页。二、通路、回路、图的连通性1、基本概念路，回路，迹， 通路，圈无向图和有向图中结点之间的可达关系；连通图，连通分支，连通分支数W(G)点割集，割点，点连通度k(G)边割集，割边(桥)，边连通度λ(G)短程线，距离有向图连通的分类，强连通，单侧连通，弱连通， 强分图，单侧分图，弱分图 2、运用(1) 判断有向图或无向图中通路(回路)的类型。(2) 求短程线和距离。(3) 判断有向图连通的类型。第六页，共四十八页。三、图的矩阵表示1、基本概念。无向图的邻接矩阵A根据邻接矩阵判断:各结点的度, 有向图结点出,入度。由Ak可以求一个结点到另一个结点长度为k的路条数.有向图的可达矩阵P用P可以判定:各结点的度. 有向图的强分图。关联矩阵M:是结点与边的关联关系矩阵. 用M判定:各结点的度第七页，共四十八页。重要定理：握手定理及其推论无向图：有向图：且推论 ： 任何图(无向的或有向的)中，奇度结点的个数是偶数。第八页，共四十八页。(1)(2)(3)典型题设图G=V,E，其中V={a,b,c,d,e}，E分别由下面给出。判断哪些是简单图，哪些是多重图？简单图多重图不是第九页，共四十八页。下列各序列中，可以构成无向简单图的度数序列的有哪些？(1) (2,2,2,2,2) 可以(2)(1,1,2,2,3) 不可以(3)(1,1,2,2,2) 可以(4)(0,1,3,3,3) 不可以(5)(1,3,4,4,5) 不可以第十页，共四十八页。图G如右图所示，以下说法正确的是 ( ) ．A．{(a, d)}是割边B．{(a, d)}是边割集C．{(d, e)}是边割集D．{(a, d) ,(a, c)}是边割集正确答案是：C。对割边、边割集的概念理解到位。定义 设无向图G=V, E为连通图，若有边集E1?E，使图G删除了E1的所有边后，所得的子图是不连通图，而删除了E1的任何真子集后，所得的子图是连通图，则称E1是G的一个边割集．若某个边构成一个边割集，则称该边为割边（或桥）如果答案A正确，即删除边(a, d)后，得到的图是不连通图，但事实上它还是连通的。因此答案A是错误的。第十一页，共四十八页。设给定图G(如由图所示)，则图G的点割集是 ．应该填写：{f}，{c，e}。定义 设无向图G=V, E为连通图，若有点集V1?V，使图G删除了V1的所有结点后，所得的子图是不连通图，而删除了V1的任何真子集后，所得的子图是连通图，则称V1是G的一个点割集．若某个结点构成一个点割集，则称该结点为割点。{f，c}是不满定义的，因为{f}是{f，c}的真子集，而删除{f}后，图是不连通的。第十二页，共四十八页。下图所示的六个图中，强连通，单向连通，弱连通的分别有哪些？弱连通强连通单向连通单向连通强连通强连通第十三页，共四十八页。设图G的邻接矩阵为则G的边数为( )．A．5 B．6 C．3 D．4正确答案是：D。当给定的简单图是无向图时，邻接矩阵为对称的．即当结点vi与vj相邻时，结点vj与vi也相邻，所以连接结点vi与vj的一条边在邻接矩阵的第i行第j列处和第j行第i列处各有一个1，题中给出的邻接矩阵中共有8个1，故有8?2=4条边。度数之和等于2倍的边数。第十四页，共四十八页。有向图D如图所示，回答下列问题：(1) D是哪类连通图?(2) D中v1到v4长度为1,2,3,4的通路各多少条？(3) D中长