月日图的基本概念.pptx

1.1 图的基本概念图的定义图的一些概念和规定简单图和多重图顶点的度数与握手定理图的同构完全图与正则图子图与补图第1页/共114页无序积与多重集合 设A，B为任意的两个集合，称a,b|aAbB为A与B的无序积，记作A&B。可将无序积中的无序对a,b记为(a,b)，并且允许ab。无论a,b是否相等，均有(a,b)(b,a)，因而A&BB&A。元素可以重复出现的集合称为多重集合或者多重集，某元素重复出现的次数称为该元素的重复度。例如 在多重集合a,a,b,b,b,c,d中，a,b,c,d的重复度分别为2,3,1,1。第2页/共114页笛卡尔积设A，B为任意的两个集合，称|aAbB为A与B的笛卡尔积，记作AXB。笛卡尔积中的是有序对。只有a,b相等的时候才有(a,b)(b,a).也只有A=B时才有AXBBXA。第3页/共114页定义1 一个无向图是一个有序的二元组,记作G，其中（1）V称为顶点集，其元素称为顶点或结点。（2）E称为边集，它是无序积V&V的多重子集，其元素称为无向边，简称边。定义2 一个有向图是一个有序的二元组，记作D，其中（1）V称为顶点集，其元素称为顶点或结点。（2）E为边集，它是笛卡儿积VV的多重子集，其元素称为有向边，简称边。无向图和有向图说明q可以用图形表示图，即用小圆圈（或实心点）表示顶点，用顶点之间的连线表示无向边，用有方向的连线表示有向边。第4页/共114页例1.1例1.1(1)给定无向图G，其中 Vv1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5).(2)给定有向图D=，其中 Va,b,c,d，E,。画出G与D的图形。第5页/共114页图的一些概念和规定G表示无向图，但有时用G泛指图(无向的或有向的)。D只能表示有向图。V(G)，E(G)分别表示G的顶点集和边集。若|V(G)|n，则称G为n阶图。若|V(G)|与|E(G)|均为有限数，则称G为有限图。若边集E(G)，则称G为零图，此时，又若G为n阶图，则称G为n阶零图，记作Nn，特别地，称N1为平凡图。在图的定义中规定顶点集V为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记为。第6页/共114页标定图与非标定图、基图 将图的集合定义转化成图形表示之后，常用ek表示无向边(vi,vj)（或有向边），并称顶点或边用字母标定的图为标定图，否则称为非标定图。将有向图各有向边均改成无向边后的无向图称为原来图的基图。易知标定图与非标定图是可以相互转化的;任何无向图G的各边均加上箭头就可以得到以G为基图的有向图。第7页/共114页关联与关联次数、环、孤立点 设G为无向图，ek(vi,vj)E，称vi,vj为ek的端点，ek与vi或ek与vj是彼此相关联的。若vivj，则称ek与vi或ek与vj的关联次数为1。若vivj，则称ek与vi的关联次数为2，并称ek为环。任意的vlV，若vlvi且vlvj，则称ek与vl的关联次数为0。设D为有向图，ekE，称vi,vj为ek的端点。若vivj，则称ek为D中的环。无论在无向图中还是在有向图中，无边关联的顶点均称为孤立点。第8页/共114页相邻与邻接 设无向图G，vi，vjV，ek，elE。若etE，使得et(vi，vj)，则称vi与vj是相邻的。若ek与el至少有一个公共端点，则称ek与el是相邻的。设有向图D，vi，vjV，ek，elE。若etE，使得et，则称vi为et的始点，vj为et的终点，并称vi邻接到vj，vj邻接于vi。若ek的终点为el的始点，则称ek与el相邻。第9页/共114页邻域设无向图G，vV，称u|uV(u,v)Euv为v的邻域，记做NG(v)。称NG(v)v为v的闭邻域，记做NG(v)。称e|eEe与v相关联为v的关联集，记做IG(v)。设有向图D，vV，称u|uVEuv为v的后继元集，记做+D(v)。称u|uVEuv为v的先驱元集，记做-D(v)。称+D(v)为v的出邻域,-D(v)为v 的入邻域.+D(v)-D(v)为v的邻域，记做ND(v)。称ND(v)v为v的闭邻域，记做ND(v)。第10页/共114页举例NG(v1)+D(d)v2，v5NG(v1)v1，v2，v5IG(v1)e1，e2，e3 c-D(d)a，cND(d)a，cND(d)a，c，d第11页/共114页简单图与多重图 定义1.3 在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数。在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点和终点相同(也就是它们的方向相同)，则称这些边为平行边。含平行边的图称为多重图。既不含平行边也不含环的图称为简单图。例如：在图1.1中，(a)中e5与e6是平行边，(b)中e2与e3是平行边，但e6与e7不是平行边。(a)和(b)两个图都不是简单图。第12页/共114页顶点的度数定义1.4 设G为一无向图，vV，称v作为边的端点次数之和为v的度数，简称为度，记做 dG(v)。在不发生混淆时，简记为d(v)。注:某个点上的环要计算2次度数.设D为有向图，vV，称v作为边的始点次数之和为v的出度，记做d+D(v)，简记作d+(v)。称v作为边的终点次数之和为v的入度，记做d-D(v)，简记作d-(v)。称d+(v)+d-(v)为v的度数，记做d(v)。注:某个点上的有向环要对这个点计算一次入度计算一次出度.第13页/共114页图的度数的相关概念在无向图G中，最大度(G)maxd(v)|vV(G)最小度(G)mind(v)|vV(G)称度数为1的顶点为悬挂顶点，与它关联的边称为悬挂边。度为偶数(奇数)的顶点称为偶度(奇度)顶点。在有向图D中，最大出度+(D)maxd+(v)|vV(D)最小出度+(D)mind+(v)|vV(D)最大入度-(D)maxd-(v)|vV(D)最小入度-(D)mind-(v)|vV(D)第14页/共114页图的度数举例d(v1)4(注意，环提供2度)，4，1，v4是悬挂顶点，e7是悬挂边。d+(a)4，d-(a)1(环e1提供出度1，提供入度1)，d(a)4+15。5，3，+4(在a点达到)+0(在b点达到)-3(在b点达到)-1(在a和c点达到)第15页/共114页第16页/共114页另外一个更严格的证明：当G是简单图时，第17页/共114页当图G不是简单图时，只要把每一个环与重边上“嵌入”一个新的顶点得到新的图G，G是简单图.假设有t个新的顶点,图G中原来G中的顶点度数不变，而每个新的顶点的度数为2.新图G的边数比图G的边数多了t条（原因是在环和重边上加入新点后，将原来的一条边变成了两条边）。对G利用前面的证明结果：两边消去2t,得到结论。第18页/共114页第19页/共114页握手定理的推论推论任何图(无向的或有向的)中，奇度顶点的个数是偶数。证明设G为任意一图，令V1v|vVd(v)为奇数V2v|vVd(v)为偶数则V1V2V，V1V2，由握手定理可知 由于2m和，所以为偶数，但因V1中顶点度数为奇数，所以|V1|必为偶数。第20页/共114页问题研究问题：在一个部门的25个人中间，由于意见不同，是否可能每个人恰好与其他5个人意见一致？解答：不可能。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不可能的。说明：(1)很多离散问题可以用图模型求解。(2)为了建立一个图模型，需要决定顶点和边分别代表什么。(3)在一个图模型中，边经常代表两个顶点之间的关系。第21页/共114页例2：晚会上大家握手言欢，试证握过奇次手的人数是偶数。解答：构造一个图，以参加晚会的人为顶，仅当二人握手时在相应的二顶间加一条边。于是每个人握手的次数为这个图的相应顶点的度数。用握手定理的推论得到结论。例3：空间中不可能有这样的多面体存在，它的面数是奇数，而且每个面是奇数条围成的。解答：如果有这样的多面体存在，以此多面体的面集合为顶点集构造一个图G,当且仅当两个面有公共边界线时在相应的两顶间连一条边，于是|V(G)|是奇数，而且对每个顶点v,d(v)是奇数,则所有的顶点的度数之和为奇数，与握手定理矛盾。第22页/共114页第23页/共114页度数列举例按顶点的标定顺序，度数列为4,4,2,1,3。按字母顺序，度数列，出度列，入度列分别为5,3,3,34,0,2,11,3,1,2第24页/共114页第25页/共114页可图化举例由定理1.3立即可知，(3,3,2,1)，(3,2,2,1,1)等是不可图化的，(3,3,2,2)，(3,2,2,2,1)等是可图化的。第26页/共114页定理：若 是简单图的次序列，且则 是偶数，且对1960年Erdos和Gallai已经证明这也是充分条件。第27页/共114页证明：大致思路：对任意的k,把图分成两部分：一部分是1到k个点组成的，设为V1，另外的n-K点组成另外一部分,设为V2。我们再来计算1到k点的总的度数之和。这个度数由两部分贡献，一是来自于V1的贡献，最多是V1构成完全图，它们的度数之和为k(k-1),第二部分来自于V2,V2中的每个点给V1的所有点贡献的次数最多是d_i和k之间的最小值（原因是，V2的每个点的度数全部贡献给V1,但V1中的点最多只有k个，只能最多接收k次）。第28页/共114页定理1.4定理1.4 设G为任意n阶无向简单图，则(G)n-1。证明因为G既无平行边也无环，所以G中任何顶点v至多与其余的n-1个顶点均相邻，于是d(v)n-1，由于v的任意性，所以(G)n-1。例1.2 判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？(1)(5,5,4,4,2,1)不可图化。(2)(5,4,3,2,2)可图化，不可简单图化。若它可简单图化，设所得图为G，则(G)max5,4,3,2,25，这与定理1.4矛盾。第29页/共114页第30页/共114页例14.2(5)(4,4,3,3,2,2)可简单图化。下图中两个6阶无向简单图都以(5)中序列为度数列。第31页/共114页第32页/共114页图的同构举例彼得森(Petersen)图第33页/共114页图同构的必要条件：节点数目相等边数相等度数相同的节点数目相等第34页/共114页边图（线图）定义：设G是一个无环图，边图L(G)这样构成：将E(G)中的每条边作为L(G)的顶点集，即 V（L(G)=E(G)，L(G)中的两顶相邻当且仅当它们是G中的两条相邻的边。边图有许多有趣的性质.例如，(1)若uv是G中的边，则在L(G)中uv对应的顶点的度数是 的d(u)+d(v)-2.这是因为：uv对应的顶点的次数是除边uv以外的与u,v相邻的边的条数之和，即(d(u)-1)+(d(v)-1)2)第35页/共114页完全图定义1.6 设G为n阶无向简单图，若G中每个顶点均与其余的n-1个顶点相邻，则称G为n阶无向完全图，简称n阶完全图，记做Kn(n1)。设D为n阶有向简单图，若D中每个顶点都邻接到其余的n-1个顶点，又邻接于其余的n-1个顶点，则称D是n阶有向完全图。设D为n阶有向简单图，若D的基图为n阶无向完全图Kn，则称D是n阶竞赛图。第36页/共114页完全图举例n阶无向完全图的边数为：n(n-1)/2n阶有向完全图的边数为：n(n-1)n阶竞赛图的边数为：n(n-1)/2K53阶有向完全图4阶竞赛图第37页/共114页正则图定义1.7 设G为n阶无向简单图，若vV(G)，均有d(v)k，则称G为k-正则图。举例n阶零图是0-正则图n阶无向完全图是(n-1)-正则图彼得森图是3-正则图说明n阶k-正则图中，边数mkn/2。当k为奇数时，n必为偶数。第38页/共114页第39页/共114页子图设G为一图，V1V且V1，称以V1为顶点集，以G中两个端点都在V1中的边组成边集E1的图为G的V1导出的子图，记作GV1。设E1E且E1，称以E1为边集，以E1中边关联的顶点为顶点集V1的图为G的E1导出的子图，记作GE1。第40页/共114页导出子图举例在上图中，设G为(1)中图所表示，取V1a,b,c，则V1的导出子图GV1为(2)中图所示。取E1e1,e3，则E1的导出子图GE1为(3)中图所示。第41页/共114页定义1.9定义1.9 设G为n阶无向简单图，以V为顶点集，以所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作G。若图GG，则称为G是自补图。(1)为自补图(2)和(3)互为补图第42页/共114页定义1.10定义1.10 设G为无向图。(1)设eE，用G-e表示从G中去掉边e，称为删除e。设E E，用G-E 表示从G中删除E 中所有的边，称为删除E。(2)设vV，用G-v表示从G中去掉v及所关联的一切边，称为删除顶点v。设V V，用G-V 表示从G中删除V 中所有顶点，称为删除V。(3)设边e(u,v)E，用Ge表示从G中删除e后，将e的两个端点u,v用一个新的顶点w(或用u或v充当w)代替，使w关联除e外u,v关联的所有边，称为边e的收缩。(4)设u,vV(u,v可能相邻，也可能不相邻)，用G(u,v)(或G+(u,v)表示在u,v之间加一条边(u,v)，称为加新边。说明在收缩边和加新边过程中可能产生环和平行边。第43页/共114页举例GGe5Ge1,e4Gv5Gv4,v5Ge5第44页/共114页第45页/共114页关于通路与回路的说明在初级通路与初级回路的定义中，仍将初级回路看成初级通路(路径)的特殊情况，只是在应用中初级通路(路径)都是始点与终点不相同的，长为1的圈只能由环生成，长为2的圈只能由平行边生成，因而在简单无向图中，圈的长度至少为?。若中有边重复出现，则称为复杂通路，又若vi0vil，则称为复杂回路。在有向图中，通路、回路及分类的定义与无向图中非常相似，只是要注意有向边方向的一致性。在以上的定义中，将回路定义成通路的特殊情况，即回路也是通路，又初级通路(回路)是简单通路(回路)，但反之不真。第46页/共114页通路和回路的简单表示法(1)只用边的序列表示通路(回路)。定义1.11中的可以表示成ej1,ej2,ejl。(2)在简单图中也可以只用顶点序列表示通路(回路)。定义中的也可以表示成vi0,vi2,vil。(3)为了写出非标定图中的通路(回路)，可以先将非标定图标成标定图，再写出通路与回路。(4)在非简单标定图中，当只用顶点序列表示不出某些通路(回路)时，可在顶点序列中加入一些边(这些边是平行边或环)，可称这种表示法为混合表示法。第47页/共114页第48页/共114页定理1.6推论 在n阶图G中，若从顶点vi到vj（vivj）存在通路，则vi到vj一定存在长度小于或等于n-1的初级通路（路径）。定理1.6 在一个n阶图G中，若存在vi 到自身的回路，则一定存在vi 到自身长度小于或等于n的回路。推论 在一个n阶图G中，若存在vi 到自身的简单回路，则一定存在vi 到自身长度小于或等于n的初级回路。第49页/共114页第50页/共114页例1.5例1.5 无向完全图K3的顶点依次标定为a,b,c。在定义意义下K3中有多少个不同的圈？解答在同构意义下，K3中只有一个长度为3的圈。但在定义意义下，不同起点(终点)的圈是不同的，顶点间排列顺序不同的圈也看成是不同的，因而K3中有6个不同的长为3的圈：abca，acba，bacb，bcab，cabc，cbac如果只考虑起点(终点)的差异，而不考虑顺时针逆时针的差异，应有3种不同的圈，当然它们都是同构的，画出图来只有一个。第51页/共114页1.3 图的连通性无向图的连通性无向图中顶点之间的短程线及距离无向图的连通程度：点割集、割点、边割集、割边、连通度有向图的连通性及判别方法扩大路径法与极大路径二部图及其判别方法 第52页/共114页无向图的连通性定义1.12 设无向图G，u,vV，若u,v之间存在通路，则称u,v是连通的，记作uv。vV，规定vv。第53页/共114页第54页/共114页例：有2k部电话交换台，每台至少与k个台有直通线路，证明任两台之间可以通话。注意：如果直接证明需找出任意两个交换台之间有通路，这是不可能的。因为题目中没有给出具体的结构信息。证明：先把交换台之间的通话关系用图表示出来。把交换台作为图G的一个顶点，仅当两台之间有直通线路时在相应的两点之间连一条边，于是图G有2k个顶点，每顶的次数至少为k.需要证明G是连通图。用反证法：假设G不连通，则至少存在两个连通分支，则存在一个连通分支，其顶点数小于等于k,则在这个连通分支上最大度数不超过k-1,矛盾第55页/共114页例：在仅两个奇次顶的图中，其二奇次顶连通。说明：直接证明此二奇次点之间有路连接是不可能的。故采用反证法。证明：如果图G中恰有两个奇次顶 u,v,但在G中这两个奇次顶 u,v不连通，则存在两个连通分支，每个包含一个奇次点。对于这两个分支而言，皆有1个奇次点，与握手定理的推论矛盾。第56页/共114页无向图中顶点之间的短程线及距离 定义1.15 设u,v为无向图G中任意两个顶点，若uv，称u,v之间长度最短的通路为u,v之间的短程线，短程线的长度称为u,v之间的距离，记作d(u,v)。当u,v不连通时，规定d(u,v)。距离有以下性质：(1)d(u,v)0，uv时，等号成立。(2)具有对称性，d(u,v)d(v,u)。(3)满足三角不等式：u,v,wV(G)，则d(u,v)+d(v,w)d(u,w)说明：在完全图Kn(n2)中，任何两个顶点之间的距离都是1。在n阶零图Nn(n2)中，任何两个顶点之间的距离都为。第57页/共114页如何定义连通度问题：如何定量地比较无向图的连通性的强与弱？点连通度：为了破坏连通性，至少需要删除多少个顶点？边连通度：为了破坏连通性，至少需要删除多少条边？“破坏连通性”是指“变得更加不连通”。第58页/共114页无向图的点割集定义1.16 设无向图G，若存在V V，且V，使得p(G-V)p(G)，而对于任意的V V，均有p(G-V)p(G)，则称V 是G的点割集。若V 是单元集，即V v，则称v为割点。v2,v4,v3,v5都是点割集v3,v5都是割点v1与v6不在任何割集中。实际上，点割集是若删去它们就会使图不连通的顶点的集合，而割点是若删去此一顶点就会使图不连通的顶点。第59页/共114页无向图的边割集定义1.17设无向图G，若存在E E，且E，使得p(G-E)p(G)，而对于任意的E E，均有p(G-E)p(G)，则称E是G的边割集，或简称为割集。若E 是单元集，即E e，则称e为割边或桥。e6,e5,e2,e3,e1,e2,e3,e4,e1,e4,e1,e3,e2,e4都是割集，e6,e5是桥。实际上，边割集是若删去它们就会使图不连通的边的集合，而割边是若删去此一边就会使图不连通的边。第60页/共114页点连通度定义1.18设G为无向连通图且为非完全图，则称 (G)min|V|V 为G的点割集为G的点连通度，简称连通度。说明 连通度是为了产生一个不连通图需要删去的点的最少数目。规定完全图Kn(n1)的点连通度为n-1，规定非连通图的点连通度为0，若(G)k，则称G是k-连通图，k为非负整数。说明(G)有时简记为。上例中图的点连通度为1，此图为1-连通图。K5的点连通度K4，所以K5是1-连通图，2-连通图，3-连通图，4-连通图。若G是k-连通图（k1）则在G中删除任何k-1个顶点后，所得图一定还是连通的。第61页/共114页边连通度定义1.19 设G是无向连通图，称(G)min|E|E 是G的边割集为G的边连通度。规定非连通图的边连通度为0。若(G)r，则称G是r 边-连通图。说明(G)也可以简记为。若G是 r 边-连通图，则在G中任意删除r-1条边后，所得图依然是连通的。完全图Kn的边连通度为n-1，因而Kn是r边-连通图，0rn-1。平凡图G 由于E 则0图14.8中图的边连通度1，它只能是1边-连通图。第62页/共114页例1.6求所示各图的点连通度，边连通度，并指出它们各是几连通图及几边连通图。最后将它们按点连通程度及边连通程度排序。K4K3K2K1K=1=2K2K0K0第63页/共114页第64页/共114页有向图的连通性定义1.20 设D为一个有向图。vi,vjV，若从vi到vj存在通路，则称vi可达vj，记作vivj，规定vi总是可达自身的，即vivi。若vivj且vjvi，则称vi与vj是相互可达的，记作vi vj。规定vivi。说明 与都是V上的二元关系，并且不难看出是V上的等价关系。定义1.21 设D为有向图，vi,vjV，若vivj，称vi到vj长度最短的通路为vi到vj的短程线，短程线的长度为vi到vj的距离，记作d。说明 与无向图中顶点vi与vj之间的距离d(vi,vj)相比，d除无对称性外，具有d(vi,vj)所具有的一切性质。第65页/共114页连通图定义1.22 设D为一个有向图。若D的基图是连通图，则称D是弱连通图，简称为连通图。若vi,vjV，vivj与vjvi至少成立其一，则称D是单向连通图。若均有vi vj，则称D是强连通图。说明 强连通图一定是单向连通图，单向连通图一定是弱连通图。强连通图单向连通图弱连通图第66页/共114页强连通图与单向连通图的判定定理定理1.8 设有向图D，Vv1,v2,vn。D是强连通图当且仅当D中存在经过每个顶点至少一次的回路。证明 充分性显然。下面证明必要性。由D的强连通性可知，vivi+1，i1,2,n-1。设i为vi到vi+1的通路。又因为vnv1，设n为vn到v1的通路，则1,2,n-1,n所围成的回路经过D中每个顶点至少一次。定理1.9 设D是n阶有向图，D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路。第67页/共114页关于连通图的例子：例：简单图G及补图Gc不能都不连通 证明：我们只需要证明：如G不连通的时候，Gc一定连通。设 u,v为Gc中的任意两个不同的点。设G1,G2,.Gm为G的所有的连通分支（m大于等于2）。(1)如u,v不属于G的同一个连通分支，则(u,v)属于Gc中的边，u，v在Gc中连通。(2）如u,v属于G的同一个连通分支，因为G不是连通图，则在这个连通分支以外一定存在另外一个连通分支，任取这个连通的一点w,则（u,w),(w,v)都属于Gc中的边，即，u,v在Gc中连通。第68页/共114页例：如G是连通图，G是G的子图，|V(G)|V(G)|,则G中有不属于G的边e,e的一端属于V(G),另外一端不属于V(G).思路：由于|V(G)|V(G)|,则在G中存在一点u，另外存在一点v不在G中。因为G连通，则这两点在G中有一条路P(u,v)存在。从u出发沿着路P（u，v）前进，遇到第一个不属于G的顶点w,P(u,v)上的一段P(u,w)的最后一条边即为所求的边e.第69页/共114页第70页/共114页关于极大路径的说明由某条路经扩大出的极大路径不唯一。极大路径不一定是图中最长的路径。第71页/共114页“最长路径法”-在图中选最长的路，则最长路的两个起点的所有邻点都在这条路上。利用这个性质来证明。第72页/共114页第73页/共114页一般地：设G为n（n3）阶无向简单图，(G)2，则G中存在至少长度大于或者等于+1的圈。证明：最大路径法设P=u0u1uk是图中任意两点之间的最短路中的最长路。则u0的所有邻点都在P上，否则，P能变成更长的路。设u_j1,u_j2,u_jl 是u0的邻点，且就j1j2=(G),u0u1u_jlu0形成一个圈，圈长至少是+1.第74页/共114页第75页/共114页例题：若G是简单图，每顶的次数不小于3，则G中各圈长的最大公约数是1或者2.证明：用最长路法我们能证明G还有圈i+1,j+1和j-i+2的圈（ji,上一个例题）。反证：假设G中各圈长的最大公约数k2,则i+1,j+1和j-i+2有公因子k,则k可除尽j-i，于是k可除2，矛盾。第76页/共114页二部图定义1.23 设G为一个无向图，若能将V分成V1和V2(V1V2V,V1V2)，使得G中的每条边的两个端点都是一个属于V1，另一个属于V2，则称G为二部图（或称二分图，偶图等），称V1和V2为互补顶点子集。常将二部图G记为。若G是简单二部图，V1中每个顶点均与V2中所有顶点相邻，则称G为完全二部图，记为Kr,s，其中r|V1|，s|V2|。说明n阶零图为二部图。第77页/共114页二部图举例K6的子图K6的子图K3,3K2,3K3,3K2,3第78页/共114页二部图的判定定理定理1.10 一个无向图G是二部图当且仅当G中无奇数长度的圈。证明必要性。设图G是二部图,令Cv0,v1,v2,vk,v0是G的一条回路，其长度为k+1。不失一般性，假设v0V1，由二部图的定义知，v1V2，v2V1。由此可知，v2iV1且v2i+1V2。又因为v0V1，所以vkV2，因而k为奇数，故C的长度为偶数。第79页/共114页二部图的判定定理充分性。不妨设G为连通图，否则可对每个连通分支进行讨论。设v0为G中任意一个顶点，令V1v|vV(G)d(v0,v)为偶数V2v|vV(G)d(v0,v)为奇数易知，V1,V2,V1V2，V1V2V(G)。下面只要证明V1中任意两顶点不相邻,V2中任意两点也不相邻。若存在vi,vjV1相邻，令(vi,vj)e，设v0到vi,vj的短程线分别为i,j，则它们的长度d(v0,vi),d(v0,vj)都是偶数，于是ije中一定含奇圈，这与已知条件矛盾。类似可证，V2中也不存在相邻的顶点，于是G为二部图。第80页/共114页第81页/共114页第82页/共114页第83页/共114页第84页/共114页第85页/共114页第86页/共114页有向图无向图都适用第87页/共114页第88页/共114页第89页/共114页第90页/共114页第91页/共114页第92页/共114页第93页/共114页第94页/共114页1.5 图的运算定义1.28 设G1，G2为两个图。若V1V2，则称G1与G2是不交的。若E1E2，则称G1与G2是边不交的或边不重的。说明：不交的图，必然是边不交的，但反之不真。第95页/共114页图的运算定义1.29 设G1，G2为不含孤立点的两个图（它们同为无向图或同为有向图）。(1)称以E1E2为边集，以E1E2中边关联的顶点组成的集合为顶点集的图为G1与G2的并图，记作G1G2。(2)称以E1-E2为边集，以E1-E2中边关联的顶点组成的集合为顶点集的图为G1与G2的差图，记作G1-G2。(3)称以E1E2为边集，以E1E2中边关联的顶点组成的集合为顶点集的图为G1与G2的交图，记作G1G2。(4)称以E1E2为边集（为集合之间的对称差运算），以E1E2中边关联的顶点组成的集合为顶点集的图为G1与G2的环和，记作G1G2。第96页/共114页定义1.29的说明(1)若G1G2，则G1G2G1G2G1(G2)G1-G2G2-G1G1G2这就是在图的定义中给出空图概念的原因。(2)当G1与G2边不重时，G1G2G1-G2G1G2-G1G2G1G2G1G2(3)图之间环和的定义也可以用并、交、差给出，即G1G2(G1G2)-(G1G2)第97页/共114页最短路算法问题：若干个城市被铁路网连通，任何制定其中的两座城市，试求这两座城市之间的最近的铁路图论模型：城市作为顶点，仅当两城市有一段铁路，中途没有其他火车站的将这两个城市连边，边上赋权。求任意2个点的最短路第98页/共114页Dijkstra算法 Dijkstra算法能求一个顶点到另一顶点最短路径。它是由Dijkstra于1959年提出的。实际它能出始点到其它所有顶点的最短路径。Dijkstra算法是一种标号法：给赋权图的每一个顶点记一个数，称为顶点的标号（临时标号，称T标号，或者固定标号，称为P标号）。T标号表示从始顶点到该标点的最短路长的上界；P标号则是从始顶点到该顶点的最短路长。Dijkstra算法步骤如下：第99页/共114页Dijkstra算法第100页/共114页v1v2v3v4v5v6v7v8v9v10v112817615129341369272149第101页/共114页v1v2v3v4v5v6v7v8v9v10v1128176151293413692721490281第102页/共114页v1v2v3v4v5v6v7v8v9v10v112817615129341369272149028101第103页/共114页v1v2v3v4v5v6v7v8v9v10v1128176151293413692721490831012第104页/共114页v1v2v3v4v5v6v7v8v9v10v11281761512934136927214908610125123第105页/共114页v1v2v3v4v5v6v7v8v9v10v1128176151293413692721490861012141235第106页/共114页v1v2v3v4v5v6v7v8v9v10v1128176151293413692721490710121412356第107页/共114页v1v2v3v4v5v6v7v8v9v10v112817615129341369272149091214123567第108页/共114页v1v2v3v4v5v6v7v8v9v10v11281761512934136927214901214101235679第109页/共114页v1v2v3v4v5v6v7v8v9v10v11281761512934136927214901114123567910第110页/共114页v1v2v3v4v5v6v7v8v9v10v11281761512934136927214901312356791011第111页/共114页v1v2v3v4v5v6v7v8v9v10v11281761512934136927214901235679101113第112页/共114页基本要求理解与图的定义有关的诸多概念，以及它们之间的相互关系。深刻理解握手定理及其推论的内容，并能熟练地应用它们。深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图等概念及其它们的性质和相互关系，并能熟练地应用这些性质和关系。深刻理解通路与回路的定义、相互关系及其分类，掌握通路与回路的各种不同的表示方法。理解无向图的点连通度、边连通度等概念及其之间的关系，并能熟练地求出给定的较为简单的图的点连通度与边连通度。理解有向图连通性的概念及其分类，掌握判断有向连通图类型的方法。第113页/共114页感谢您的观看！第114页/共114页