(图论)图的基本概念--第一章

第1章图的基本概念本章内容1图2通路与回路3图的连通性4图的矩阵表示5图的运算1.1图的基本概念图的定义图的一些概念和规定简单图和多重图顶点的度数与握手定理图的同构完全图与正则图子图与补图无序积与多重集合设A，B为任意的两个集合，称{{a,b}|a∈A∧b∈B}为A与B的无序积，记作A&B。可将无序积中的无序对{a,b}记为(a,b)，并且允许a＝b。无论a,b是否相等，均有(a,b)＝(b,a)，因而A&B＝B&A。元素可以重复出现的集合称为多重集合或者多重集，某元素重复出现的次数称为该元素的重复度。例如在多重集合{a,a,b,b,b,c,d}中，a,b,c,d的重复度分别为2,3,1,1。笛卡尔积设A，B为任意的两个集合，称{a,b|a∈A∧b∈B}为A与B的笛卡尔积，记作AXB。笛卡尔积中的是有序对a,b。只有a,b相等的时候才有(a,b)＝(b,a).也只有A=B时才有AXB＝BXA。定义1一个无向图是一个有序的二元组V，E,记作G，其中（1）V≠称为顶点集，其元素称为顶点或结点。（2）E称为边集，它是无序积V&V的多重子集，其元素称为无向边，简称边。定义2一个有向图是一个有序的二元组V，E，记作D，其中（1）V≠称为顶点集，其元素称为顶点或结点。（2）E为边集，它是笛卡儿积V×V的多重子集，其元素称为有向边，简称边。无向图和有向图说明可以用图形表示图，即用小圆圈（或实心点）表示顶点，用顶点之间的连线表示无向边，用有方向的连线表示有向边。例1.1例1.1(1)给定无向图G＝V,E，其中V＝{v1,v2,v3,v4,v5}，E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}.(2)给定有向图D=V,E，其中V＝{a,b,c,d}，E＝{a,a,a,b,a,b,a,d,c,d,d,c,c,b}。画出G与D的图形。图的一些概念和规定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为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记为。标定图与非标定图、基图将图的集合定义转化成图形表示之后，常用ek表示无向边(vi,vj)（或有向边vi,vj），并称顶点或边用字母标定的图为标定图，否则称为非标定图。将有向图各有向边均改成无向边后的无向图称为原来图的基图。易知标定图与非标定图是可以相互转化的;任何无向图G的各边均加上箭头就可以得到以G为基图的有向图。关联与关联次数、环、孤立点设G＝V,E为无向图，ek＝(vi,vj)∈E，称vi,vj为ek的端点，ek与vi或ek与vj是彼此相关联的。若vi≠vj，则称ek与vi或ek与vj的关联次数为1。若vi＝vj，则称ek与vi的关联次数为2，并称ek为环。任意的vl∈V，若vl≠vi且vl≠vj，则称ek与vl的关联次数为0。设D＝V,E为有向图，ek＝vi,vj∈E，称vi,vj为ek的端点。若vi＝vj，则称ek为D中的环。无论在无向图中还是在有向图中，无边关联的顶点均称为孤立点。相邻与邻接设无向图G＝V，E，vi，vj∈V，ek，el∈E。若et∈E，使得et＝(vi，vj)，则称vi与vj是相邻的。若ek与el至少有一个公共端点，则称ek与el是相邻的。设有向图D＝V，E，vi，vj∈V，ek，el∈E。若et∈E，使得et＝vi，vj，则称vi为et的始点，vj为et的终点，并称vi邻接到vj，vj邻接于vi。若ek的终点为el的始点，则称ek与el相邻。邻域设无向图G＝V，E，v∈V，称{u|u∈V∧(u,v)∈E∧u≠v}为v的邻域，记做NG(v)。称NG(v)∪{v}为v的闭邻域，记做NG(v)。称{e|e∈E∧e与v相关联}为v的关联集，记做IG(v)。设有向图D＝V，E，v∈V，称{u|u∈V∧v,u∈E∧u≠v}为v的后继元集，记做Г+D(v)。称{u|u∈V∧u,v∈E∧u≠v}为v的先驱元集，记做Г-D(v)。称Г+D(v)为v的出邻域,Г-D(v)为v的入邻域.Г+D(v)∪Г-D(v)为v的邻域，记做ND(v)。称ND(v)∪{v}为v的闭邻域，记做ND(v)。举例NG(v1)＝Г+D(d)＝{v2，v5}NG(v1)＝{v1，v2，v5}IG(v1)＝{e1，e2，e3}{c}Г-D(d)＝{a，c}ND(d)＝{a，c}ND(d)＝{a，c，d}简单图与多重图定义1.3在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数。在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点和终点相同(也就是它们的方向相同)，则称这些边为平行边。含平行边的图称为多重图。既不含平行边也不含环的图称为简单图。例如：在图1.1中，(a)中e5与e6是平行边，(b)中e2与e3是平行边，但e6与e7不是平行边。(a)和(b)两个图都不是简单图。顶点的度数定义1.4设G＝V,E为一无向图，v∈V，称v作为边的端点次数之和为v的度数，简称为度，记做dG(v)。在不发生混淆时，简记为d(v)。注:某个点上的环要计算2次度数.设D＝V，E为有向图，v∈V，称v作为边的始点次数之和为v的出度，记做d+D(v)，简记作d+(v)。称v作为边的终点次数之和为v的入度，记做d-D(v)，简记作d-(v)。称d+(v)+d-(v)为v的度数，记做d(v)。注:某个点上的有向环要对这个点计算一次入度计算一次出度.图的度数的相关概念在无向图G中，最大度△(G)＝max{d(v)|v∈V(G)}最小度δ(G)＝min{d(v)|v∈V(G)}称度数为1的顶点为悬挂顶点，与它关联的边称为悬挂边。度为偶数(奇数)的顶点称为偶度(奇度)顶点。在有向图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(v1)＝4(注意，环提供2度)，△＝4，δ＝1，v4是悬挂顶点，e7是悬挂边。d+(a)＝4，d-(a)＝1(环e1提供出度1，提供入度1)，d(a)＝4+1＝5。△＝5，δ＝3，△+＝4(在a点达到)δ+＝0(在b点达到)△-＝3(在b点达到)δ-＝1(在a和c点达到)握手定理定理1.1设G＝V,E为任意无向图，V＝{v1,v2,…,vn}，|E|＝m，则n12)(iimvd说明任何无向图中，各顶点度数之和等于边数的两倍。证明G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，当然，m条边，共提供2m度。另外一个更严格的证明：当G是简单图时，否则当,0),(),(,1),(GEvvvvjiji当图G不是简单图时，只要把每一个环与重边上“嵌入”一个新的顶点得到新的图G’，G’是简单图.假设有t个新的顶点,图G’中原来G中的顶点度数不变，而每个新的顶点的度数为2.新图G’的边数比图G的边数多了t条（原因是在环和重边上加入新点后，将原来的一条边变成了两条边）。对G’利用前面的证明结果：两边消去2t,得到结论。握手定理定理1.2设D＝V,E为任意有向图，V＝{v1,v2,…,vn}，|E|＝m，则nnn111)()(,2)(iiiiiimvdvdmvd且握手定理的推论推论任何图(无向的或有向的)中，奇度顶点的个数是偶数。证明设G＝V，E为任意一图，令V1＝{v|v∈V∧d(v)为奇数}V2＝{v|v∈V∧d(v)为偶数}则V1∪V2＝V，V1∩V2＝，由握手定理可知Vvvdm)(221)()(VvVvvdvd由于2m和2)(Vvvd，所以1)(Vvvd为偶数，但因V1中顶点度数为奇数，所以|V1|必为偶数。问题研究问题：在一个部门的25个人中间，由于意见不同，是否可能每个人恰好与其他5个人意见一致？解答：不可能。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不可能的。说明：(1)很多离散问题可以用图模型求解。(2)为了建立一个图模型，需要决定顶点和边分别代表什么。(3)在一个图模型中，边经常代表两个顶点之间的关系。例2：晚会上大家握手言欢，试证握过奇次手的人数是偶数。解答：构造一个图，以参加晚会的人为顶，仅当二人握手时在相应的二顶间加一条边。于是每个人握手的次数为这个图的相应顶点的度数。用握手定理的推论得到结论。例3：空间中不可能有这样的多面体存在，它的面数是奇数，而且每个面是奇数条围成的。解答：如果有这样的多面体存在，以此多面体的面集合为顶点集构造一个图G,当且仅当两个面有公共边界线时在相应的两顶间连一条边，于是|V(G)|是奇数，而且对每个顶点v,d(v)是奇数,则所有的顶点的度数之和为奇数，与握手定理矛盾。度数列设G＝V,E为一个n阶无向图，V＝{v1,v2,…,vn}，称d(v1)，d(v2)，…，d(vn)为G的度数列。对于顶点标定的无向图，它的度数列是唯一的。反之，对于给定的非负整数列d＝{d1,d2,…,dn}，若存在V＝{v1,v2,…,vn}为顶点集的n阶无向图G，使得d(vi)＝di，则称d是可图化的。特别地，若所得图是简单图，则称d是可简单图化的。类似地，设D＝V,E为一个n阶有向图，V＝{v1,v2,…,vn}，称d(v1)，d(v2)，…，d(vn)为D的度数列，另外称d+(v1)，d+(v2)，…，d+(vn)与d-(v1)，d-(v2)，…，d-(vn)分别为D的出度列和入度列。度数列举例按顶点的标定顺序，度数列为4,4,2,1,3。按字母顺序，度数列，出度列，入度列分别为5,3,3,34,0,2,11,3,1,2可图化的充要条件定理1.3设非负整数列d＝(d1，d2，…，dn)，则d是可图化的当且仅当n1)2(mod0iid证明必要性。由握手定理显然得证。充分性。由已知条件可知，d中有偶数个奇数度点。奇数度点两两之间连一边，剩余度用环来实现。5331可图化举例由定理1.3立即可知，(3,3,2,1)，(3,2,2,1,1)等是不可图化的，(3,3,2,2)，(3,2,2,2,1)等是可图化的。定理：若是简单图的次序列，且则是偶数，且对1960年Erdos和Gallai已经证明这也是充分条件。证明：大致思路：对任意的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次）。定理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)可图化，不可简