《离散数学及其应用 本科 何中胜04 图论》由会员分享，可在线阅读，更多相关《离散数学及其应用 本科 何中胜04 图论（133页珍藏版）》请在金锄头文库上搜索。
1、1,第4篇 图论,第四篇 图论,图论是一门很有实用价值的学科，它在自然科学、社会科学等各领域均有很多应用。自上世纪中叶以来，它受计算机科学蓬勃发展的刺激，发展极其迅速，应用范围不断拓广，已渗透到诸如语言学、逻辑学、物理学、化学、电讯工程、计算机科学以及数学的其它分支中。特别在计算机科学中，如形式语言、数据结构、分布式系统、操作系统等方面均扮演着重要的角色。,A,C,B,D,A,B,C,D,哥尼斯堡七桥问题,本篇学习要求,第7章 图,7.1 图的基本概念 7.2 图的连通性 7.3 图的矩阵表示 7.4 几种特殊的图 7.5 树及其应用,7.1 图的基本概念,7.1.1 无向图与有向图 7.1.
2、2 顶点的度数与握手定理 7.1.3 简单图、完全图、正则图、圈图、 轮图、方体图 7.1.4 子图、补图 7.1.5 图的同构,无序对与多重集合,无序对: 2个元素构成的集合, 记作(a,b) 无序积: AB=(x,y) | xAyB 例如 A=a,b,c, B=1,2 AB=BA=(a,1), (b,1), (c,1), (a,2), (b,2), (c,2) AA=(a,a), (a,b), (a,c), (b,b), (b,c), (c,c) BB=(1,1), (1,2), (2,2) 多重集合: 元素可以重复出现的集合 重复度: 元素在多重集合中出现的次数 例如 S=a,b,b,c
3、,c,c, a,b,c 的重复度依次为1,2,3,无向图,定义7.1 无向图G=, 其中V称为顶点集, 其元素称为顶点或结点; E是VV的多重子集, 称为边集, 其元素称为无向边，简称边. 有时用V(G)和E(G)分别表示V和E 例如, G=如图所示, 其中V=v1, v2, ,v5 E=(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5),有向图,定义7.2 有向图D=, 其中V称为顶点集, 其元素称为顶点或结点; E是VV的多重子集, 称为边集, 其元素称为有向边，简称边. 有时用V(D)和E(D)分别表示V和E 有限图
4、: V, E都是有穷集合的图 n 阶图: n个顶点的图 零图: E=的图 平凡图: 1 阶零图,顶点和边的关联与相邻,设无向图G=, ek=(vi, vj)E, 称vi, vj为ek的端点, ek与vi ( vj)关联. 若vi = vj, 则称ek为环. 无边关联的顶点称作孤立点. 若vi vj, 则称ek与vi ( vj)的关联次数为1; 若vi = vj, 则称ek与vi 的关联次数为2; 若vi不是边e的端点, 则称e与vi 的关联 次数为0. 设vi,vjV, ek,elE, 若(vi,vj)E, 则称vi,vj相邻; 若ek,el有一个公共端点, 则称ek,el相邻. 对有向图有类
5、似定义. 设ek=vi,vj是有向图的一条边, 又称vi是ek的始点, vj是ek的终点, vi邻接到vj, vj邻接于vi,顶点的度数,设G=为无向图, vV, v的度数(度) d(v): v作为边的端点次数之和 悬挂顶点: 度数为1的顶点 悬挂边: 与悬挂顶点关联的边 G的最大度(G)=maxd(v)| vV G的最小度(G)=mind(v)| vV 例如 d(v5)=3, d(v2)=4, d(v1)=4, (G)=4, (G)=1, v4是悬挂顶点, e7是悬挂边, e1是环,顶点的度数(续),设D=为有向图, vV, v的出度d+(v): v作为边的始点次数之和 v的入度d(v):
6、v作为边的终点次数之和 v的度数(度) d(v): v作为边的端点次数之和 d(v)= d+(v)+ d-(v) +(D), +(D), (D), (D), (D), (D) 悬挂顶点, 悬挂边 例如 d+(a)=4, d-(a)=1, d(a)=5, d+(b)=0, d-(b)=3, d(b)=3, +=4, +=0, =3, =1, =5, =3,握手定理,定理7.1 任何图(无向图和有向图)的所有顶点度数之和都等于边数的2倍. 证 图中每条边(包括环)均有两个端点, 所以在计算各顶点度数之和时, 每条边均提供2度, m条边共提供2m度. 推论 任何图(无向图和有向图)都有偶数个奇度顶点
7、 定理7.2 有向图所有顶点的入度之和等于出度之和等于边数 证 每条边恰好提供1个入度和1个出度,图的度数列,设无向图G的顶点集V=v1, v2, , vn G的度数列: d(v1), d(v2), , d(vn) 如右图度数列:4,4,2,1,3 设有向图D的顶点集V=v1, v2, , vn D的度数列: d(v1), d(v2), , d(vn) D的出度列: d+(v1), d+(v2), , d+(vn) D的入度列: d(v1), d(v2), , d(vn) 如右图度数列:5,3,3,3 出度列:4,0,2,1 入度列:1,3,1,2,实例,(2) 能,例1 下述2组数能成为无向
8、图的度数列吗? (1) 3,3,3,4; (2) 1,2,2,3,解 (1) 不可能. 有奇数个奇数.,实例,例2 已知图G有10条边, 4个3度顶点, 其余顶点的度数均小于等于2, 问G至少有多少个顶点?,解 设G有n个顶点. 由握手定理, 43+2(n-4)210 解得 n8,例3 已知5阶有向图的度数列和出度列分别为3,3,2,3,3和1,2,1,2,1, 求它的入度列,解 2,1,1,1,2,实例,例4 证明不存在具有奇数个面且每个面都具有奇数条棱的多面体.,证 用反证法. 假设存在这样的多面体, 作无向图G=,其中 V=v | v为多面体的面, E=(u,v) | u,vV u与v有
9、公共的棱 uv. 根据假设, |V|为奇数且vV, d(v)为奇数. 这与握手定理的推论矛盾.,实例,例5 设9阶无向图的每个顶点的度数为5或6, 证明它至少有5个6度顶点或者至少有6个5度顶点.,证 讨论所有可能的情况. 设有a个5度顶点和b个6度顶点,(1)a=0, b=9; (2)a=2, b=7; (3)a=4, b=5; (4)a=6, b=3; (5)a=8, b=1 (1)(3) 至少5个6度顶点, (4)和(5) 至少6个5度顶点,方法二 假设b9-5=4. 由握手定理的推论, a 6,简单图,定义7.4 在无向图中, 关联同一对顶点的2条或2条以上的边, 称为平行边, 平行边
10、的条数称为重数 在有向图中, 具有相同始点和终点的2条或2条以上的边称为有向平行边, 简称平行边, 平行边的条数称为重数 含平行边的图称为多重图 既无平行边也无环的图称为简单图,实例,e5和e6 是平行边 重数为2 不是简单图,e2和e3 是平行边,重数为2 e6和e7 不是平行边 不是简单图,完全图与正则图,无向完全图: 每对顶点之间都有一条边的无向简单图.n阶无向完全图记作Kn, 顶点数n, 边数m=n(n-1)/2, =n-1 有向完全图: 每对顶点之间均有两条方向相反的边的有向简单图. 顶点数n, 边数m=n(n-1), +=+=-=-=n-1, =2(n-1) k-正则图: 每个顶点
11、的度数均为k的无向简单图 顶点数n, 边数m=kn/2,实例,K3,K5,3阶有向完全图,2正则图,4正则图,3正则图 彼得松图,圈图与轮图,无向圈图Cn=, 其中V=v1,v2,vn, E=(v1,v2),(v2,v3),(vn-1,vn),(vn,v1), n 3 有向圈图Cn=, 其中V=v1,v2,vn, E=, n 3 轮图Wn:无向圈图Cn-1内放一个顶点, 且与圈图的每个顶点之间恰有一条边, n 4,方体图,n方体图Qn=是2n阶无向简单图, 其中 V=v|v=a1a2an, ai=0,1, i=1,2,n E=(u,v)| u,vVu与v恰好有一位数字不同.,子图,定义7.10
12、 设G=, G=是2个图(同为无向图,或同为有向图) 若VV且EE, 则称G为G的子图, G为G的母图, 记作GG 若GG 且V=V, 则称G为G的生成子图 若VV或EE, 称G为G的真子图 设VV且V, 以V为顶点集, 以两端点都在V中的所有边为边集的G的子图称作V的导出子图, 记作GV 设EE且E, 以E为边集, 以E中边关联的所有顶点为顶点集的G的子图称作E的导出子图, 记作GE,实例,(1),(2),(3)是(1)的子图, (2),(3)是真子图, (1)是母图. (1),(3)是(1)的生成子图. (2)是d,e,f 的导出子图, 也是e5, e6, e7导出子图. (3)是e1,
13、e3, e5, e7的导出子图,补图,定义7.11 设G=为n阶无向简单图, 记 =VV -E, 称 为G的补图,图的同构,定义7.12 设G1=, G2=为两个无向图(有向图), 若存在双射函数 f: V1V2, 使得对于任意的vi,vjV1, (vi,vj)E1 (E1) 当且仅当 (f(vi), f(vj)E2 (E2) 并且 (vi,vj) () 与 (f(vi),f(vj) ()的重数相同， 则称G1与G2是同构的，记作G1G2.,实例,实例,例6 画出4阶3条边的所有非同构的无向简单图 解 总度数为6, 分配给4个顶点, 最大度为3, 且奇度顶点数为偶数, 有下述3个度数列: (1
14、) 1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.,1,1,1,3,1,1,2,2,0,2,2,2,实例,例7 画出3个以1,1,1,2,2,3为度数列的非同构的无向简单图,7.2 图的连通性,7.2.1 通路与回路 初级通路(回路)与简单通路(回路) 7.2.2 无向图的连通性与连通度 连通图、连通分支 短程线与距离 点割集、割点、边割集、割边(桥) 点连通度与边连通度 7.2.3 有向图的连通性及其分类 可达性 弱连通、单向连通、强连通 短程线与距离,通路与回路,定义7.13 给定图G=(无向或有向的), G中顶点与边的交替序列=v0e1v1e2elvl. 若i(1il),
15、ei=(vi1,vi)(对于有向图, ei=), 则称为v0到vl的通路, v0和vl分别为通路的起点和终点, l为通路的长度. 又若v0=vl, 则称为回路. 若通路(回路)中所有顶点(对于回路, 除v0=vl)各异, 则称为初级通路或路径(初级回路或圈). 长度为奇数的圈称作奇圈,长度为偶数的圈称作偶圈 若通路(回路)中所有边各异, 则称为简单通路(简单回路), 否则称为复杂通路(复杂回路),说明,(1) 表示方法 按定义用顶点和边的交替序列, =v0e1v1e2elvl 用边序列, =e1e2el 简单图中, 用顶点序列, =v0v1vl (2) 在无向图中, 长度为1的圈由环构成.长度为2的圈由两条平行边构成. 在无向简单图中, 所有圈的长度3. 在有向图中, 长度为1的圈由环构成. 在有向简单图中, 所有圈的长度2.,说明(续),(3) 初级通路(回路)是简单通路(回路), 但反之不真,初级通路,非初级的简单通路,初级回路,非初级的 简单回路,通路与回路(续),定理7.3 在n阶图中, 若从顶点u到v(uv)存在通路, 则从u到v存在长度小于等于n1的初级通路. 证 若通路中没有相同的顶点(即初级通路), 长度必 n1. 若有相同的顶点, 删去这两个顶点之间的这一段,
