离散数学第十四章图论基本概念.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《离散数学第十四章图论基本概念.ppt》由会员分享,可在线阅读,更多相关《离散数学第十四章图论基本概念.ppt(51页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第五部分第五部分 图论图论本部分主要内容本部分主要内容l 图的基本概念图的基本概念l 欧拉图、哈密顿图欧拉图、哈密顿图l 树树l 平面图平面图l 支配集、覆盖集、独立集、匹配与着色支配集、覆盖集、独立集、匹配与着色1第十四章第十四章 图的基本概念图的基本概念主要内容主要内容l图图l通路与回路通路与回路l图的连通性图的连通性l图的矩阵表示图的矩阵表示l图的运算图的运算预备知识预备知识l多重集合多重集合元素可以重复出现的集合元素可以重复出现的集合l无序集无序集A B=(x,y)|x A y B214.1 图图定义定义 无向图无向图G=,其中其中(1)V 为顶点集,元素称为为顶点集,元素称为顶点顶点
2、(2)E为为V V 的多重集,其元素称为无向边,简称的多重集,其元素称为无向边,简称边边实例实例 设设 V=v1,v2,v5,E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)则则 G=为一无向图为一无向图3有向图有向图定义定义 有向图有向图D=,只需注意只需注意E是是V V 的多重子集的多重子集图图2表示的是一个有向图,试写出它的表示的是一个有向图,试写出它的V 和和 E 注意:图的数学定义与图形表示,在同构(待叙)的意义下注意:图的数学定义与图形表示,在同构(待叙)的意义下是一一对应的是一一对应的4相关概念相关概念1.图图 可
3、用可用G泛指图(无向的或有向的)泛指图(无向的或有向的)V(G),E(G),V(D),E(D)n阶图阶图2.有限图有限图3.n 阶零图与平凡图阶零图与平凡图4.空图空图5.用用 ek 表示无向边或有向边表示无向边或有向边6.顶点与边的关联关系顶点与边的关联关系 关联、关联次数关联、关联次数 环环 孤立点孤立点7.顶点之间的相邻与邻接关系顶点之间的相邻与邻接关系58.邻域与关联集邻域与关联集 v V(G)(G为无向图为无向图)v 的关联集的关联集 v V(D)(D为有向图为有向图)9.标定图与非标定图标定图与非标定图10.基图基图相关概念相关概念6多重图与简单图多重图与简单图定义定义14.3 (
4、1)无向图中的平行边及重数无向图中的平行边及重数(2)有向图中的平行边及重数(注意方向性)有向图中的平行边及重数(注意方向性)(3)多重图多重图(4)简单图简单图在定义中定义的简单图是极其重要的概念在定义中定义的简单图是极其重要的概念 7顶点的度数顶点的度数定义定义 (1)设设G=为无向图为无向图,v V,d(v)v的度数的度数,简称度简称度 (2)设设D=为有向图为有向图,v V,d+(v)v的出度的出度 d(v)v的入度的入度 d(v)v的度或度数的度或度数 (3)(G),(G)(4)+(D),+(D),(D),(D),(D),(D)(5)奇顶点度与偶度顶点奇顶点度与偶度顶点8定理定理 设
5、设G=为任意无向图,为任意无向图,V=v1,v2,vn,|E|=m,则则证证 G中每条中每条边边(包括包括环环)均有两个端点,所以在均有两个端点,所以在计计算算G中各中各顶顶点点度数之和度数之和时时,每条,每条边边均提供均提供2度,度,m 条条边边共提供共提供 2m 度度.本定理的证明类似于定理本定理的证明类似于定理握手定理握手定理定理定理 设设D=为任意有向图,为任意有向图,V=v1,v2,vn,|E|=m,则则9握手定理推论握手定理推论推论推论 任何图任何图(无向或有向无向或有向)中,奇度顶点的个数是偶数中,奇度顶点的个数是偶数.证证 设设G=为任意图,令为任意图,令 V1=v|v V d
6、(v)为奇数为奇数 V2=v|v V d(v)为偶数为偶数 则则V1 V2=V,V1 V2=,由握手定理可知,由握手定理可知由于由于2m,均为偶数,所以均为偶数,所以 为偶数,但因为为偶数,但因为V1中中顶点度数为奇数,所以顶点度数为奇数,所以|V1|必为偶数必为偶数.10例例1 无向图无向图G有有16条边,条边,3个个4度顶点,度顶点,4个个3度顶点,其余度顶点,其余顶点度数均小于顶点度数均小于3,问,问G的阶数的阶数n为几?为几?解解 本题的关键是应用握手定理本题的关键是应用握手定理.设除设除3度与度与4度顶点外,还有度顶点外,还有x个顶点个顶点v1,v2,vx,则则 d(vi)2,i=1
7、,2,x,于是得不等式于是得不等式 32 24+2x得得 x 4,阶数阶数 n 4+4+3=11.握手定理应用握手定理应用11图的度数列图的度数列1.V=v1,v2,vn为无向图为无向图G的顶点集,称的顶点集,称d(v1),d(v2),d(vn)为为G的的度数列度数列 2.V=v1,v2,vn为有向图为有向图D的顶点集,的顶点集,D的的度数列度数列:d(v1),d(v2),d(vn)D的的出度列出度列:d+(v1),d+(v2),d+(vn)D的的入度列入度列:d(v1),d(v2),d(vn)3.非负整数列非负整数列d=(d1,d2,dn)是是可图化的可图化的,是,是可简单图化可简单图化的的
8、.易知:易知:(2,4,6,8,10),(1,3,3,3,4)是可图化的,后者又是是可图化的,后者又是可可简单图化的,而简单图化的,而(2,2,3,4,5),(3,3,3,4)都不是可简单图都不是可简单图化化的,特别是后者也不是可图化的的,特别是后者也不是可图化的12图的同构图的同构定义定义 设设G1=,G2=为两个无向图为两个无向图(两个有向两个有向图图),若存在双射函数,若存在双射函数f:V1V2,对于对于vi,vj V1,(vi,vj)E1 当且仅当当且仅当(f(vi),f(vj)E2 (E1 当且仅当当且仅当 E2)并且并且,(vi,vj)()与)与(f(vi),f(vj)()的)的重
9、数相重数相同,则称同,则称G1与与G2是是同构同构的,记作的,记作G1 G2.l图之间的同构关系具有自反性、对称性和传递性图之间的同构关系具有自反性、对称性和传递性.l能找到多条同构的必要条件,但它们全不是充分条件:能找到多条同构的必要条件,但它们全不是充分条件:边数相同,顶点数相同边数相同,顶点数相同;度数列相同度数列相同;对应顶点的关联集及邻域的元素个数相同,等等对应顶点的关联集及邻域的元素个数相同,等等 若破坏必要条件,则两图不同构若破坏必要条件,则两图不同构l判断两个图同构是个难题判断两个图同构是个难题13图同构的实例图同构的实例图中图中(1)与与(2)的度数列相同,它们同构吗?为什么
10、?的度数列相同,它们同构吗?为什么?(1)(2)(3)(4)图中,图中,(1)与与(2)不同构(度数列不同),不同构(度数列不同),(3)与与(4)也不同构也不同构.(1)(2)14n 阶完全图与竞赛图阶完全图与竞赛图定义定义14.6(1)n(n 1)阶无向完全图阶无向完全图每个顶点与其余顶点均相邻每个顶点与其余顶点均相邻的无向简单图,记作的无向简单图,记作 Kn.简单性质:边数简单性质:边数(2)n(n 1)阶阶有向完全图有向完全图每对顶点之间均有两条方向相每对顶点之间均有两条方向相反的有向边的有向简单图反的有向边的有向简单图.简单性质:简单性质:(3)n(n 1)阶阶竞赛图竞赛图基图为基图
11、为Kn的有向简单图的有向简单图.简单性质:边数简单性质:边数 15n 阶阶 k 正则图正则图(1)为为K5,(2)为为3阶有向完全图,阶有向完全图,(3)为为4阶竞赛图阶竞赛图.(1)(2)(3)定义定义 n 阶阶k正则图正则图=k 的无向简单图的无向简单图简单性质:边数(由握手定理得)简单性质:边数(由握手定理得)Kn是是 n 1正则图,正则图,彼得松图(见书上图彼得松图(见书上图14.3(1)所示,记住它)所示,记住它)16子图子图定义定义 G=,G=(1)GG G 为为G的的子图子图,G为为G 的的母图母图(2)若若GG且且V=V,则称,则称G 为为G的的生成子图生成子图(3)若若VV或
12、或EE,称,称G 为为G的的真子图真子图(4)V(VV且且V)的)的导出子图导出子图,记作,记作GV(5)E(EE且且E)的)的导出子图导出子图,记作,记作GE 17例例2 画出画出K4的所有非同构的生成子图的所有非同构的生成子图实例实例18补图补图定义定义 设设G=为为n阶无向简单图,以阶无向简单图,以V为顶点集,以所有为顶点集,以所有使使G成为完全图成为完全图Kn的添加边组成的集合为边集的图,称为的添加边组成的集合为边集的图,称为G的的补图补图,记作,记作 .若若G ,则称则称G是是自补图自补图.相对于相对于K4,求上面图中所有图的补图,并指出哪些是自补求上面图中所有图的补图,并指出哪些是
13、自补图图.问:互为自补图的两个图的边数有何关系?问:互为自补图的两个图的边数有何关系?1914.2 通路与回路通路与回路定义定义 给定图给定图G=(无向或有向的),(无向或有向的),G中中顶点与顶点与边的交替序列边的交替序列 =v0e1v1e2elvl,vi 1,vi 是是 ei 的端点的端点.(1)通路与回路:通路与回路:为为通路通路;若;若 v0=vl,为为回路回路,l 为为回路长回路长 度度.(2)简单通路与回路:所有边各异,简单通路与回路:所有边各异,为为简单通路简单通路,又若,又若v0=vl,为为简单回路简单回路(3)初级通路初级通路(路径路径)与初级回路与初级回路(圈圈):中所有顶
14、点各异,中所有顶点各异,则称则称 为为初级通路初级通路(路径路径),又若除,又若除v0=vl,所有的顶点各不,所有的顶点各不相同且所有的边各异,则称相同且所有的边各异,则称 为为初级回路初级回路(圈圈)(4)复杂通路与回路:有边重复出现复杂通路与回路:有边重复出现20几点说明几点说明表示法表示法 定义表示法定义表示法 只用边表示法只用边表示法 只用顶点表示法(在简单图中)只用顶点表示法(在简单图中)混合表示法混合表示法环环(长为(长为1的圈)的长度为的圈)的长度为1,两条平行边构成的圈长度为,两条平行边构成的圈长度为 2,无向简单图中,圈长,无向简单图中,圈长 3,有向简单图中圈的长度,有向简
15、单图中圈的长度 2.不同的圈(以长度不同的圈(以长度 3的为例)的为例)定义意义下定义意义下 无向图:图中长度为无向图:图中长度为l(l 3)的圈,定义意义下为)的圈,定义意义下为2l个个 有向图:图中长度为有向图:图中长度为l(l 3)的圈,定义意义下为)的圈,定义意义下为l个个 同构意义下:长度相同的圈均为同构意义下:长度相同的圈均为1个个试讨论试讨论l=3和和l=4的情况的情况21通路与回路的长度通路与回路的长度定理定理 在在n 阶图阶图G中,若从顶点中,若从顶点vi 到到vj(vi vj)存在通路,)存在通路,则从则从vi 到到 vj 存在长度小于或等于存在长度小于或等于n 1 的通路
16、的通路.推论推论 在在 n 阶图阶图G中,若从顶点中,若从顶点vi 到到 vj(vi vj)存在通路,则)存在通路,则从从vi 到到vj 存在长度小于或等于存在长度小于或等于n 1的初级通路(路径)的初级通路(路径).定理定理 在一个在一个n 阶图阶图G中,若存在中,若存在 vi 到自身的回路,则一到自身的回路,则一定存在定存在vi 到自身长度小于或等于到自身长度小于或等于 n 的回路的回路.推论推论 在一个在一个n 阶图阶图G中,若存在中,若存在 vi 到自身的简单回路,则一到自身的简单回路,则一定存在长度小于或等于定存在长度小于或等于n 的初级回路的初级回路.22 图的连通性图的连通性无向
17、图的连通性无向图的连通性(1)顶点之间的连通关系:顶点之间的连通关系:G=为无向图为无向图 若若 vi 与与 vj 之间有通路,则之间有通路,则 vi vj 是是V上的等价关系上的等价关系 R=|u,v V且且u v(2)G的连通性与连通分支的连通性与连通分支 若若 u,v V,u v,则称,则称G连通连通 V/R=V1,V2,Vk,称,称GV1,GV2,GVk为为连通连通分分 支支,其个数,其个数 p(G)=k (k 1);k=1,G连通连通23短程线与距离短程线与距离(3)短程线与距离短程线与距离 u与与v之间的之间的短程线短程线:u v,u与与v之间长度最短的通路之间长度最短的通路 u与
18、与v之间的之间的距离距离:d(u,v)短程线的长度短程线的长度 d(u,v)的性质:的性质:d(u,v)0,u v时时d(u,v)=d(u,v)=d(v,u)d(u,v)+d(v,w)d(u,w)24无向图的连通度无向图的连通度1.删除顶点及删除边删除顶点及删除边 G v 从从G中将中将v及关联的边去掉及关联的边去掉 G V 从从G中删除中删除V 中所有的顶点中所有的顶点 G e 将将e从从G中去掉中去掉 G E 删除删除E 中所有边中所有边 2.点割集与边割集点割集与边割集 点割集与割点点割集与割点定义定义 G=,VV V 为为点割集点割集p(G V)p(G)且有极小性且有极小性 v为为割点
19、割点v为点割集为点割集定义定义 G=,EE E 是是边割集边割集p(G E)p(G)且有极小性且有极小性 e是是割边割边(桥)(桥)e为边割集为边割集25点割集与割点点割集与割点例例3 v1,v4,v6是点是点割集,割集,v6是割点是割点.v2,v5是点割集吗?是点割集吗?e1,e2,e1,e3,e5,e6,e8等是边割集,等是边割集,e8是是桥,桥,e7,e9,e5,e6 是边是边割割集吗?集吗?几点说明:几点说明:lKn中无点割集,中无点割集,Nn中既无点割集,也无边割集,其中中既无点割集,也无边割集,其中Nn为为 n 阶零图阶零图.l若若G 连通,连通,E 为边割集,则为边割集,则 p(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 第十四 章图论 基本概念
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内