图论离散数学讲义海南大学_第1页
图论离散数学讲义海南大学_第2页
图论离散数学讲义海南大学_第3页
图论离散数学讲义海南大学_第4页
图论离散数学讲义海南大学_第5页
已阅读5页,还剩15页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、8.图论 Topics in Graph Theory§8.1 图GraphsG=<V, E,> V=v1,v2,······,vn 顶点vertex集。E= e | e=( vi, vj), vi,vjV, vivj无向边edge集。(e)= vi, vj, e的端点end points集。简写为GV,E。TD(vi)顶点vi的度数degree:连接到vi的边的条数。连接一个顶点的圈loop算两度。孤立点isolated vertex:度数为0的点。两个顶点相邻adjacent:有一边相连。定理1. (握手定理

2、) TDåTD(vi)=2m.推论. 任意图的奇数度顶点必有偶数多个。完全图complete graph:任意两点都相邻简单图。定理2. n个顶点的完全图有n(n-1)/2条边。正那么图regular graph:每个顶点都有相同的度数。E=<vi, vj>|vi , vjV有向边集 有向图有向边 <vi, vj> , vi起点弧尾, vj终点弧头 TD(vi):顶点的度degree: 以vi为端点的边的数目。 OD(vi): 出度, 以vi为起点的边的数目。 ID(vi): 入度,以vi为终点的边的数目。 TD(vi)= OD(vi)+ ID(vi) OD=

3、ID, TD=2|E|,E| =1/2*TD TD OD ID 为整个图的总度,出度,入度数。路径path: vi······vj, 以vi为起点vj为终点的顶点序列,相邻顶点相邻。路径的长length: 路径上边的数目,简单路径simple path:点都不重复的路径,回路circuit : 首尾相接的路径,简单回路simple circuit: 除起点和终点以外都不重复的路径,vivj连通connected: 有路径 vi······vj相连。连通图: 任意两点都连通的图

4、。例bfgdceafdcaeb左图a,c,d,g是简单路径 右图a,d,b,c,e是简单路径。f,e,a,d,b,a,f是简单回路。f,e,d,c,e,f不是简单回路。有向图vivj强连通 vivj连通 vjvi也连通,强连通图 任意两点都强连通。子图和商图Subgraph and Quotient GraphG=(V, E), G=(V, E)如果 V ÍV, E ÍE , 就称 G是G的子图subgraph。G的补图:(V, EE), G的边集中去掉E的边。GeV,E, E=Ee.连通分量connected components: 一个图的极大连通子图。一个图可以划分成

5、几个不相交的连通分量。强连通分量strong connected components: 一个有向图的极大强连通子图。商图quotient graphR是V上等价关系,V/R=v | vVE/R=(v, w) | v, w中有相邻的顶点GRG/R=(V/R, E/R),称为G模R的商图。把R相关的顶点粘合成一点,相关的边粘合成一边,就得到商图。连通图的生成树spanning tree: 含有所有顶点的极小连通图.n个顶点连通图至少有n-1条边。m条边的连通图去掉mn1条边可以得到生成树。从连通图中如有回路,去掉回路中的一条边,继续直至没有回路,就得到生成树。从m条边的连通图中得到生成树,要去掉

6、mn1条边T是连通图G的生成树,G的每一条不属于T的边e,叫弦。m条边的连通图共有mn1条弦。根本回路:每条弦加到T中得到一个回路,叫根本回路。m条边的连通图共有mn1个根本回路。割集:G的边集,去掉后G不连通。一条边组成的割集叫桥bridge。树的每条边都是桥。根本割集:生成树T中每一条边,和G中对应于T的所有的弦,组成一个割集,叫根本割集。最小生成树:权重最小的生成树。带权的边:带边长的边。带权的图:每边都带权。Prim算法:设 G=<V,E>, 1. 令 U=v0, T= . 2. 对任意uU, vV-U, (u,v)E, 找到权最小的边(u1,v1), 令U=Uv1, T=

7、T(u1,v1) 3. 重复2,直至U=V. 得到 T就是最小生成树。 T中共有n-1条边 Kruskal 克鲁斯卡尔算法G=(V,E) 连通图令 T=(V, ) 是G的所有顶点而无边的非连通图。1. 选择E中权值最小的边, 假设该边连接T的两个连通分量,将它参加T, 这时T的连通分量减少1; 否那么选下一条权值最小的边。2. 重复1 n-1次直到T连通。 T 就是最小生成树§8.2 欧拉路径和欧拉回路哥尼斯堡七桥问题。一笔画问题。欧拉路径Eular path:通过图的所有边,每个边恰好一次的路径。欧拉回路Eular circuit:构成回路的欧拉路径。定理1. G有欧拉回路当且仅当

8、G连通且没有奇数度顶点。定理2. G有欧拉路径当且仅当G连通且至多有两个奇数度顶点。§8.3 Hamilton路径和Hamilton回路周游世界问题:每个城市访问一次只经过一次。Hamilton公爵提出是否存在一条回路通过正二十边形每个顶点恰一次。一个连通图GHamilton路径: 经过每个顶点恰一次的路径。Hamilton回路:经过每个顶点恰一次的回路。Hamilton图:有Hamilton回路的图。完全图Kn,n>2,是Hamilton 图。归纳可证。n个顶点的连通图G有Hamilton回路,G至少有n条边。用p(G)表示图G的连通分量的个数。定理1. G(V,E)是Ham

9、ilton图,那么对任意V1ÍV, p(G-V1)|V1|.证明:设C是G的一个Hamilton回路,V1都在C上。回路C中去掉V1中顶点,至多划分成|v1|段。因此p(C-V1)|V1|.例1. 以下图不是Hamilton图。引理2. n阶简单无向图G中,l: avivjb,是一条有m个顶点的路径。a,b只与l中顶点相邻,D(a)+D(b)m。那么l中所有顶点构成回路。证明.假设a,b相邻,avivjb是回路。设a,b不相邻。D(a)=s, D(b)=t.s+tm。tms。l中存在相连顶点vi,vj,a vj相邻,b vi相邻,avjbvia构成一个回路。定理3. n阶简单无向图G

10、中, n>2,任意两个不相邻顶点的度数之和大于等于n1,那么G有Hamilton路径。证明. 取G中最长路径:l: avivjb。我们证明其长度为n1,包含G的所有顶点,否那么一定可以加长。a, b不与l外的顶点相邻,否那么l可以加长。设l的长度n2,l上共有顶点少于n1个。a,b度数和大于n1,由引理1. l的所有顶点组成回路。这时有一顶点c不在l上,c c必与l中一点vi相邻。我们得到含有顶点c,和l中所有顶点的路径,长度比l更长。推论4. n阶简单无向图G中, n>2,任意两个不相邻顶点的度数之和大于等于n,那么G有Hamilton回路。证明. 由定理3,G有Hamilton

11、路径。由引理2,这条路径可以构成一条Hamilton回路。推论5. n阶简单无向图G中, n>2,任意顶点的度数大于等于n/2,那么G有Hamilton回路。定理6. G有n个顶点,m条边,如果,那么G是Hamilton图。证明.任取不相邻的两个顶点u,vG,G中去掉u,v后导出子图G,G有n2个顶点,至多条边。u,v到G的边数有D(u)+D(v)n.由推论4.G是Hamilton图。§8.4 运输网络Transport Networks§8.5 匹配问题Matching Problem二部图、偶图 Bipartite Graph:无向图G(V,E), V= V1V2

12、,V1V2Æ。V1中顶点互不相邻, V2中顶点互不相邻,任意边连接V1,V2中各一个顶点。G=( V1,V2 ,E).完全二部图:V1中每个顶点与V2 中每个顶点都相邻。| V1|=m , | V2|=n ,完全二部图记做Km,n。K2,3, K3,3.定理1.二部图中没有奇数长的回路。左边两图同构是K2,3,右边都是K3,3.E*ÍE. E*中的边互不相连,称E*为G的一个匹配。边数最大的匹配叫最大匹配。邻接V1或V2 中所有顶点的匹配叫完全匹配。|V1|=|V2 |时,完全匹配也叫完美匹配。定理2. Hall定理设G=( V1,V2 ,E),|V1|V2|.G中有完全匹

13、配iff V1中任意k个顶点至少与V2中任意k个顶点相邻,即,任意XÍ V1,|X|R(X)|, R(X)为与X中顶点相邻的顶点的集合。证明. Þ是显然的。Ü对V1中顶点个数归纳: | V1|=1是显然的。设| V1|=k时定理成立。| V1|=k1:1如果V1中任意k个顶点都至少与V2中k1个顶点相邻,从G中去掉一条边,V1中任意k个顶点都至少与V2中k个顶点相邻,存在完美匹配。2如果V1中存在k个顶点只与V2中k个顶点相邻,例如a1,a2,,akÍV1,b1,b2,,bkÍV2,a1,a2,,ak只与b1,b2,,bk相邻。那么V1a1,a

14、2,,ak任意s个顶点,都与V2b1,b2,,bk中s个顶点相连。两局部都有完美匹配。推论3.二部图G(V1,V2,E)中如果(1) V1中每个顶点至少与V2中t条边相邻。(2) V2中每个顶点至多与V1中t条边相邻。那么G有完美匹配。证明.V1中任意k个顶点的总度数kt。V2中任意k个顶点的总度数kt。V1中任意k个顶点至少与V2中k条边相邻。由Hall定理,G有完美匹配。推论4. 正那么二部图必有完美匹配。§8.6 染色图Coloring Graphs平面图planar grapha graph can be drawn in a plane so that no edges c

15、ross except at verticesK5, K3,3 不是平面图平面图的面:内部面,外部面, 有限面,无限面。 面的边界:包围这个面的回路不一定是简单回路。面的次数次数deg(R)=边界的长度。非连通平面图有一个公共外面,边界由k个回路组成,kp(G).平面图每条边都是两个面的交线。一条边处于一个内部面中或一个外部面中,面的次数要计算两次。定理1.平面图的所有面的次数之和等于边数的两倍:极大平面图:简单平面图,增加一边就不是平面图。极小非平面图:简单非平面图,减少一边就是平面图。定理2. n阶极大平面图的性质:(1) 连通。(2) n3时,每个面Ri,deg(Ri)=3.(3) n4

16、时,每个顶点v:D(v)3。定理3. 欧拉定理:满足nmr2,任意连通平面图G,满足nmr2, 即,顶点数边数面数2。证明. 对边数归纳:m0,1,2,3显然。 增加一边:增加一个顶点,不增加面。 不增加顶点,增加一面。推论4. 任意连通度为k的平面图G,满足nmrk1。不满足欧拉公式的简单图不是平面图。请验证K5,K3,3,不是欧拉图。定理5. 设G是连通平面图,每个面的次数至少l,l3,那么m。证明. 2mlr, nmr2,lnlm2m lnlmlr2l, lm2mln2l m。定理6. 简单连通平面图G中至少有一点v, D(v)5.证明.假设任意顶点v,D(v)6. 6n2m,3r2m

17、3nm nmr2 63n3m3rm3m2m0 这不可能。定理7.库拉图斯基定理一个图G是平面图当且仅当G没有可以收缩到K5或K3,3的子图。每个凸多面体都可以映射到平面图。定理8. 正多面体只有正4,6,8,12,20面体五种。证明.设G是一个正多面体,n个顶点,m条边,r个面,每个顶点d度,每个面l次。由定理6,3d5。l3。dn2m,lr=2mdn. nmr=2, 2ln2lm2lr=4l, 2lndln2dn=4l, n=4 l /(2ldl2d),1d3. n=4l/(6l) l=3, n=4, m=6, r=4. 正四面体 l4,n8,m=12, r=6, 正六面体. l5,n20,

18、m=30, r=12, 正12面体 2d4. n=2 l /(4 l).l =3, n=6, m=12, r=8, 正八面体。3d5. n=4 l /(103l).l3,n12, m30,r20正20面体。对偶图:设G(T,V)是平面图,1G的每个面Ri中取一点vi*, V*=v1*,v2*,vr*2假设两个面Ri,Rj有公共边界ek,连接vi*,vj*,得到边ek*, E*= e1*,e2*,em*那么得到G*=(V*,E*)称为G的对偶图。G和G*边数相同,m*m;G的面数等于G*的顶点数,n*=r;G连通,那么G的顶点数等于G*的面数, r*=n.G不连通,那么G的顶点数等于G*的面数,

19、 r*=np(G)1.G和G*不同构,同构图的对偶图不一定同构。G*不一定同构于G。不连通图的对偶图连通,连通图的对偶图连通。假设GG*,就称G是自对偶的图。染色图colouring Graph一个图用彩色将每个顶点着色,相邻顶点染不同颜色。一个平面图用彩色将每个面着色,相邻面染不同颜色。只要换成其对偶图即可。平面图G最少用k种颜色染色,就称为k色图。k称为chromatic number of G. 记做(G)四色定理:任何一个平面图都是四色图。染色多项式chromatic polynomial 用n种颜色染一个图,有多少不同的方法,记做PG(n).PG是一个多项式函数,称为chromati

20、c polynomial of G.例4. 设L4是4个顶点的一条线。用x种颜色,第一点,x种方法着色,第二点x1种方法着色。第三第四点都是x1。PL4(x)=x(x-1)3. (L4)2。例5PKn(x)x(x-1)(x-2)(x-n+1)=xn.(Kn)n。定理1. 设G1,G2,Gm是G的连通分量,那么PG(x)= PG1(x) PG2(x)PGm(x)。(G)max(G1), (G2),,(Gm)例6. G是两个不相连三角形,PG(x)= x2(x-1)2(x-2)2.例7. G是n个不相连顶点,PG(x)=xn。Ge是G去掉e导出的子图,Ge是将e的两端点粘合得到的图。定理2. PG(x)PGe(x)PGe(x)证明. 设e的端点为a,b。G着色必须将ab着不同色。 Ge着色必须将ab着同色。Ge着色a,b可着同色,可着不同色。PGe(x)PG(x

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论