《离散数学第14章》由会员分享，可在线阅读，更多相关《离散数学第14章（43页珍藏版）》请在金锄头文库上搜索。
1、.,1,第五部分 图论,本部分主要内容 图的基本概念 欧拉图、哈密顿图 树,.,2,第十四章 图的基本概念,主要内容 图 通路与回路 图的连通性 图的矩阵表示 图的运算 预备知识 多重集合元素可以重复出现的集合 无序积AB=x,y | xAyB,.,3,14.1 图,定义14.1 无向图G = , 其中 (1) V 为顶点集，元素称为顶点 (2) E为VV 的多重集，其元素称为无向边，简称边 实例 设 V = v1, v2, ,v5, E = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 则 G = 为一无向图,.,
2、4,有向图,定义14.2 有向图D=, 只需注意E是VV 的多重子集 图2表示的是一个有向图，试写出它的V 和 E 注意：图的数学定义与图形表示。,.,5,相关概念,1. 图 可用G泛指图（无向的或有向的） V(G), E(G), V(D), E(D) n阶图 2. 有限图 3. n 阶零图与平凡图 4. 空图 5. 用 ek 表示无向边或有向边 6. 顶点与边的关联关系 关联、关联次数 环 孤立点 7. 顶点之间的相邻关系,.,6,8. 邻域与关联集 vV(G) (G为无向图),v 的关联集, vV(D) (D为有向图),9. 标定图与非标定图 10. 基图,相关概念,.,7,多重图与简单图
3、,定义14.3 (1) 无向图中的平行边及重数 (2) 有向图中的平行边及重数（注意方向性） (3) 多重图 (4) 简单图 在定义14.3中定义的简单图是极其重要的概念,.,8,顶点的度数,定义14.4 (1) 设G=为无向图, vV, d(v)v的度数, 简称度 (2) 设D=为有向图, vV, d+(v)v的入度 d(v)v的出度 d(v)v的度或度数 (3) (G), (G) (4) +(D), +(D), (D), (D), (D), (D) (5) 奇顶点度与偶度顶点,.,9,定理14.1 设G=为任意无向图，V=v1,v2,vn, |E|=m, 则,证 G中每条边 (包括环) 均
4、有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m 条边共提供 2m 度.,本定理的证明类似于定理14.1,握手定理,定理14.2 设D=为任意有向图，V=v1,v2,vn, |E|=m, 则,.,10,握手定理推论,推论 任何图 (无向或有向) 中，奇度顶点的个数是偶数. 证 设G=为任意图，令 V1=v | vV d(v)为奇数 V2=v | vV d(v)为偶数 则V1V2=V, V1V2=，由握手定理可知 由于2m, 均为偶数，所以 为偶数，但因为V1中 顶点度数为奇数，所以|V1|必为偶数.,.,11,例1 无向图G有16条边，3个4度顶点，4个3度顶点，其余顶点度数均
5、小于3，问G的阶数n为几？,解 本题的关键是应用握手定理. 设除3度与4度顶点外，还有x个顶点v1, v2, , vx， 则 d(vi) 2，i =1, 2, , x， 于是得不等式 32 24+2x 得 x 4, 阶数 n 4+4+3=11.,握手定理应用,.,12,图的度数列,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(
6、v2), , d(vn) 3. 非负整数列d=(d1, d2, , dn)在什么条件下是可图化的，是可简单图化的？ 定理14.4 p277 易知：(2, 4, 6, 8, 10)，(1, 3, 3, 3, 4) 是可图化的，后者又是可 简单图化的，而(2, 2, 3, 4, 5)，(3, 3, 3, 4) 都不是可简单图化 的，特别是后者也不是可图化的,.,13,n 阶完全图与竞赛图,定义14.6 (1) n (n1) 阶无向完全图每个顶点与其余顶点均相邻的无向简单图，记作 Kn. 简单性质：边数 (2) n (n1)阶有向完全图每对顶点之间均有两条方向相反的有向边的有向简单图. 简单性质：
7、(3) n (n1) 阶竞赛图基图为Kn的有向简单图. 简单性质：边数,.,14,n 阶 k 正则图,(1)为K5，(2)为3阶有向完全图，(3)为4阶竞赛图.,(1) (2) (3),定义14.7 n 阶k正则图=k 的无向简单图 简单性质：边数（由握手定理得） n阶完全图Kn是 n1正则图，,.,15,子图,定义14.8 G=, G= (1) GG G为G的子图，G为G的母图 (2) 若GG且V=V，则称G为G的生成子图 (3) 若VV或EE，称G为G的真子图 (4) V（VV且V）的导出子图，记作GV (5) E（EE且E）的导出子图，记作GE,.,16,例2 画出K4的所有非同构的生成
8、子图,实例,.,17,补图,定义14.9 设G=为n阶无向简单图，以V为顶点集，以所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作 . 若G , 则称G是自补图. 例：见书P280 图14.6,.,18,14.2 通路与回路,定义14.11 给定图G=（无向或有向的），G中顶点与 边的交替序列 = v0e1v1e2elvl，vi1, vi 是 ei 的端点. (1) 通路与回路： 为通路；若 v0=vl， 为回路，l 为回路长 度. (2) 简单通路与回路：所有边各异， 为简单通路，又若v0=vl， 为简单回路 (3) 初级通路(路径)与初级回路(圈)： 中所有顶点各异，
9、则称 为初级通路(路径)，又若除v0=vl，所有的顶点各不相同且所有的边各异，则称 为初级回路(圈) (4) 复杂通路与回路：有边重复出现,.,19,几点说明,表示法 定义表示法 只用边表示法 只用顶点表示法（在简单图中） 混合表示法 环（长为1的圈）的长度为1，两条平行边构成的圈长度为 2，无向简单图中，圈长3，有向简单图中圈的长度2. 不同的圈（以长度3的为例）,.,20,通路与回路的长度,定理14.5 在n 阶图G中，若从顶点vi 到vj（vivj）存在通路， 则从vi 到 vj 存在长度小于或等于n1 的通路. 推论 在 n 阶图G中，若从顶点vi 到 vj（vivj）存在通路，则 从
10、vi 到vj 存在长度小于或等于n1的初级通路（路径）. 定理14.6 在一个n 阶图G中，若存在 vi 到自身的回路，则一 定存在vi 到自身长度小于或等于 n 的回路. 推论 在一个n 阶图G中，若存在 vi 到自身的简单回路，则一 定存在长度小于或等于n 的初级回路.,.,21,14.3 图的连通性,无向图的连通性 (1) 顶点之间的连通关系：G=为无向图 若 vi 与 vj 之间有通路，则 vivj 是V上的等价关系 R=| u,v V且uv (2) G的连通性与连通分支 若u,vV，uv，则称G连通 V1,V2,Vk，称GV1, GV2, ,GVk为连通分 支，其个数 p(G)=k
11、(k1)； k=1，G连通,.,22,短程线与距离,(3) 短程线与距离 u与v之间的短程线：uv，u与v之间长度最短的通路 u与v之间的距离：d(u,v)短程线的长度 d(u,v)的性质： d(u,v)0, uv时d(u,v)= d(u,v)=d(v,u) d(u,v)+d(v,w)d(u,w),.,23,无向图的连通度,1. 删除顶点及删除边 Gv 从G中将v及关联的边去掉 GV从G中删除V中所有的顶点 Ge 将e从G中去掉 GE删除E中所有边 2. 点割集与边割集 点割集与割点 书p283 定义14.15 G=, VV V为点割集p(GV)p(G)且有极小性 v为割点v为点割集 定义14
12、.16 G=, EE E是边割集p(GE)p(G)且有极小性 e是割边（桥）e为边割集,.,24,点割集与割点,例3 v1,v4，v6是点 割集，v6是割点. v2,v5 是点割集吗？ e1,e2，e1,e3,e5,e6， e8等是边割集，e8是 桥，e7,e9,e5,e6 是边割 集吗？,几点说明： Kn中无点割集，Nn中既无点割集，也无边割集，其中Nn为 n 阶零图. 若G 连通，E为边割集，则 p(GE)=2，V为点割集，则 p(GV)2,.,25,点连通度与边连通度,定义14.18 G为连通非完全图 点连通度 (G) = min |V |V 为点割集 规定 (Kn) = n1 若G非连
13、通，(G) = 0 若 (G)k，则称G为 k-连通图 定义14.19 设G为连通图 边连通度(G) = min|E|E为边割集 若G非连通，则(G) = 0 若(G)r，则称G是 r 边-连通图 图中， =1，它是 1-连通图 和 1边-连通图,.,26,有向图的连通性,定义14.20 D=为有向图 vi vj（vi 可达 vj）vi 到vj 有通路 vi vj（vi 与vj 相互可达） 性质 具有自反性(vi vi)、传递性 具有自反性、对称性、传递性 vi 到vj 的短程线与距离 类似于无向图中，只需注意距离表示法的不同 (无向图中d(vi,vj)，有向图中d) 及 d无对称性,.,27
14、,有向图的连通性及分类,定义14.22 D=为有向图 D弱连通(连通)基图为无向连通图 D单向连通vi,vjV，vivj 或 vjvi D强连通vi,vjV，vivj 易知，强连通单向连通弱连通 判别法 定理14.8 D强连通当且仅当D中存在经过每个顶点至少一次 的回路 定理14.9 D单向连通当且仅当D中存在经过每个顶点至少一 次的通路,.,28,二部图,定义14.23 设 G=为一个无向图，若能将 V分成 V1和V2 (V1V2=V，V1V2=)，使得 G 中的每条边的两个端点都是 一个属于V1，另一个属于V2，则称 G 为二部图 ( 或称二分 图、偶图等 )，称V1和V2为互补顶点子集，
15、常将二部图G 记为. 又若G是简单二部图，V1中每个顶点均与V2中所有的顶点相 邻，则称G为完全二部图，记为 Kr,s，其中r=|V1|，s=|V2|. 注意，n 阶零图为二部图.,.,29,14.4 图的矩阵表示,无向图的关联矩阵（对图无限制） P288 定义14.24 无向图G=，|V|=n，|E|=m，令 mij为 vi 与 ej 的关联次数，称(mij)nm为G 的关联矩阵，记为M(G). 性质,.,30,有向图的关联矩阵（无环有向图）P288,定义14.25 有向图D=，令 则称 (mij)nm为D的关联矩阵，记为M(D).,(4) 平行边对应的列相同,性质,有向图的关联矩阵,.,3
16、1,有向图的邻接矩阵（无限制）,定义14.26 设有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令为顶点 vi 邻接到顶点 vj 边的条数，称为D的邻接矩 阵，记作A(D)，或简记为A. 性质,.,32,推论 设Bl=A+A2+Al（l1），则 Bl中元素,为D中长度为 l 的通路总数，,定理14.11 设 A为有向图 D 的邻接矩阵，V=v1, v2, , vn为顶点集，则 A 的 l 次幂 Al（l1）中元素,为D中vi 到vj长度为 l 的通路数，其中,为vi到自身长度为 l 的回路数，而,为D中长度小于或等于 l 的回路数,为D中长度小于或等于 l 的通路数.,邻接矩阵的应用,为D 中长度为 l 的回路总数.,.,33,例5 有向图D如图所示，求 A, A2, A3, A4，并回答诸问题： (1) D
