离散数学-图论基础

第七章图论基础Graphs2020年1月19日星期日第一节图的基本概念一个图G定义为一个三元组：G=V,E,ΦV——非空有限集合，V中的元素称为结点(node)或顶点(vertex)E——有限集合（可以为空），E中的元素称为边(edge)Φ——从E到V的有序对或无序对的关联映射(associativemapping)v1v2v3(a)v1v2v3(b)v1v2v3(c)2020年1月19日星期日图的基本概念图G=V,E,Φ中的每条边都与图中的无序对或有序对联系若边eE与无序对结点[va,vb]相联系，即Φ(e)=[va,vb]（va,vbV）则称e是无向边（或边、棱）若边eE与有序对结点va,vb相联系，即Φ(e)=va,vb（va,vbV）则称e是有向边（或弧）va是e的起始结点，vb是e的终结点v1v2v3(a)v1v2v3(b)v1v2v3(c)2020年1月19日星期日图的基本概念若va和vb与边（弧）e相联结，则称va和vb是e的端结点va和vb是邻接结点，记作：vaadjvb(adjoin)也称e关联va和vb，或称va和vb关联e若va和vb不与任何边（弧）相联结，则称va和vb是非邻接结点，记作：vanadjvb关联同一个结点的两条边（弧），称为邻接边（弧）关联同一个结点及其自身的边，称为环(cycle)，环的方向没有意义v1v2v3(a)v1v2v3(b)v1v2v3(c)2020年1月19日星期日图的基本概念若将图G中的每条边（弧）都看作联结两个结点则G简记为：V,E每条边都是弧的图，称为有向图(directedgraph)（如图b）每条边都是无向边的图，称为无向图(undirectedgraph)（如图a）有些边是弧，有些边是无向边的图，称为混合图（如图c）v1v2v3(a)v1v2v3(b)v1v2v3(c)2020年1月19日星期日图的基本概念若图G中的任意两个结点之间不多于一条无向边（或不多于一条同向弧），且任何结点无环，则称G为简单图（如图c）若图G中某两个结点之间多于一条无向边（或多于一条同向弧），则称G为多重图（如图a,b）两个结点间的多条边（同向弧）称为平行边（弧），平行边（弧）的条数，称为重数v1v2v3(a)v1v2v3(b)v1v2v3(c)2020年1月19日星期日图的基本概念在多重图的表示中，可在边（弧）上标注正整数，以表示平行边（弧）的重数把重数作为分配给边（弧）上的数，称为权(weight)将权的概念一般化，使其不一定是正整数，则得到加权图的概念：给每条边（弧）都赋予权的图，叫做加权图(weightedgraph)记作G=V,E,W，W是各边权之和v1v2v3(a)v1v2v3(b)v1v2v3(c)11111122112020年1月19日星期日图的基本概念在无向图G=V,E中，V中的每个结点都与其余的所有结点邻接，即(va)(vb)(va,vbV[va,vb]E)，如图(a)则称该图为无向完全图(completegraph)，记作K|V|若|V|=n，则|E|=C=n(n-1)/2v1v2v3(a)v1v2v3(b)2n2020年1月19日星期日图的基本概念在有向图G=V,E中，V中的任意两个结点间都有方向相反的两条弧，即(va)(vb)(va,vbVva,vbE∧vb,vaE)，如图(a)则称该图为有向完全图，记作K|V|若|V|=n，则|E|=P=n(n-1)v1v2v3(a)v1v2v3(b)2n2020年1月19日星期日图的基本概念在图G=V,E中，若有一个结点不与其他任何结点邻接则该结点称为孤立结点，如图(a)中的v4仅有孤立结点的图，称为零图，零图的E=，如图(b)仅有一个孤立结点的图，称为平凡图(trivialgraph)，如图(c)v1v2v3(a)v1v2v3(b)v1(c)v42020年1月19日星期日问题问题1：是否存在这种情况：25个人中，由于意见不同，每个人恰好与其他5个人意见一致？问题2：是否存在这种情况：2个或以上的人群中，至少有2个人在此人群中的朋友数一样多？2020年1月19日星期日结点的次数二、结点的次数定义：在有向图G=V,E中，对任意结点vV以v为起始结点的弧的条数，称为出度(out-degree)（引出次数），记为d+(v)以v为终结点的弧的条数，称为入度(in-degree)（引入次数），记为d-(v)v的出度和入度的和，称为v的度数(degree)（次数），记为d(v)=d+(v)+d-(v)v1v2v3(a)2020年1月19日星期日结点的次数定义：在无向图G=V,E中，对任意结点vV结点v的度数d(v)，等于联结它的边数若结点v上有环，则该结点因环而增加度数2记G的最大度数为：(G)=max{d(v)|vV}记G的最小度数为：(G)=min{d(v)|vV}v1v2v3(a)v1v2v3(b)v42020年1月19日星期日结点的次数在图G中的任意一条边eE，都对其联结的结点贡献度数2定理：在无向图G=V,E中，d(v)=2|E|通常，将度数为奇数的结点称为奇度结点将度数为偶数的结点称为偶度结点定理：在无向图G=V,E中，奇度结点的个数为偶数个2020年1月19日星期日结点的次数问题1：是否存在这种情况：25个人中，由于意见不同，每个人恰好与其他5个人意见一致？在建立一个图模型时，一个基本问题是决定这个图是什么——什么是结点？什么是边？在这个问题里，我们用结点表示对象——人；边通常表示两个结点间的关系——表示2个人意见一致。也就是说，意见一致的2个人（结点）间存在一条边。2020年1月19日星期日结点的次数问题1：是否存在这种情况：25个人中，由于意见不同，每个人恰好与其他5个人意见一致？这样我们可以知道，如果存在题目所述情况，那么每个结点都与其他5个结点相关联。也就是说，每个结点的度为5。由定理可知：奇度结点的个数为偶数个。现在是否能够得出结论了？2020年1月19日星期日结点的次数类似问题：1.晚会上大家握手言欢，握过奇数次手的人数一定是偶数2.碳氢化合物中，氢原子个数是偶数3.是否有这样的多面体，它有奇数个面，每个面有奇数条棱？2020年1月19日星期日结点的次数问题2：是否存在这种情况：两个人或以上的人群中，至少有两个人在此人群中的朋友数一样多？以人为结点，仅当二人为朋友时，在此二人之间连一边，得一“友谊图”G(V,E)，设V={v1,v2,…,vn}，不妨设各结点的次数为d(v1)≤d(v2)≤…≤d(vn)≤n-1。假设命题不成立，则所有人的朋友数都不一样多，则0≤d(v1)d(v2)…d(vn)≤n-1。2020年1月19日星期日结点的次数问题2：是否存在这种情况：两个人或以上的人群中，至少有两个人在此人群中的朋友数一样多？若0≤d(v1)d(v2)…d(vn)≤n-1，则有：由于d(v1)≥0，则有d(v2)≥1，d(v3)≥2，…，d(vn)≥n-1；又因为d(vn)≤n-1，所以：d(vn)=n-1因为d(vn)=n-1，则每个结点皆与vn相邻，则d(v1)≥1。于是有：d(v2)≥2，d(v3)≥3，…，d(vn)≥n，矛盾。故假设不成立，即d(v1)d(v2)…d(vn)中至少有一个等号成立，命题成立。2020年1月19日星期日结点的次数定义：在无向图G=V,E中，若每个结点的度数都是k，即(v)(vVd(v)=k)，则称G为k度正则图(regulargraph)v1v2v6v33度正则图v4v5v7v8v9v103度正则图v1v5v6v2v3v42020年1月19日星期日子图三、子图定义：给定无向图G1=V1,E1，G2=V2,E2若V2V1，E2E1，则称G2是G1的子图(subgraph)，记作G2G1若V2V1，E2E1，且E2≠E1，则称G2是G1的真子图，记作G2G1若V2=V1，E2E1，则称G2是G1的生成子图(spanningsubgraph)，记作G2G1V2=V12020年1月19日星期日子图例如：v2v1(a)v3v4v5(a)的真子图v2v3v4v5(a)的生成子图v2v3v4v5v12020年1月19日星期日子图定义：对于图G=V,E，G1=V,E=G，G2=V,G1和G2都是G的生成子图，称为平凡生成子图定义：设G2=V2,E2是G1=V1,E1的子图对任意结点u,vV2，若有[u,v]E1，则有[u,v]E2，则G2由V2唯一地确定，则称G2是V2的诱导子图记作G[V2]，或G2=V2若G2中无孤立结点，且由E2唯一地确定，则称G2是E2的诱导子图，记作G[E2]，或G2=E22020年1月19日星期日子图例如：v2v1G=V,Ev3v4v5G’=V’,E’V’或E’的诱导子图v2v3v4v52020年1月19日星期日补图定义：设G1=V1,E1和G2=V2,E2是G=V,E的子图，若E2=E-E1，且G2是E2的诱导子图，即G2=E2则称G2是相对于G的G1的补图2020年1月19日星期日补图图G1和G2互为相对于G补图G1v2v1v3v4v5G2v2v3v4v5Gv2v1v3v4v52020年1月19日星期日补图定义：给定图G1=V,E1，若存在图G2=V,E2且E1E2=，及图V,E1E2是完全图则称G2是相对于完全图的G1的补图，记作G2=G12020年1月19日星期日补图G2=G1v2v1G1v3v4v5v2v1K5v3v4v5G2v2v3v4v5v12020年1月19日星期日图的同构四、图的同构定义：给定图G1=V1,E1，G2=V2,E2若存在双射函数f:V1V2，使得对于任意u,vV1有[u,v]E1[f(u),f(v)]E2（或u,vE1f(u),f(v)E2）则称G1与G2同构(isomorphic)，记作G1G22020年1月19日星期日图的同构例7.1.1证明下面两个图G1=V1,E1，G2=V2,E2同构证明：V1={v1,v2,v3,v4},V2={a,b,c,d}构造双射函数f:V1V2，f(v1)=a，f(v2)=bf(v3)=c，f(v4)=d可知，边[v1,v2],[v2,v3],[v3,v4],[v4,v1]被分别映射成[a,b],[b,c],[c,d],[d,a]，故G1G2v2v1G1v3v4badcG22020年1月19日星期日图的同构例7.1.2证明下面两个有向图是同构的。G1eabcd证明：如图所示，G1=V1,E1，G2=V2,E2，结点编号如图所示。构造函数f:V1V2，使得f(a)=1,f(b)=3,f(c)=4,f(d)=5,f(e)=2则a,e,b,a,b,c,c,e,d,a,d,c,e,b,e,d被分别映射成1,2,3,1,3,4,4,2,5,1,5,4,2,3,2,5故f是双射函数，所以G1与G2同构G1312452020年1月19日星期日图的同构可以给出图的同构的必要条件：结点数相等边数相等度数相等的结点数相等要注意的是，这不是充分条件2020年1月19日星期日图的同构例7.1.3证明下面两个无向图是不同构的G1v1v2v3v4v5v6v7v8G2abcdefghv1是3度结点，故f(v1)只能是c或d或g或h。若f(v1)=c，由于v2、v4和v5与v1邻接，因此f(v2)、f(v4)和f(v5)应当分别为与c邻接的b、d和g。但是，v2、v4和v5中，只有一个3度结点，而b、d、g中却有2个3度结点，故f(v1)≠c。同理可说明，f(v1)也不可能是d、g和h。因此这样的f是不存在的。因此G1和G2是不同构的。2020年1月19日星期