《二编图论.ppt》由会员分享,可在线阅读,更多相关《二编图论.ppt(84页珍藏版)》请在三一文库上搜索。
1、 Peking University,1,第二编 图论,图论Graph Theory是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。 图论本身是应用数学的一部份,因此,历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论著中,他所考虑的原始问题有很强的实际背景。, Peking University,2,图论简介,图论起源于著名的七桥问题。A、B、C,D表示陆地。问题是要从这四块陆地中任何一块开始,通过每一
2、座桥正好一次,再回到起点。然而无数次的尝试都没有成功。欧拉在1736年解决了这个问题,他用抽象分析法将这个问题化为第一个图论问题:即把每一块陆地用一个点来代替,每一座桥用相应两点的一条线来代替,从而相当于得到一个图。欧拉证明了这个问题没有解,并且推广了这个问题,给出了对于一个给定的图可以某种方式走遍的判定法则。这项工作使欧拉成为图论及拓扑学的创始人。, Peking University,3,第7章 图,7.1 图的基本概念 7.2 通路与回路 7.3 无向图的连通性 7.4 无向图的连通度 7.5 有向图的连通性, Peking University,4,无序积,无序积: A,B为两个集合,
3、称 (a,b) |aAbB为A与B的无序积,记作A&B 允许 a = b 无序对: (a,b)=(b,a), Peking University,5,无向图(undirected graph),无向图(graph): 是一个有序的二元组,记作G (1) V, 顶点集,其元素为顶点或结点(vertex / node) (2) E称为边集,是无序积V&V的多重子集,其元素称为无向边,简称边(edge / link)., Peking University,6,有向图(directed graph),有向图(digraph): 是一个有序二元组,记作D (1)顶点集V, 结点/顶点(vertex /
4、 node) (2)边集, E是卡氏积VV的多重子集, 边(edge / link / arc), Peking University,7,例: G=,V=a,b,c,d,e, E=(a,a),(a,b),(a,b),(b,c),(c,d),(b,d).,a,b,c,d,e,例:无向图, Peking University,8,例: D=,V=a,b,c,d,e, E= , , .,a,b,c,d,e,例:有向图, Peking University,9,表示方法,图G:V(G), E(G)分别表示图G的顶点集和边集 图D:V(D),E(D) |V(G)|, |E(G)|, |V(D)|, |
5、E(D)|分别表示G和D的顶点数和边数, Peking University,10,n阶图(有向图): 若|V(G)|=n 或|V(D)|=n 有限图:若|V(G)|和|E(G)|均为有限数 零图(null graph): E=, n阶零图: |V(G)|=n, Nn 平凡图(trival graph): 1阶零图, N1 空图(empty graph): V=E=, 图定义中规定顶点集非空,由于图的运算中,可能产生点集为空集的运算结果, Peking University,11,标定图,非标定图,基图,标定图(labeled graph): 顶点或边标定字母 非标定图(unlabeled g
6、raph): 顶点或边不标定字母 基图(底图ground graph): 有向图各边的箭头都去掉,所得图为无向图,a,b,c,d, Peking University,12,关联(incident),关联(incident):图G中, 边ek=(vivj), ek与vi(ek与vi)彼此关联 (点与边) 关联次数: 若vivj ,称ek与vi(ek与vi)关联次数为1; 若vi=vj ,关联次数为2 环(loop):只与一个顶点关联的边 孤立点(isolated vertex):无边关联的点,vi,ek,vj,vi,ek, Peking University,13,相邻(adjacent),相
7、邻(邻接) :G, 任意两顶点vivj,存在边ek, ek=(vi,vj) ,称vi,vj彼此相邻 (点与点) 任意两边ek,el,至少存在一个公共端点,称ek,el彼此相邻(边与边) 邻接到,邻接于: 有向图D, ek=, vi邻接到vj, vj邻接于vi 平行边(parallel edge): 端点相同的两条无向边是平行边 起点与终点相同的两条有向边是平行边,vi,vj, Peking University,14,邻域(neighborhood),邻域: NG(v)=u|uV(G)(u,v)E(G)uv为v的邻域(v在图G中的相邻顶点) 闭(closed)邻域: 关联集: IG(v) =
8、e | e与v关联 后继:D+(v)=u|uV(D)E(D)uv 前驱:D-(v)=u|uV(D)E(D)uv 邻域: ND(v)=D+(v)D-(v) 闭邻域:, Peking University,15,顶点的度数(degree/valence),度dG(v): v作为G中边的端点的次数之和 出度dD+(v): v作为D中边的始点的次数之和 入度dD-(v): v作为D中边的终点的次数之和 度dD(v) = dD+(v) + dD-(v),0,3,3,4,0,0,1,2 (d+,d-),2,1,2,2, Peking University,16,最大(出/入)度,最小(出/入)度,最大度:
9、 (G) = max dG(v) | vV(G) 最小度: (G) = min dG(v) | vV(G) 最大出度: +(D) = max dD+(v) | vV(D) 最小出度: +(D) = min dD+(v) | vV(D) 最大入度: -(D) = max dD-(v) | vV(D) 最小入度: -(D) = min dD-(v) | vV(D) 简记为 , , +, +, -, -, Peking University,17,0,3,3,4,0,0,2,1,2,2,=0 =4,+ = 2, +=0 - =2, - = 0, Peking University,18,握手定理(图
10、论基本定理),定理1:设G=是无向图, V=v1,v2,vn, |E|=m, 则 d(v1)+d(v2)+d(vn)=2m. #,每一条边均有两个端点, 提供2度, m条边提供2m度, Peking University,19,定理2:设D=是有向图, V=v1,v2,vn, |E|=m, 则 d+(v1)+d+(v2)+d+(vn) = d-(v1)+d-(v2) +d-(vn) = m. #,d+, d-, Peking University,20,推论:任何图中,奇数度顶点的个数是偶数. # 证明:分为奇数度顶点集合V1和偶数度顶点集合V2, Peking University,21,简
11、单图(simple graph),简单图(simple graph): 无环,无平行边 若G是简单图, 则 0 (G) n-1, Peking University,22,度数列,度数列: 设G=,V=v1,v2,vn, 称 d = ( d(v1),d(v2), d(vn) ) 为G的度数列 例: d = ( 5, 1, 2, 3, 3 ),v2,v3,v4,v5,v1, Peking University,23,可图化,可图化:设非负整数列d=( d1,d2, , dn ), 若存在图G, 使得G的度数列是d, 则称d为可图化的 例: d = ( 5, 3, 3, 2, 1 ), Pekin
12、g University,24,定理3(可图化充要条件),定理3:非负整数列d=(d1,d2,dn)是可图化的, 当且仅当d1+d2+dn=0(mod 2). 证明: () 握手定理 () 奇数度点两两之间连一边, 剩余度用环来实现. #, Peking University,25,例2,例2: (1)d=(5,4,4,3,3,2); (2)d=(5,3,3,2,1)., Peking University,26,可简单图化,可简单图化:设非负整数列d=( d1, d2, , dn ), 若存在简单图G, 使得G的度数列是d, 则称d为可简单图化的, Peking University,27,
13、可简单图化充要条件,定理5(V. Havel, 1955):设非负整数列d=(d1,d2,dn)满足: d1+d2+dn=0(mod 2), n-1d1d2dn0, 则d可简单图化当且仅当 d=(d2-1,d3-1,dd1+1-1,dd1+2,dn) 可简单图化., Peking University,28,举例,例4: 判断下列非负整数列是否可简单图化. (1) (5,5,4,4,2,2) (2)(4,4,3,3,2,2) 解: (1) (5,5,4,4,2,2), (4,3,3,1,1), (2,2,0,0), (1,-1,0), 不可简单图化. (2) (4,4,3,3,2,2), (3
14、,2,2,1,2), (3,2,2,2,1), (1,1,1,1), (0,1,1),(1,1,0), (0,0), 可简单图化. #, Peking University,29,定理5(图示),v1,v2,v3,vd1+1,vn,vd1+2,v2,v3,vd1+1,vn,vd1+2,G,G,d = (d1,d2,d3,dd1+1,dd1+2,dn),d = (d2-1,d3-1,dd1+1-1,dd1+2,dn), Peking University,30,定理5(证明),证明: () 设 d=(d2-1,d3-1,dd1+1-1, dd1+2, , dn) 可简单图化为 G=, 其中 V=
15、v2,v3,vn, 则令G=, V=Vv1, E = E (v1,v2), (v1,v3), , (v1,vd1+1) , 于是d可简单图化为G., Peking University,31,定理5(证明,续),证明: () 设d可简单图化为G=, 其中V=v1,v2,vn, d(v1)d(v2)d(vn). (1) 若NG(v1)=v2,v3, ,vd1+1, 则令 G=, V=V-v1, E=E- (v1,v2), (v1,v3), , (v1,vd1+1) , 于是d可简单图化为G. (2) 若ij( ij viNG(v1) vjNG(v1) ), Peking University,3
16、2,定理5(示意),v1,v2,vi,vd1+1,vn,vk,G,d = (d1,d2,d3,dd1+1,dd1+2,dn),vj,v1,v2,vi,vd1+1,vn,vk,G1,d = (d1,d2,d3,dd1+1,dd1+2,dn),vj,v1NG(vi)v1NG(vj)didj vk(vkNG(vi)vkNG(vj), Peking University,33,定理5(示意),v1,v2,vi,vd1+1,vn,vk,G,d = (d1,d2,d3,dd1+1,dd1+2,dn),vj,v1,v2,vi,vd1+1,vn,vk,G1,d = (d1,d2,d3,dd1+1,dd1+2,
17、dn),vj, Peking University,34,定理5(证明,续),证明: () (2)若ij(1i, 则G1与G的度数列都还是d,重复这个步骤, 直到化为(1)中情形为止. #, Peking University,35,定理4 (可简单图化充要条件),定理4(P.Erds,T.Gallai,1960):设非负整数列d=(d1,d2,dn)满足: n-1d1d2dn0, 则d可简单图化当且仅当 d1+d2+dn=0(mod 2) 并且对r=1,2,n-1有 d1+d2+dr r(r-1)+minr,dr+1+minr,dr+2+minr,dn. #, Peking Universi
18、ty,36,Paul Erds(1913-1996),一生中同485位合作者发表过1475篇数学论文,每天工作19个小时以上。 Another roof, Another proof “Erdos数“是数学界流传的一个典故。即给每一个数学家赋予一个Erdos数:Erdos本人的Erdos数是0;曾与Erdos合作发表过文章的人的Erdos数是1;没有与Erdos合作发表过文章,但与Erdos数为1的人合作过的是2;不属于以上任何一类的就是., Peking University,37,几乎每一个当代数学家都有一个有限的Erdos数,而且这个数往往非常小 Fields奖得主的Erdos数都不超过
19、5 Nevanlinna奖得主的Erdos数不超过3 Wolf数学奖得主的Erdos数不超过6 Steele奖的终身成就奖得主的Erdos数不超过4. 一些其他领域的专家, Bill Gates,他的Erdos数是4,通过如下途径实现:Erdos-Pavol Hell-Xiao Tie Deng-Chris tos H. Papadimitriou-William H. (Bill) Gates, Peking University,38,定理4(举例),例3: 判断下列非负整数列是否可简单图化. (1) (5,4,3,2,2,1) (2)(5,4,4,3,2) (3) (3,3,3,1) (
20、4)(6,6,5,4,3,3,1) (5) (5,5,3,3,2,2,2) (6) (d1,d2,dn), d1d2dn1, 解: (1) 5+4+3+2+2+1=170(mod 2). 不可(简单)图化., Peking University,39,定理4(举例),例3: 判断下列非负整数列是否可简单图化. (2)(5,4,4,3,2) 解: (2) 5+4+4+3+2=18=0(mod 2). 但是d1=5n-1=4,不满足n-1d1, 不可简单图化. ( 或者: 但是r=1时, d1=51(1-1)+min1,4 +min1,4+min1,3 +min1,2=4, 不可简单图化.), P
21、eking University,40,定理4(举例),例3: 判断下列非负整数列是否可简单图化. (3) (3,3,3,1) 解: (3) 3+3+3+1=10=0(mod 2). d1=3=n-1,满足n-1d1, 但是r=2时, d1+d2=62(2-1)+min2,3+min2,1=5, 不可简单图化., Peking University,41,定理4(举例),例3: 判断下列非负整数列是否可简单图化. (4)(6,6,5,4,3,3,1) 解: (4) 6+6+5+4+3+3+1=28=0(mod 2). d1=6=n-1,满足n-1d1. r=1,2时, d1=61(1-1)+m
22、in1,6+min1,5+ =6, d1+d2=122(2-1)+min2,5+=11, 不可简单图化. 或:6,6,*,*,*,*,1不可简单图化, Peking University,42,定理4(举例),例3: (5) (5,5,3,3,2,2,2) 解: (5) 5+5+3+3+2+2+2=22=0(mod 2). d1=5n-1,满足n-1d1. r=1,2,7时, d1=51(1-1)+min1,5+min1,5+ =6, d1+d2=102(2-1)+min2,3+=12, d1+d2+d3 =133(3-1)+min3,3+=15, d1+d2+d3+d4 =164(4-1)+
23、min4,2+=18, Peking University,43,定理4(举例),例3: (5) (5,5,3,3,2,2,2) 解: (5) d1+d2+d5 =185(5-1)+min5,2+=24, d1+d2+d6 =206(6-1)+min6,2=32, d1+d2+d7 =227(7-1)=42, 可简单图化., Peking University,44,定理4(举例),例3: (5) (5,5,3,3,2,2,2) 解: (5) 可简单图化. (5,5,3,3,2,2,2), (4,2,2,1,1,2), (4,2,2,2,1,1), (1,1,1,0,1),(1,1,1,1),
24、 (0,1,1),(1,1), Peking University,45,定理4(举例),例3: 判断下列非负整数列是否可简单图化. (6) (d1,d2,dn), d1d2dn1, 解: (6) d1d2dn1, dn-12, dn-23, d1n,不满足n-1d1, 不可简单图化. #, Peking University,46,图同构(graph isomorphism),图同构: 设(有向)图G1=, G2=, 若存在双射 f:V1V2, 满足uV1,vV1, (u,v)E1 (f(u),f(v)E2 且与重数相同, 则称G1与G2同构, 记作G1G2 算法:NAUTY, Peking
25、 University,47,图同构(举例),G1,G2,G3, Peking University,48,图同构(举例),G1,G2,G3,G1G3, G1G2, Peking University,49,图同构(举例),G1,G2,G3,G1G2G3,彼得森(Peterson)图, Peking University,50,图同构(举例),D1,D2,D3,D1D2, D2D3, Peking University,51,同构关系,同构关系是全体图集合上的二元关系 自反的 对称的 传递的 同构关系是等价关系, Peking University,52,图族(graph class),完全图
26、,有向完全图,竞赛图 正则图:柏拉图图,彼德森图,库拉图斯基图 r部图,二部图(偶图),完全r部图 路径,圈,轮, Peking University,53,完全图(complete graphs),K1,K2,K3,K4,K5,每个顶点均与其余的n-1个顶点相邻,记作Kn, Peking University,54,有向完全图, Peking University,55,竞赛图(tournament), Peking University,56,正则图(regular graph),k正则图: vV(G), d(v)=k, r=0,1,2, 完全图Kn是n-1正则图(n=1,2,3,), P
27、eking University,57,柏拉图图(Platonic graphs),正四面体图,正六面体图,正八面体图,正十二面体图,正二十面体图, Peking University,58,彼德森图(Pertersen graph), Peking University,59,库拉图斯基图(Kuratowski graph),K3,3,K5, Peking University,60,r部图(r-partite graphs),r部图: G=,若V分成r个互不相交的子集,使得G中任何一条边的两个端点都不在同一个Vi中, 即 V=V1V2Vr, ViVj= (ij),EU(Vi E., Pek
28、ing University,61,二部图(偶图)(bipartite graphs),二部图: G=, 也称为偶图, Peking University,62,完全r部图(complete r-partite graphs),K3,3,K2,3,Kr,s,K1,1,1,K1,1,2,K1,2,2,K1,2,3,r个,s个,Kn1,n2,nr:Vi中任一个顶点均与Vj(ij)所有顶点相邻, Peking University,63,圈(cycles),C1,C2,C3,C4,C5, Peking University,64,轮(wheels),W1,W2,W3,W4,W5, Peking Un
29、iversity,65,树(trees),树: 连通无回图, Peking University,66,子图,生成子图,子图(subgraph): G=, G=, GG VV EE 真子图(proper subgraph): GG GG (VV EE) 生成子图(spanning subgraph): G是G的生成子图 GG V=V, Peking University,67,导出子图(induced subgraph),导出子图: G=, 若V1V, 以G中两个端点都在V1中的边组成边集E1的图,即E1 = E V1&V1,GV1 = 为由V1导出的子图 若E1E, 以E1中的边关联的点为顶
30、点集V1, 则称GE1 = 为由E1导出的子图, Peking University,68,导出子图(举例),G,e1,GV1,GE1,v1,v2,v3,v4,v5,v6,v7,v1,v4,v5,v6,v7,e2,e3, Peking University,69,补图(complement graph),补图: 以V为顶点集,以使G称为n阶完全图的所有添加边组成的集合为边集的图,为G的补图, 即G=, G= 自补图(self-complement graph):GG, Peking University,70,例5,例5: (1) 画出5阶4条边的所有非同构的无向简单图; (2)画出4阶2条边
31、的所有非同构的有向简单图. 解: (1) d(v)=2m=8, n-1=4, (4,1,1,1,1),(3,2,1,1,1),(2,2,2,1,1), (3,2,2,1,0),(2,2,2,2,0) (2) d+(v)=d-(v)=m=2, d(v)=2m=4, (2,1,1,0),(1,1,1,1),(2,2,0,0), Peking University,71,例5(1),例5: (1) 画出5阶4条边的所有非同构的无向简单图; 解: (1),4,1,1,1,1,3,2,1,1,1,2,2,2,1,1,2,2,2,1,1,3,2,2,1,0,2,2,2,2,0, Peking Univer
32、sity,72,例5(2),例5: (2)画出4阶2条边的所有非同构的有向简单图. 解: (2),2,1,1,0,2,1,1,0,2,1,1,0,1,1,1,1,2,2,0,0, Peking University,73,图的运算,删除,收缩,加新边,不交 并图,交图,差图,环和 联图,积图, Peking University,74,删除(delete),删除边e: G-e = 删除边集E: G-E = , 删除顶点v以及v所关联的所有边:G-v = , 删除顶点集V以及V所关联的所有边:G-V = , Peking University,75,收缩(contract),Ge: e=(u,v
33、)E, 删除e,将e的两个端点u与v用一个新的顶点w代替,使w关联除e之外的u,v关联的所有边,e,u,v,w, Peking University,76,加新边(add new edge),G(u,v) = , 在u与v之间加新边 也写成G+(u,v), Peking University,77,不交(non-intersect),G1=, G2=, G1与G2不交 V1V2= G1与G2边不交(边不重) E1E2=, Peking University,78,并图,交图,差图,环和(ring sum),G1=, G2=, 都无孤立点 并图: 以E1E2为边集,以E1E2中边关联的顶点组成的
34、集合为顶点集的图,即: G1G2 = 交图: G1G2 = 差图: G1-G2 = 环和: G1G2 = = ( G1G2)-(G1G2), Peking University,79,性质,G1G2 = (G1G2)-(G1G2) G1=G2时, G1G2 = G1G2 = G1 = G2 G1G2 = G1-G2 = G1与G2边不重时, G1G2 = , G1-G2 = G1, G2-G1 = G2, G1G2 = G1G2, Peking University,80,联图(join),联图: G1=, G2=, 不交的无向图,以V1V2为顶点集, E=E1E2 (u,v)|(uV1)(v
35、 V2)为边集的图, 记作:G1+G2 Kr+Ks=Kr+s Nr+Ns=Kr,s 若|V1|=n1, |E1|=m1, |V2|=n2, |E1|=m2, n=n1+n2, m=m1+m2+ n1n2, Peking University,81,*积图(product),G1=, G2=, 无向简单图 积图: G1G2=, 其中 E = (,) | (,V1V2) (ui=vkuj与vs相邻) (uj=vsui与vk相邻) 若|Vi|=ni, |Ei|=mi, n=n1n2, m=n1m2+ n2m1, Peking University,82,积图(举例),a,b,0,1,2,0,1,00,01,10,11,000,001,010,011,100,101,110,111,Q1=K2,Q2=K2Q1,Qk=K2Qk-1, Peking University,83,总结,1.预备知识,无向图,有向图,相邻,关联 2.度,握手定理,度数列,可(简单)图化 3.图同构 4.图族 5. 图运算, Peking University,84,P131: 1,2,5,7 ,11(无向图),作业,
链接地址:https://www.31doc.com/p-2552492.html