离散数学屈婉玲第九章

1第三部分图论本部分主要内容图的基本概念树欧拉图与哈密顿图二部图与匹配平面图着色2第九章图的基本概念主要内容图通路与回路图的连通性图的矩阵表示预备知识多重集合——元素可以重复出现的集合无序集——AB={(x,y)|xAyB}14.1图定义9.1无向图G=V,E,其中(1)V为非空有穷集,称为顶点集，其元素称为顶点(2)E为VV的多重有穷集,称为边集,其元素称为无向边,简称边例无向图G=V,E,其中V={v1,v2,v3,v4,v5},E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}4有向图定义9.2有向图D=V,E,其中(1)V为非空有穷集,称为顶点集，其元素称为顶点(2)E为VV的多重有穷集,称为边集,其元素称为有向边,简称边例有向图D=V,E,其中V={a,b,c,d}E={a,a,a,b,a,b,a,d,d,c,c,d,c,b}注意：图的集合表示与图形表示之间的对应5相关概念1.无向图和有向图通称图.记顶点集V(G),边集E(G).2.图的阶,n阶图.3.n阶零图Nn,平凡图N1.4.空图.5.标定图与非标定图.6.有向图的基图.7.无向图中顶点与边的关联及关联次数,顶点与顶点、边与边的相邻关系.8.有向图中顶点与边的关联,顶点与顶点、边与边的相邻关系.9.环,孤立点.6多重图与简单图定义9.3无向图中关联同一对顶点的2条和2条以上的边称为平行边.有向图中2条和2条以上始点、终点相同的边称为平行边.平行边的条数称为重数.含平行边的图称为多重图,不含平行边和环的图称为简单图.定义9.4设G=V,E为无向图,vV,称v作为边的端点的次数之和为v的度数,简称度,记作d(v).设D=V,E为有向图,vV,称v作为边的始点的次数之和为v的出度,记作d+(v);称v作为边的终点的次数之和为v的入度,记作d(v);称d+(v)+d(v)为v的度数,记作d(v).7顶点的度数设G=V,E为无向图,G的最大度(G)=max{d(v)|vV}G的最小度(G)=min{d(v)|vV}设D=V,E为无向图,D的最大度(D)=max{d(v)|vV}D的最小度(D)=min{d(v)|vV}D的最大出度+(D)=max{d+(v)|vV}D的最小出度+(D)=min{d+(v)|vV}D的最大入度(D)=max{d(v)|vV}D的最小入度(D)=min{d(v)|vV}悬挂顶点:度数为1的顶点,悬挂边:与悬挂顶点关联的边.偶度(奇度)顶点:度数为偶数(奇数)的顶点8实例d(v1)=4,d(v2)=4,d(v3)=2,d(v4)=1,d(v5)=3.=4,=1.v4是悬挂点,e7是悬挂边.d+(a)=4,d(a)=1,d(a)=5,d+(b)=0,d(b)=3,d(b)=3,d+(c)=2,d(c)=1,d(c)=3,d+(d)=1,d(d)=2,d(d)=3,+=4,+=0,=3,=1,=5,=3.9定理9.1在任何无向图中,所有顶点的度数之和等于边数的2倍.证G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m条边共提供2m度.握手定理定理9.2在任何有向图中，所有顶点的度数之和等于边数的2倍;所有顶点的入度之和等于所有顶点的出度之和,都等于边数.推论任何图(无向或有向)中，奇度顶点的个数是偶数.证由握手定理,所有顶点的度数之和是偶数,而偶度顶点的度数之和是偶数,故奇度顶点的度数之和也是偶数.所以奇度顶点的个数必是偶数．10例1无向图G有16条边，3个4度顶点，4个3度顶点，其余均为2度顶点度，问G的阶数n为几？解本题的关键是应用握手定理.设除3度与4度顶点外，还有x个顶点,由握手定理,162=32=34+43+2x解得x=4,阶数n=4+4+3=11.握手定理应用定理9.3设G为任意n阶无向简单图，则(G)n1．图的同构定义9.5设G1=V1,E1,G2=V2,E2为两个无向图(两个有向图)，若存在双射函数f:V1V2,使得vi,vjV1,(vi,vj)E1当且仅当(f(vi),f(vj))E2（vi,vjE1当且仅当f(vi),f(vj)E2)并且,(vi,vj)（vi,vj）与(f(vi),f(vj))（f(vi),f(vj)）的重数相同，则称G1与G2是同构的，记作G1G2.例12图同构的实例(1)(2)(3)(4)(1)与(2),(3)与(4),(5)与(6)均不同构.(5)(6)说明:1.图的同构关系具有自反性、对称性和传递性.2.判断两个图同构是个难题图同构的实例所有4阶3条边非同构的简单无向图13所有3阶2条边非同构的简单有向图补图与自补图定义9.6设G=V,E为n阶无向简单图，令={(u,v)|uVvVuv(u,v)E},称=V,为G的补图．若G则称G是自补图．EEGG例(b)与(c)互为补图，(a)是自补图．15完全图与竞赛图定义9.7(1)n(n1)阶无向完全图——每个顶点与其余顶点均相邻的无向简单图，记作Kn.简单性质：m=n(n-1)/2,==n-1(2)n(n1)阶有向完全图——每对顶点之间均有两条方向相反的有向边的有向简单图.简单性质：m=n(n-1),==2(n-1)+=+===n-1(3)n(n1)阶竞赛图——基图为Kn的有向简单图.简单性质：m=n(n-1)/2,==n-1正则图K53阶有向完全图4阶竞赛图定义9.8k-正则图——==k的无向简单图简单性质：m=kn/2,当k是奇数时,n必为偶数.例Kn是(n1)-正则图彼得松图是3-正则图子图定义9.9设两个图G=V,E,G=V,E（同为无向图或同为有向图）,若VV且EE，则称G是G的子图，G为G母图，记作GG.又若VV或EE，则称G为G的真子图.若GG且V=V，则称G为G的生成子图．设V1V且V1,称以V1为顶点集,以G中两个端点都在V1中的边组成边集的图为G中V1的导出子图,记作G[V1].设E1E且E1,称以E1为边集,以E1中边关联的顶点为顶点集的图为G中E1的导出子图,记作G[E1]．例GG[{a,b,c}]G[{e1,e3}]18定义9.10设G=V,E为无向图．(1)设eE，用Ge表示从G中去掉边e，称为删除边e．又设EE，用GE表示从G中删除E中的所有边，称为删除E．(2)设vV，用Gv表示从G中去掉v及所关联的所有边，称为删除顶点v．又设VV，用GV表示从G中删除V中所有的顶点，称为删除V．(3)设e=(u,v)E，用G＼e表示从G中删除e后，将e的两个端点u,v用一个新的顶点w（可以用u或v充当w）代替，并使w关联除e以外u,v关联的所有边，称为收缩边e．(4)设u,vV（u,v可能相邻，也可能不相邻），用G(u,v)（或G+(u,v)）表示在u,v之间加一条边(u,v)，称为加新边．在收缩边和加新边过程中可能产生环和平行边．删除,收缩与加新边19实例v1v2v3v4v5e1e2e3e4e5e6e7Gv1v2v3v4v5e1e2e3e4e6e7G-e5v1v2v3v4v5e2e3e5e6e7G-{e1,e4}v1v2v3v4e3e4e5e6e7G-v5v1v2v3e4e5e7G-{v4,v5}v1v3v4v5e1e2e3e4e6e7G＼e5209.2通路与回路定义9.11设图G=V,E(无向或有向的),G中顶点与边的交替序列=v0e1v1e2…elvl，如果vi1,vi是ei的端点(始点和终点),1il,则称为v0到vl的通路.v0,vl分别称作的始点和终点.中的边数l称作它的长度.又若v0=vl,则称为回路.若所有的边各异,则称为简单通路.又若v0=vl,则称为简单回路.若中所有顶点各异(除v0和vl可能相同外)且所有边也各异,则称为初级通路或路径.若又有v0=vl,则称为初级回路或圈.长度为奇数的圈称为奇圈,长度为偶数的圈称为偶圈.若中有边重复出现,则称为复杂通路.若又有v0=vl,则称为复杂回路.21通路与回路定理9.4在n阶图G中，若从顶点u到v（uv）存在通路，则从u到v存在长度小于或等于n1的通路.推论在n阶图G中，若从顶点u到v（uv）存在通路，则从u到v存在长度小于或等于n1的初级通路（路径）.定理9.5在n阶图G中，若存在v到自身的回路，则一定存在v到自身长度小于或等于n的回路.推论在n阶图G中，若存在v到自身的简单回路，则一定存在v到自身的长度小于或等于n的初级回路.22同构意义下和定义意义下的圈例2无向完全图Kn（n3）中有几种非同构的圈？解长度相同的圈都是同构的.易知Kn(n3)中含长度3,4,…,n的圈，共有n2种非同构的圈．长度相同的圈都是同构的,因此在同构意义下给定长度的圈只有一个.在标定图中,圈表示成顶点和边的标记序列.如果只要两个圈的标记序列不同,称这两个圈在定义意义下不同.例3无向完全图K3的顶点依次标定为a,b,c．在定义意义下K3中有多少个不同的长度为3的圈？解在定义意义下,不同起点(终点)的圈是不同的,顶点间排列顺序不同的圈也是不同的,因而K3中有3!=6个不同的长为3的圈：abca，acba，bacb，bcab，cabc，cbac．23带权图与最短路径定义9.12设图G=V,E(无向图或有向图),对G的每一条边e,给定一个数W(e),称作边e的权.把这样的图称为带权图,记作G=V,E,W.当e=(u,v)(u,v)时,把W(e)记作W(u,v).设P是G中的一条通路,P中所有边的权之和称为P的长度,记作W(P).类似地,可定义回路C的长度W(C).设带权图G=V,E,W(无向图或有向图),其中每一条边e的权W(e)为非负实数.u,vV,当u和v连通(u可达v)时,称从u到v长度最短的路径为从u到v的最短路径,称其长度为从u到v的距离,记作d(u,v).约定:d(u,u)=0;当u和v不连通(u不可达v)时,d(u,v)=+.24最短路问题最短路问题:给定带权图G=V,E,W及顶点u和v,其中每一条边e的权W(e)为非负实数,求从u到v的最短路径.Dijkstra标号法(求从s到其余各点的最短路径和距离)1.令l(s)(s,0),l(v)(s,+)(vV-{s}),i1,l(s)是永久标号,其余标号均为临时标号,us2.for与u关联的临时标号的顶点v3.ifl2(u)+W(u,v)l2(v)then令l(v)(u,l2(u)+W(u,v))4.计算l2(t)=min{l2(v)|vV且有临时标号},l(t)改为永久标号5.ifinthen令ut,ii+1,转2对每一个u,d(s,u)=l2(u),根据l1(v)回溯找到s到u的最短路径.25实例例9.5一个总部和6个工地,求从总部到各工地的最短路径解12345671510364451726总部12345671510364451726(0,S)(+,S)(+,S)(+,S)(+,S)(+,S)(+,S)26实例12345671510364451726(0,S)(15,1)(10,1)(+,S)(+,S)(+,S)(+,S)u=112345671510364451726(0,S)(13,3)(10,1)(+,S)(14,3)(+,S)(+,S)u=327实例12345671510364451726(0,S)(13,3)(10,1)(19,2)(14,3)(30,2)(+,S)u=2123456715103644517