第七章图论

1第七章图论图论是近年来发展迅速而又应用广泛的一门学科。本章主要讲授图论的基本概念和定理。重点是欧拉图与汉密尔顿图、平面图、树。要求：熟练掌握图的基本概念和定理并能够进行简单应用。7-1图的基本概念（2学时）7-2链(或路)与圈(或回路)（2学时）7-3图的矩阵表示（2学时）7-4欧拉图与汉密尔顿图（2学时）7-5平面图（2学时）7-4对偶图与着色（2学时）7-7树与生成树（2学时）7-8根树及其应用（4学时）7-1图的基本概念什么是图?可用一句话概括，即：图是用点和线来刻划离散事物集合中的每对事物间以某种方式相联系的数学模型。因为它显得太抽象，不便于理解，2所以有必要给出另外的回答。下面便是把图作为代数结构的一个定义。一、图的定义1、图的定义定义7-1.1：一个图是一个三元组V(G)，E(G)，G，其中V(G)={v1，v2，…，vn}为有限非空结点集合，vi称为结点，E(G)={e1，…，em}为有限的边集合，ei称为边，G是从边集合E到结点对集合上的函数。图可简记为：G=V，E。例1：G=V(G)，E(G)，G其中V(G)={a，b，c，d}，E(G)={e1，e2，e3，e4，e5，e6}，G(e1)=(a，b)，G(e2)=(a，c)，G(e3)=(b，d)，G(e4)=(b，c)，G(e5)=(d，c)，G(e6)=(a，d)例1：G=V(G)，E(G)，Gabcde2e3e4e5e63其中V(G)={a，b，c，d}，E(G)={e1，e2，e3，e4，e5，e6}，G(e1)=(a，b)，G(e2)=(a，c)，G(e3)=(b，d)，G(e4)=(b，c)，G(e5)=(d，c)，G(e6)=(a，d)由定义可知，图G中的每条边都与图中的无序或有序结点对相联系的。2、无向边：如果E中边ei对应V中的结点对是无序的(u，v)称ei是无向边，记ei=(u，v)，称u，v是ei的两个端点。有向边：如果ei与结点有序对u，v相对应，称ei是有向边，记ei=u，v，称u为ei的始点，v为ei的终点。3、图的分类：①无向图：每条边均为无向边的图称为无向图。②有向图：每条边均为有向边的图称为有向图。③混合图：有些边是无向边，有些边是有向边的图称4为混合图。见273页图7-1.2(a)是无向图(b)是有向图(c)是混合图练习：画出下面的图。（1）G1=V1，E1是无向图，其中V1={V1，V2，V3，V4，V5，V6}，E1={e1，e2，e3，e4，e5，e6}，e1=(V1，V3)，e2=(V1，V4)，e2=(V2，V4)，e3=(V3，V4)，e4=(V3，V6)，e5=(V4，V5)，e6=(V5，V6)（2）G2=V2，E2是有向图，其中V2={V1，V2，V3，V4}，E={V3，V1，V3，V2，V1，V1，V1，V2，V4，V1，V3，V4，V4，V3}（3）G3=V3，e3是混合图，V3={V1，V2，V3，V4}，E3={V1，V1，(V1，V3)，V3，V1，V1，V2，(V4，V2)}4、点和边的关联：如ei=(u，v)或ei=u，v称u，v与ei关联。5、点与点的相邻：关联于同一条边的结点称为邻接5点。6、边与边的邻接：关联于同一结点的边称为邻接边。7、孤立结点：不与任何结点相邻接的结点称为孤立结点。8、零图：仅有孤立结点的图。9、平凡图：仅有一个孤立结点的图。10、自回路(环)：关联于同一结点的边称为自回路，或称为环。见274页图7-1.3(c,c)是环11、平行边：在有向图中，始点和终点均相同的边称为平行边，无向图中若两点间有多条边，称这些边为平行边，两点间平行边的条数称为边的重数。见274页图7-1.4二、点的度数1、点的度数的定义定义7-1.2：在图G=V，E，vV，与结点v关联的边数称为该点的度数，记为deg(v)。孤立结点的度数为0。2、出度与入度定义7-1.3：在有向图中，vV，以v为始点的边数6称为该结点的出度，记作deg+(v);以v为终点的边数称为该结点的入度，记作deg-(v)。显然有deg(v)=deg+(v)+deg-(v)如：G1是无向图，deg(v1)=3，deg(v2)=1G2是有向图，deg+(v1)=3，deg-(v1)=2，deg(v1)=5，3、最大度和最小度：图G最大度记为(G)=max{deg(v)|vV(G)}，最小度数记为(G)=min{deg(v)|vV(G)}。4、定理7-1.1：每个图中，结点度数总和等于边数的两倍。即deg(v)=2|E|该定理又称握手定理证明因为每条边必关联两个结点，而一条边给予关联的每个结点的度数为1。因此在每个图中，结点度v1v2v1v3v4v2G1G27数总和等于边数的两倍。5、定理7-1.2：在任何图中，度数为奇数的结点的个数必为偶数。6、定理7-1.3：在任何有向图中，所有结点的入度之和等于所有结点的出度之和。证明因为每一条有向边必对应一个入度和一个出度，若一个结点具有一个入度或出度，则必关联一条有向边，所以有向图中，各结点入度之和等于边数，各结点出度之和也等于边数。因此，在任何有向图中，所有结点的入度之和等于所有结点的出度之和。三、特殊的图1、多重图定义7-1.4：含有平行边的图称为多重图。2、简单图：不含平行边和环的图称为简单图。3、完全图定义7-1.5：简单图G=V，E中，若每一对结点间均有边相连，则称该图为完全图。有n个结点的无向完全图记为Kn。无向完全图：每一条边都是无向边，不含有平行边和8环，每一对结点间都有边相连4、定理7-1.4：n个结点的无向完全图Kn的边数为n(n-1)/2。如果在Kn中，对每一条边任意确定一个方向，则称该图为n个结点的有向完全图。显然它的边数为n(n-1)/2。练习：279页(1)证明在任何有向完全图中，所有结点入度的平方之和等于所有结点的出度平方之和。证明设有向完全图有n个结点。对于任意结点vi均有deg+(vi)+deg-(vi)=n-1（1）而有向完全图的边数为n(n-1)/2，由定理7-1.1有∑deg+(vi)+∑deg-(vi)=n(n-1)由定理7-1.3有∑deg+(vi)=∑deg-(vi)所以∑deg+(vi)=∑deg-(vi)=n(n-1)/2（2）由（1）有(deg+(vi))2=(n-1-deg-(vi))2因此∑(deg+(vi))2=∑(n-1-deg-(vi))2=∑[(n-1)2-2(n-1)deg-(vi)+(deg-(vi))2]9∑(deg+(vi))2=∑(n-1-deg-(vi))2=∑[(n-1)2-2(n-1)deg-(vi)+(deg-(vi))2]=n(n-1)2–2n(n-1)∑deg-(vi)+∑(deg-(vi))2=n(n-1)2–2(n-1)∑deg-(vi)+∑(deg-(vi))2由（2）有∑deg-(vi)=n(n-1)/2代入上式即得∑(deg+(vi))2=∑(deg-(vi))26、子图定义7-1.7：设图G=V，E，如果有图G’=V’，E’，且E’E，V’V，则称G’为G的子图。当V’=V时，则称G’为G的生成子图。7、相对于图G的补图定义7-1.8：设G’=V’，E’是G=V，E的子图，若给定另一个图G”=V”，E”使得E”=E-E’，且V”中仅包含E”的边所关联的结点，则称G”是子图G’相对于图G的补图。见图7-1.7图(c)是图(b)相对于图(a)的补图。8、同构10在图的定义中，强调的是结点集、边集以及边与结点的关联关系，既没有涉及到联结两个结点的边的长度、形状和位置，也没有给出结点的位置或者规定任何次序。因此，对于给定的两个图，在它们的图形表示中，即在用小圆圈表示结点和用直线或曲线表示联结两个结点的边的图解中，看起来很不一样，但实际上却是表示同一个图。因而，引入两图的同构概念便是十分必要的了。定义7-1.9：设图G=V，E及图G’=V’，E’，如果存在一一对应的映射g：vivi’且e=(vi，vj)(或vi，vj)是G的一条边，当且仅当e’=(g(vi)，g(vj))(或g(vi)，g(vj))是G’的一条边，则称G与G’同构，记作G≌G’。由同构的定义可知，不仅结点之间要具有一一对应关系，而且要求这种对应关系保持结点间的邻接关系。对于有向图的同构还要求保持边的方向。显然，两图的同构是相互的，即G1同构于G2，G2同构于G1。两图同构的一些必要条件：111.结点数目相同；2.边数相等；3.度数相同的结点数目相等。以上几个条件不是两个图同构的充分条件。见279页图7-1.10同构必须是结点和边分别存在一一对应。练习279页（3）对应结点度数不同，所以两图不同构。寻找一种简单有效的方法来判定图的同构，至今仍是图论中悬而未决的重要课题。作业279页（4）(5)280页（6）127-2路与回路在无向图(或有向图)的研究中，常常考虑从一个结点出发，沿着一些边(或弧)连续移动而达到另一个指定结点，这种依次由结点和边(或弧)组成的序列，便形成了链(或路)的概念。学习本节要熟悉如下概念(23个)：路、路的长度、回路、迹、通路、圈、连通、连通分支、点割集、割点、点连通度、边割集、割边、边连通度、可达性、节点之间的距离、图的直径、单侧连通、强连通、弱连通、强分图、单侧分图、弱分图。掌握5个定理，一个推论。一、路1、定义7-2.1：给定图G＝V，E，设v0，v1，…，vnV，e1，e2，…，emE，其中ei是关联于结点vi-1，vi的边，交替序列v0e1v1e2…envn称为联结v0到vn的路。v0和vn分别称作路的起点和终点，边的数目n称作路的长度。当v0=vn时，这条路称作回路。若一条路中所有的边e1，e2，…，em均不相同，称13作迹。若一条路中所有的结点v0，v1，…，vn均不相同，则称作通路。闭的通路，即除v0=vn外，其余的结点均不相同的路，就称作圈。例如路：v1e2v3e3v2e3v3e4v2e6v5e7v3迹：v5e8v4e5v2e6v5e7v3e4v2通路：v4e8v5e6v2e1v1e2v3圈：v2e1v1e2v3e7v5e6v2在简单图中一条路v0e1v1e2…envn，由它的结点序列v0，v1，…，vn确定，所以简单图的路，可由其14结点序列表示。在有向图中，结点数大于一的—条路亦可由边序列e1e2…en表示。2、定理7-2.1：在一个具有n个结点的图中，如果从结点vj到vk存在一条路，则从结点vj到vk存在一条不多于n-1条边的路。3、推论：在一个具有n个结点的图中，若从结点vj到vk存在一条路，则必存在一条从vj到vk而边数小于n的通路。定理7-2.1的证明如果从结点vj到vk存在一条路，该路上的结点序列是vj…vi…vk，如果在这条中有l条边，则序列中必有l+1个结点，若ln-1，则必有结点vs，它在序列中不止出现一次，即必有结点序列vj…vs…vs…vk，在路中去掉从vs到vs的这些边，仍是vj到vk的一条路，但此路比原来的路边数要少，如此重复进行下去，必可得到一条从vj到vk的不多于n-1条边的路。15如在图7-2.1中有5个结点。v1到v3的一条路为：v1e2v3e3v2e3v3e4v2e6v5e7v3此路中有6条边，去掉e3有路v1e2v3e4v2e6v5e7v3有4条边。v1到v3最短的路为v1e2v3二、无向图的连通性：1、连通定义7-2.2：在无向图G中，结点u和v之间若存在16一条路，则称结点u和结点v是连通的。不难证明，结点之间连通性是结点集V上的等价关系，因此对应这个等价关系，必可对结点集V作出一个划分，把V分成非空子集V1，V2，…，Vm，使得两个结点vj和vk是连通的，当且仅当它们属手同一个Vi。我们把子图G(V1)，…，G(Vm)称为图G的连通分支(图)，今