组合数学公开课一等奖优质课大赛微课获奖课件.pptx

第 11 章图 论 引 导第1页第1页11.1 基 本 性 质11.1基本性质图G是个二元组 G=(V，E)；其中，V是图G顶点集合，且V是有限集；E V V=(x，y)|x，y V，x y称为图G边集，且若边=(x，y)E，则边=(y，x)E，且，被视为同一条边。这样图G，我们也称作简朴图。顶点集合V中顶点个数称为图G阶。若=(x，y)E是图G一条边，则说边连接顶点x和y；或者说，顶点x和y是邻接；或者说，顶点x和y均依附于边，即，x和，y和 是关联。第2页第2页例 G是一个5阶图 G=(V,E)其中 V=a,b,c,d,e；E=(a,b),(b,c),(c,d),(d,a),(e,a),(e,b),(e,d)G可图示为11.1 基 本 性 质第3页第3页 假如边集E是一个多重集，则 G=(V,E)是一个多重图。在多重图 G=(V,E)中，若边=(x,y)在E中出现了m次，则称m是边重数，记作 m(x,y)。对于多重图 G=(V,E)，若边集E中允许出现形如(x,x)边，则称G是普通图，其中边(x,x)称作球。11.1 基 本 性 质第4页第4页例11.1 基 本 性 质第5页第5页 对于图G=(V,E)，若V中任意一对不同顶点x,y，都有(x,y)E，则称G是一个 n=|V|阶完全图。对于n阶简朴完全图而言，它所包含边数是 n(n-1)/2。把此图、记作Kn。例K1K2K3K4K511.1 基 本 性 质第6页第6页 对于图 G=(V,E)，若在平面上存在一个画法，使得E中任意两条边均不相交（仅能在顶点处相交），则称G是一个平面图。在普通图 G=(V,E)中，x V，顶点x度deg(x)是与x关联边条数。尤其，若=(x,x)E，则使x度增长了2。设 V=x1,x2,xn，则deg(xi)=di，i=1,2,n，使得d1 d2 dn 0，则称 （d1,d2,dn）是图G度序列。定理11.1.1 设G 是一个普通图，则其所有顶点度数 之和 d1+d2+dn 是一个偶数，从而，其奇度顶点个数也必为偶数。11.1 基 本 性 质第7页第7页 设G=(V,E),G=(V,E)均是普通图。若存在1-1相应：V V使得：x,y V，(x,y)在E中重数等于(x),(y)在E中重数，则称G和G是同构，相应称为G和G一个同构。11.1 基 本 性 质第8页第8页例 设 G=(a1,a2,a3,a4,E)G=(x1,x2,x3,x4,E)定义(ai)=xi i=1,2,3,4 且若(ai,aj)E，iff(xi,xj)E 则 G 和G同构。a1a2a3a4x1x2x3x411.1 基 本 性 质第9页第9页例11.1 基 本 性 质第10页第10页例11.1 基 本 性 质第11页第11页定理11.1.2 两个同构普通图含有相同度序列。反之，则不一定。11.1 基 本 性 质第12页第12页 设G（V，E）是一个普通图，x0，xmV，若存在（xi,xi+1）E,i=0,1,2,m-1 则称由这m个边构成序列:（x0,x1）,(x1,x2),(xm-1,xm)是连接顶点x0和xm一条长度为m路径，记作：x0 x1x2xm若x0 xm，则称该路径为开，不然为闭路径。无重复边路径称为迹；无重复顶点路径称为链；x0 xm链称为圈。11.1 基 本 性 质第13页第13页 设G=(V，E)是一个普通图，x，yV，G中均存在连接x和y路径，则称G是连通图；不然G是非连通图。设G=(V,E)是一个连通图，x，yV,x和y之间距离是连接x和y 路径最短长度，记作d（x，y）。11.1 基 本 性 质第14页第14页 设G=(V,E)是普通图，G=(U,F)也是普通图，使得：且 (x,y)F，有x，yU，则称G是G普通子图。进一步，若 x，yU，(x,y)E，必有(x,y)F，则称G是GU导出普通子图，记为GuG；在G中，若UV，则称G为G生成子图。11.1 基 本 性 质第15页第15页11.1 基 本 性 质第16页第16页定理11.1.3 设G=(V,E)是普通图，则V存在划分 V1，V2，,Vk：使得：i）由Vi导出普通子图Gi=(Vi,Ej)是连通，1ik；)若ij，则 xVi和 yVj，G中不存在连接 x和y路径。并称Gi是G连通分量(连通分支，连通分图)，1ik。ViVj=ij,Vi 1i k 11.1 基 本 性 质第17页第17页定理11.1.4 设G=(V,E)，G=(V,E)，则G与G同构必有：)若G是简朴图，则G也是简朴图；)G与G含有相同数目的连通分量；)若G存在一个长度为m圈，则G亦然；)若G存在一个m阶完全图Km是G(导出)普通子 图，则G 亦然。11.1 基 本 性 质第18页第18页 设G=(V,E)是n阶普通图，V(x1,x2,xn)。现定义nn矩阵 A(aij)nn：aij连接xi和xj边数目 1 i，j n则称A是G邻接矩阵。11.1 基 本 性 质第19页第19页例Ax1 x2 x3 x4 x5 x60 1 2 0 1 01 1 0 0 2 02 0 0 1 1 10 0 1 1 2 21 2 1 2 0 00 0 1 2 0 0 x1 x2 x3 x4 x5 x611.1 基 本 性 质第20页第20页11.2 欧 拉 迹11.2 欧拉迹 设G(V,E)是一个普通图。若 x,yV，连接x和y迹包括了E中每一条边，则该迹称作欧拉迹。比如第21页第21页引理11.2.1 设G(V,E)是普通图，若 x V，deg(x)为偶数，则G每条边均属于一条闭迹，因而也属于一个圈。定理11.2.2 设G(V,E)是连通普通图，则G中存在闭欧拉迹，iff x V，deg(x)是偶数。例11.2 欧 拉 迹第22页第22页定理11.2.3 设G(V,E)是连通普通图，则G中存在一条开欧拉迹 iff G中正好有两个奇度顶点u，v。且G中任意一条开欧拉迹均连接u和v。例11.2 欧 拉 迹第23页第23页定理11.2.4 设G(V,E)是连通普通图，G中奇度顶点个数m0，则G边可划分为m/2个开迹，但不能划分为少于m/2个开迹。例11.2 欧 拉 迹第24页第24页例11.2 欧 拉 迹第25页第25页 中国邮递员问题：设G(V,E)是连通普通图，G中是否存在一条最短路径r，使得 ，e至少在r中出现一次。定理11.2.5 设G(V,E)是一个含有K|E|条边连通普通图，则G中存在一条长度为2K闭路径r，使得 ，e在r中出现次数等于e重数2倍。分析 G：G*G*中每条边重数均是G中每条边重数2倍，且共有2K条边。依据定理11.2.2，G*中存在一条闭欧拉迹。此欧拉迹即G中所求。11.2 欧 拉 迹第26页第26页例11.2 欧 拉 迹第27页第27页11.3 Hamilton链和Hamilton圈11.3 Hamilton链和Hamilton圈 设G(V,E)是一个简朴图，是否存在一个圈r，使得 ，x在r中出现一次且仅出现一次。若这样图存在，则称其为Hamilton圈。相应，若G中存在一条链，使得 ，x在该链中出现一次且仅出现一次，则该链是 Hamilton链。第28页第28页例 关于Kn（n 3）例11.3 Hamilton链和Hamilton圈第29页第29页 设 G(V,E)是一个连通简朴图，若 ，使得图G*（V，Ee）是非连通图，则称边e是图G一个桥。定理11.3.1 带有桥连通图中不存在Hamilton圈。11.3 Hamilton链和Hamilton圈第30页第30页 设 G(V,E)是一个简朴图，且|V|=n。若 ，即x与y不邻接，都有：deg（x）deg（y）n则称图G含有Ore性质。定理11.3.2 设G是一个满足Ore性质，阶数n 3简朴图，则G中存在Hamilton圈。11.3 Hamilton链和Hamilton圈xyyx第31页第31页11.4 二 分 多 重 图11.4 二分多重图 设 G(V,E)是一个多重图，若V存在划分X，Y：XY=V,XY=,X ,Y 使得 (x，y)E，x，则称图G是一个二分多重图，相应 X，Y称为一个二分划。第32页第32页例11.4 二 分 多 重 图第33页第33页11.4 二 分 多 重 图第34页第34页定理11.4.1 一个多重图是二分 iff 它任意一个圈 长度均是偶数。分析 1)G(V,E)是二分多重图 G任意一个圈长度均是偶数。由于G是二分，因此G存在一个二分划X,Y。依据二分图定义，G中任一路径上之顶点必交替于X和Y之间，故|X|Y|。因此G任一圈其长度必是偶数。11.4 二 分 多 重 图第35页第35页 2)G(V,E)任一圈长度是偶数 G是二分。设G是连通，任取一个x V，令 X=y|y到x距离是偶数，y V Y=y|y到x距离是奇数，y V则X，Y必是G一个分划。不然，则有（a，b）E，使a，b X。即 a-x 和 b-x 长度均是偶数。于是有圈：a-x b-x 其长为奇数。这与条件矛盾。故不存在（a，b）E使a，b X；同样，也不存在(a，b)E使a，b Y。从而X，Y是G二分划。若G是不连通，则其每个连通分量均是二分。11.4 二 分 多 重 图第36页第36页例 考虑全部n位二进制数组成集合V，令 E=（x，y）|x，y V，x与y仅有一位不同则Qn=（V，E）是二分图。因为令 X=x|x有偶数个1，x V Y=x|x有奇数个1，x V则X，Y组成Qn一个二分划。Q1Q2Q311.4 二 分 多 重 图第37页第37页定理11.4.2 设G是一个含有二分划X，Y二分图，1）假如|X|Y|，则G中不存在Hamilton圈；2）假如|X|=|Y|，则G中不存在起始于X（或Y）中顶点又终止于X（或Y）中顶点Hamilton链；3）假如|X|Y|+2，或|Y|X|+2则G中不存在Hamilton链；4）假如|X|=|Y|+1，则G中不存在起始于X终止于Y中Hamilton链，反之亦然。11.4 二 分 多 重 图第38页第38页例（骑士问题）给定一个88棋盘，棋盘上一个格子表示一个位置，并遵循下列移动规则：1 垂直移动2格并水平移动1格，或者 2 垂直移动1格并水平移动2格。现在问题是：骑士从任意指定位置出现。按照移动规则，是否存在一个也许，使得骑士在棋盘上每一格正好出项一次？骑士环游 假如存在上述也许，那么当骑士到达最后一格时，遵循同样移动规则，是否能够回到本来起始置？重复环游11.4 二 分 多 重 图第39页第39页5843 6037 52 41 64 354946 5742 61 36 53 404459 4851 38 55 34 634750 4556 33 62 39 5422732124 13 18 1531223619 16 27 12821 429 10 25 14 17330 920 528 1126 设G(V,E)是一个二分图。G二分划是X，Y。且|X|=m，|Y|=n，则记该二分图为Km，n=(X，Y，E)。11.4 二 分 多 重 图第40页第40页11.5 树11.5 树 设G(V,E)是n阶连通图，且G中不含圈，则称G是n阶树。定理11.5.1 一个n阶连通图至少有n-1条边。另外，对于任意一个正整数n，存在一个正好为n-1条边连通图。从n个顶点，n-1条边连通图中去掉任意一条边，得到一个不连通图，因此，每条边都是一个桥。定理11.5.2 一个n1阶连通图是树，iff G正好有n-1条边。引理11.5.3 设G是一个连通图，=（x，y）是G一条边。是桥，iff G任何圈中不包括。第41页第41页定理11.5.4 设G是一个n阶连通图，则G是树，iff G 中无圈。定理11.5.5 一个图G是树，iff 任意一对不同顶点x，y 之间，都有唯一一条链，且该链是长度为 d（x，y）链。定理11.5.6 设G是一个n阶n 2树，则G中最少有 2个悬挂顶点。定理11.5.6 任何连通图都有一个生成树。11.5 树第42页第42页