08图论离散数学讲义海南大学共十一讲.docx

1、08图论离散数学讲义海南大学共十一讲8.图论 Topics in Graph Theory8.1 图GraphsG= V=v1,v2,vn 顶点vertex集。E= e | e=( vi, vj), vi,vjV, vivj无向边edge集。(e)= vi, vj, e的端点end points集。简写为G（V，E）。TD(vi)顶点vi的度数degree：连接到vi的边的条数。连接一个顶点的圈loop算两度。孤立点isolated vertex：度数为0的点。两个顶点相邻adjacent：有一边相连。定理1. (握手定理) TD TD(vi)=2m.推论. 任意图的奇数度顶点必有偶数多个。完

2、全图complete graph：任意两点都相邻简单图。定理2. n个顶点的完全图有n(n-1)/2条边。正则图regular graph：每个顶点都有相同的度数。E=|vi , vjV有向边集 有向图有向边 ， vi起点弧尾， vj终点弧头 TD(vi):顶点的度degree: 以vi为端点的边的数目。 OD(vi): 出度, 以vi为起点的边的数目。 ID(vi): 入度，以vi为终点的边的数目。 TD(vi)= OD(vi)+ ID(vi) OD=ID, TD=2|E|，E| =1/2*TD TD OD ID 为整个图的总度,出度,入度数。路径path： vivj， 以vi为起点vj为终

3、点的顶点序列，相邻顶点相邻。路径的长length: 路径上边的数目，简单路径simple path:点都不重复的路径，回路circuit : 首尾相接的路径，简单回路simple circuit: 除起点和终点以外都不重复的路径，vivj连通connected: 有路径 vivj相连。连通图: 任意两点都连通的图。例左图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 Graph

4、G=(V, E), G=(V, E)如果 V V, E E , 就称 G是G的子图subgraph。G的补图：(V, EE), G的边集中去掉E的边。Ge（V，E）, E=Ee.连通分量connected components: 一个图的极大连通子图。一个图可以划分成几个不相交的连通分量。强连通分量strong connected components: 一个有向图的极大强连通子图。商图quotient graphR是V上等价关系，V/R=v | vVE/R=(v, w) | v, w中有相邻的顶点GRG/R=(V/R, E/R),称为G模R的商图。把R相关的顶点粘合成一点，相关的边粘合成一边

5、，就得到商图。连通图的生成树spanning tree: 含有所有顶点的极小连通图.n个顶点连通图至少有n-1条边。m条边的连通图去掉mn1条边可以得到生成树。从连通图中如有回路，去掉回路中的一条边，继续直至没有回路，就得到生成树。从m条边的连通图中得到生成树，要去掉mn1条边T是连通图G的生成树，G的每一条不属于T的边e，叫弦。m条边的连通图共有mn1条弦。基本回路：每条弦加到T中得到一个回路，叫基本回路。m条边的连通图共有mn1个基本回路。割集：G的边集，去掉后G不连通。一条边组成的割集叫桥bridge。树的每条边都是桥。基本割集：生成树T中每一条边，和G中对应于T的所有的弦，组成一个割集

6、，叫基本割集。最小生成树：权重最小的生成树。带权的边：带边长的边。带权的图：每边都带权。Prim算法：设 G=, 1. 令 U=v0, T= . 2. 对任意uU, vV-U, (u,v)E, 找到权最小的边(u1,v1), 令U=Uv1, T=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连通。

7、 T 就是最小生成树8.2 欧拉路径和欧拉回路哥尼斯堡七桥问题。一笔画问题。欧拉路径Eular path：通过图的所有边，每个边恰好一次的路径。欧拉回路Eular circuit：构成回路的欧拉路径。定理1. G有欧拉回路当且仅当G连通且没有奇数度顶点。定理2. G有欧拉路径当且仅当G连通且至多有两个奇数度顶点。8.3 Hamilton路径和Hamilton回路周游世界问题：每个城市访问一次只经过一次。Hamilton公爵提出是否存在一条回路通过正二十边形每个顶点恰一次。一个连通图GHamilton路径: 经过每个顶点恰一次的路径。Hamilton回路：经过每个顶点恰一次的回路。Hamilto

8、n图：有Hamilton回路的图。完全图Kn，n2，是Hamilton 图。归纳可证。n个顶点的连通图G有Hamilton回路，G至少有n条边。用p(G)表示图G的连通分量的个数。定理1. G(V,E)是Hamilton图，则对任意V1V, 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相邻，av

9、ivjb是回路。设a，b不相邻。D(a)=s, D(b)=t.s+tm。tms。l中存在相连顶点vi，vj，a vj相邻，b vi相邻，avjbvia构成一个回路。定理3. n阶简单无向图G中， n2,任意两个不相邻顶点的度数之和大于等于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中所有顶点

10、的路径，长度比l更长。推论4. n阶简单无向图G中， n2,任意两个不相邻顶点的度数之和大于等于n，则G有Hamilton回路。证明. 由定理3，G有Hamilton路径。由引理2，这条路径可以构成一条Hamilton回路。推论5. n阶简单无向图G中， n2,任意顶点的度数大于等于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

11、8.5 匹配问题Matching Problem二部图、偶图 Bipartite Graph：无向图G(V,E), V= V1V2，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

12、 |时，完全匹配也叫完美匹配。定理2. （Hall定理）设G=( V1,V2 ,E),|V1|V2|.G中有完全匹配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

13、，a1,a2,，ak只与b1,b2,，bk相邻。则V1a1,a2,，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 p

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

15、n3时，每个面Ri，deg(Ri)=3.（3） n4时，每个顶点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.

16、证明.假设任意顶点v，D(v)6. 6n2m，3r2m 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)，1）d3. n=4l/(6l) l=3, n=4, m=6, r=4. 正四面体

17、 l4，n8，m=12, r=6, 正六面体. l5，n20，m=30, r=12, 正12面体 2）d4. n=2 l /(4 l).l =3, n=6, m=12, r=8, 正八面体。3）d5. n=4 l /(103l).l3，n12， m30，r20正20面体。对偶图：设G(T,V)是平面图，（1）G的每个面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的顶点数

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

19、的方法,记做PG(n).PG是一个多项式函数，称为chromatic 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

20、去掉e导出的子图，Ge是将e的两端点粘合得到的图。定理2. PG(x)PGe(x)PGe(x)证明. 设e的端点为a，b。G着色必须将ab着不同色。 Ge着色必须将ab着同色。Ge着色a，b可着同色，可着不同色。PGe(x)PG(x)+PGe(x).例 G如下图。 PGe(x)=x2(x-1)2(x-2)2,PGe(x)= x (x-1)2(x-2)2,PG(x)= PGe(x)PGe(x)=x2(x-1)2(x-2)2x (x-1)2(x-2)2x (x-1)3(x-2)2,(G)=3, G是3色图。引理3.设G是简单图，G已染色，相邻顶点颜色不同。G中染色两种颜色的顶点导出子图为G.交换G

21、中一个连通分量中染色和，G仍然保持相邻顶点不同颜色。证明.G中任意相邻两点a，b. b G，或a，bG，或aG且b G，a，b染色仍然不同。定理4（五色定理）G是任意一个平面图,则(G)5。证明.对G的顶点个数归纳。G中至少有一点a，D(a)5。归纳假设去掉a，导出的子图G可以用5重颜色着色。如果a只与G中4个点相邻，a可以用第五种颜色着色。 如果a与G中5个点相邻，但5点中有重复颜色，a可以用第五种颜色着色。假设a与G中5个点相邻，5点着色各不相同，5点分别是b1，b2，b5。 设b1着色，b2着色，而b1，b2，不在G的同一个连通分量中。由引理3，交换b3所在分量中颜色和，可以使b1，b3着色相同。这时a可着色。设b1着色，b3着色，而b1，b3在G的同一个连通分量中。这时b1到b2有一条着色相间的链。与a形成一条回路，组成一个面。b2在这个面的内部或在外部。如果同样b2，b4；b3，b5；b3，b5；b2，b5 ；b1，b4都有一个这样的链，相互交叉。这时a，b1，b2 ，b3，b4 ，b5组成一个K5。与G是平面图矛盾。这是不可能的。