chap7图与子图.

图论是研究由线连接的点集的理论。图论为任何一个包含二元关系的系统提供了一个直观而严谨的数学模型，在科学技术的多个领域都有着应用。图论产生于18世纪，起源于游戏。近代随着科学技术的发展，特别是电子计算机的应用，用图论来解决离散型的实际问题已显示出极大的优越性。同时，图论本身的理论也取得很大的进展。本篇主要介绍图论的基本概念和定理以及在其他学科的一些应用。2020/1/11离散数学1第二篇图论与组合数学轻松一下下面这些酷炫的手机解锁图案，你会设吗？轻松一下下面这些酷炫的手机解锁图案，你会设吗？轻松一下下面这些酷炫的手机解锁图案，你会设吗？一笔画图：从图的任意一点开始，笔尖不离纸、边不重复地画出该图。若起点与终点相同则为欧拉图（E图）；若不同则为半E图。连通图G若是E图当且仅当G中无奇点；若是半E图当且仅当G中最多有两个奇点。现在知道为什么最后这一个画不出来了吧！组合数学所研究的中心问题与“按照一定的规则来安排一些物件”的数学问题有关，包括存在性问题、计数问题、构造问题、最优化问题等。我国古代就已开始了对组合学的研究，并对一些有趣的组合问题给出了正确的答案.越来越多的学者认为中国是早期组合数学的发源地.本篇主要介绍组合数学中的计数问题，以及解决计数问题的数学工具，如加法法则、乘法法则、容斥原理、递推关系和母函数等.2020/1/11离散数学5第七章图与子图§7.1图的概念图是现实世界中对象相互关联的数学抽象：点表示对象，两点之间的线表示这两点之间的关系(二元关系).说明:1.不关心点所代表的具体对象;2.不关心线的长短曲直;3.只关心点与点之间是否有连线.2020/1/11离散数学6图的定义定义7.1.1一个图G是一个有序三元组G=V，E，,其中:2020/1/11离散数学7(1)V是非空顶点集合；(2)E是边集，E∩V=；(3)是E到{uv|u、v∈V}的映射，称为关联函数。uv=vu，u、v∈V。通常用V(G)、E(G)和G分别表示图G的顶点集、边集和关联函数。一个图可以用平面上的一个图形表示。常将一个图与表示它的图形等同起来。端点：在图G中,若e∈E(G)，(e)=uv,u,v∈V(G)，则称u,v为e的端点。邻接(点)：若e∈E(G)，(e)=uv，则称u,v两点是邻接的，也称边e与u,v两点关联。邻接(边)：若(e1)=uv,(e2)=vw,则称e1与e2邻接.即两条不同的边关联同一个点。环：若(e)=uu,则称e为环。即一条边的两个端点重合。杆：若(e)=uv,u≠v,则称e为杆。即一条边的两个端点不重合。孤立点：不与任何边关联的点。2020/1/11离散数学8(一条边的两个端点。)(有共同端点的两条边)关于点与边的术语图的例子设G=V,E,,其中,V={v1,v2,v3},E={e1,e2,e3,e4,e5}(e1)=v1v3,(e2)=v1v2,(e3)=v1v2,(e4)=v2v3,(e5)=v3v32020/1/11离散数学9v1v3v2e1e2e3e4e5e1与v1,v3关联；v1与v3邻接；e2与e1邻接；e5是环；e4是杆。关于图的术语图G的阶：G的顶点数，称为G的阶。若|V(G)|=n，则称G为n阶图G(p,q)表示有p个顶点，q条边的图。用p(G)和q(G)分别表示图G的顶点数和边数。如果图G的V(G)和E(G)都是有限集，称G为有限图，否则称为无限图。2020/1/11离散数学10定义7.1.2若图G中无环，且任意两个顶点间最多有一条边，则称G为简单图或单图，否则称G为伪图。无环的伪图称为多重图。2020/1/11离散数学11单图与伪图v1v3v2e1e2e3e4e5伪图多重图简单图完全图定义7.1.3如果简单图G的任意两个顶点都邻接，则称G为完全图。P个顶点的完全图记为KP。下面给出了完全图K3，K4和K5：2020/1/11离散数学124阶完全图K45阶完全图K53阶完全图K3Kp中边的数目：|E(Kp)|=C2p=p(p-1)/2二分图定义7.1.4如果图G的顶点集V(G)能够分成两个不相交的非空子集V1和V2，使得G的每条边的两个端点分别在V1和V2中，则称G为二分图。记为G=V1,V2。2020/1/11离散数学13•二分图G的二划分子集V1、V2可能不唯一。•若二分图G=V1,V2中V1的每个顶点与V2的每个顶点都邻接，则称G为完全二分图，记为Km，n，其中，|V1|=m，|V2|=n。显然|E(Km，n)|=m×n。二分图的例子下面是图G及其二分图：2020/1/11离散数学14V1:V2:a1a2b1c1d1b2c2d2a1b1c1d1a2b2c2d2GG的二分图补图定义7.1.5如果简单图G和简单图H满足:(1)V(H)=V(G)=V;(2)对u、v∈V，u≠v，uv∈E(H)，当且仅当uvE(G)，则称H为G的补图，记为H=G。显然G与G互为补图。2020/1/11离散数学15（顶点集相等）（边集互补）两个简单图互为补图的例子：GG两种特殊的图零图:G(p,0)，即无边的图。平凡图:G(1,0)，即只有一个孤立点的图。2020/1/11离散数学16§7.2图的同构图描述客观对象间的关系，几何形状不是重要的。同一个图的图形不是唯一的，其差异可以是很大。比如，下面的三个图在图形上是完全不相同的：2020/1/11离散数学17abcdGadcbHabcdK但是我们不难看出这三个图描述的四个对象之间的关系是相同的，实质上是同一个图。它们也就是同构的图。图同构的定义定义7.2.1设G和H是两个图。如果存在两个双射：V(G)V(H)(顶点集之间的双射)：E(G)E(H)(边集之间的双射)，使得G(e)=uv当且仅当H((e))=(u)(v)，则称G和H是同构的。记为GH。2020/1/11离散数学18如果V(G)=V(H)，E(G)=E(H)且G=H，则称G和H是相等的，记为G=H。(在下)对应边的端点是(在下)对应的：显然G=H，则G≌H，反之不然。思考：G=H和GH的关系是怎样的呢？关于图的同构的定义的讨论由定义知：1、若G≌H，则|V(G)|=|V(H)|且|E(G)|=|E(H)|，但反之不然。2、若存在双射:V(G)→V(H)和:E(G)→E(H)，但不一定有G≌H。原因是关联函数的问题。例如：2020/1/11离散数学19u1u2u4u3v1v2v3v4GH:ui→vi,i=1,2,3,4:ei→ai,i=1,2,3,4H((e2))≠v2v4e1e2e3e4a1a2a3a4图同构的例子对于下图，令(ui)=vi，(ei)=ai，1≤i≤5。则和是满足定义7.2.1的两个双射，故GH。2020/1/11离散数学20u1u5u2u3u4v1v4v3v5v2e1e2e3e4e5a1a2a3a4a5G：H：≌（但G≠H）图的等价类显然，同构关系是一个等价关系。所以可以将所有的p阶图的集合按图的同构关系划分成等价类。例如，3阶图的等价类有如下四种：2020/1/11离散数学21无标记图：在每个等价类中任选一个图，去掉顶点和边的名称，作为该类的代表。这种图称为无标记图。上面这四个图就是无标记图。§7.3顶点的度定义7.3.1设G是一个图，v∈V(G)，G中与v关联的边的数目称为v在G中的度数，简称为v的度，记为dG(v)或d(v)。即：d(v)=|{e∈E(G)|e与v关联}|约定，顶点v上的一条环视为与v关联的两条边。2020/1/11离散数学22图的几种顶点。在一个图中：度为奇数的顶点称为奇点；度为偶数的顶点称为偶点；度为1的顶点称为悬挂点；度为0的顶点称为孤立点。例正则图将一个图的各顶点度数中的最大值和最小值分别记为(G)和(G),分别称为G最大度和最小度。即：最大度：(G)=max{d(v)|v∈V(G)}最小度：(G)=min{d(v)|v∈V(G)}一个简单图中，如果(G)=(G)=k,则称G为k-正则图。正则图中各顶点的度都为k。显然，p阶完全图Kp必是一个(p-1)-正则图，2020/1/11离散数学23例但反之不然。例思考：那反过来呢？正则图必是完全图吗？顶点的度数之和为偶数定理7.3.1对任何一个图G(p,q)，有2020/1/11离散数学24piiqVd12)(即一个图的所有顶点的度数之和为边数二倍。此定理很容易证明，因为在计算顶点的度时，每一条边都被计算了两次，也只被计算了两次。轻松一下玩个游戏：同学你好！很高兴认识你！图的奇点个数必为偶数推论7.3.1任何一个图的奇点个数必为偶数。2020/1/11离散数学26任何一群人中，与奇数个人握过手的人必定为偶数。由定理7.3.1可得出如下的推论：假设图中奇点个数为奇数，则它们的度数之和为奇数，偶点的度数之和是偶数，这样所有顶点的度数之和为奇数。与定理7.3.1矛盾。§7.4子图及图的运算定义7.4.1设G和H是两个图，如果V(H)V(G)且E(H)E(G)，则称H是G的子图。记为H≤G。如果H≤G，而H≠G，则称H是G的真子图，记为HG。如果H≤G，且V(H)=V(G)，则称H是G的生成子图。2020/1/11离散数学27即包含了全部顶点的子图。子图的例子观察下面各图：2020/1/11离散数学28v1v3v2v4e1e2e3e4e5e6Ge1v1v3v2e2e3H1v4v2v3e6H2v1v2v3v4e1e2e3e4H3G为母图H1和H2为G的真子图H3是G的生成子图H1、H2和H3是从G中删去一些点或边得到的真子图。几个约定从图中删去一个顶点，必须同时删去所有与该顶点关联的边；从图中删去一条边，则只要删去其两个端点之间的连线，而保留这两个端点。2020/1/11离散数学29V’V(G)，G－V’表示G中删去V’中的顶点后所得的子图；G－{v}简记为G－v，v∈V(G)。E’E(G)，G－E’表示G中删去E’中的边后所得的子图。G－{e}简记为G－e，e∈E(G)（删点边全去）（删边去两点）点导出子图说白了，图G的一个点导出子图，就是由G的一些顶点(顶点集V的一个子集)和G中所有关联这些顶点的边所构成的子图。2020/1/11离散数学30定义7.4.2(1)：设G是一个图，HG。如果e∈E(H)当且仅当存在u、v∈V(H)，使得G(e)=uv，则称H是G的由V(H)导出的子图，记为G[V(H)]。(取其两端点必取其边)点导出子图的例子观察下面各图：2020/1/11离散数学31v1v3v2v4e1e2e3e4e5e6e1v1v3v2e2e3H1Ge1v1v3v2e2H2H1=G[{v1,v2,v3}];但是,图中的H2≠G[{v1,v2,v3}]，因为缺了关联v2，v3的边e3。边导出子图定义7.4.2(2)设G是一个图，HG。如果u∈V(H)当且仅当u是E(H)中某一条边的一个端点，则称H是G的由E(H)导出的子图，记为G[E(H)]。2020/1/11离散数学32(有顶点必有边关联)(点导出子图：取其两端点必取其边)说白了，图G的边导出子图就是G的一些边和这些边的端点所构成的子图。边导出子图中不会有孤立点，也不会是零图；但是点导出子图却可以含有孤立点，甚至是一个零图。边导出子图的例子请观察下图：2020/1/11离散数学33v1v3v2v4e1e2e3e4e5e6Gv1v3v4e1e2e3e4H3v2显然H3=G[{e1,e2,e3e4}]但H3G[{v1,v2,v3,v4}]。关于导出子图G的点或边导出子图必是G的子图，但G的子图却不一定是G的点或边导出子图。2020/1/11离散数学34G–V´=G[V–V´]，V=V(G)，V´V。不一定有G–E´=G[E–E´]，E´E因为，删去顶点同时也删去其关联边。因为，删去了边，却会留下顶点。如图：例GH1H2令E´为蓝色的边的集合，则：H1=G–E´,H2=