图概念

1第四篇图论2图论图论是一门古老的学科，有200多年的历史Euler是图论之父，他用图论的方法解决了哥尼斯褒七桥问题哥尼斯褒七桥问题普鲁士的哥尼斯堡镇（现名加里宁格勒，属于俄罗斯共和国）被普雷格尔河支流分成4部分：河两岸、河中心岛、两条支流之间的部分。在18世纪有7座桥连接这4部分。镇上的人们在周日里穿过镇子进行长距离的散步。他们想弄明白是否可能从镇里某个位置出发不重复地经过所有桥并且返回出发点。3例计算机网络拓扑图，用图为计算机网络建模4(K.C.Claffy)5TelecommNetworks(电信网络)(StephenG.Eick)6引入•实体和实体之间的关系是现实世界的两个基本要素。图论（GraphTheory，GT）有效地刻画了实体与实体之间的关系，是研究现实世界的有力数学工具，在算法理论、人工智能、软件理论和软件工程、计算机网络等计算机科学的不同分支中均有重要应用。7第七章图论图论是近年来发展迅速而又应用广泛的一门学科。本章主要讲授图论的基本概念和定理。重点是欧拉图与汉密尔顿图、平面图、树。要求：熟练掌握图的基本概念和定理并能够进行简单应用。学习《图论》这一章的要求一、学习目的与要求本章主要讲授图论的基本概念和主要定义、定理。通过本章的学习，使学生了解图的基本概念、基本理论和应用范围，为学习“软件工程”、“编译原理”、“数据结构”和“人工智能”等课程打下数学基础。二、知识点1．图的基本概念、结点度数与边数的关系公式；2.路、迹、回路、通路、连通图与非连通图、强连通图与弱连通图、有向图与无向图；强分图、弱分图、点割集、边割集；3.图的矩阵表示：邻接矩阵、可达性矩阵、关联矩阵、关联矩阵的秩与结点数的关系式。4.欧拉路、欧拉回路、欧拉图；汉密尔顿回路、汉密尔顿图；5.平面图、欧拉定理、平面图中结点数和边数之间的关系不等式；Kuratowski定理；6.对偶图与着色问题、四色假设及其验证。7.树、子树、生成树、带权树、最优树；8.根树、完全m叉树、二叉树、完全二叉树中分支点和通路长度之间的关系式。三、要求1．识记图的结点数、分支数、结点的入度、出度，图的连通性：强连通、弱连通，根据图的矩阵表示确定图的性质、根据图的图形表示确定图的性质。根据结点度数的奇偶性确定回路的存在性。识别平面图，识别对偶图；树、子树、生成树、带权树。2．领会点连通度、边连通度和最小度数三者之间的关系，欧拉定理、平面图中结点数和边数之间的关系不等式；Kuratowski定理；最小生成树的计算、最优树的计算。3．简单应用计算机鼓轮的设计，比赛场次安排问题，着色问题等。12学时教学内容27-1图的基本概念27-2路与回路27-3图的矩阵表示27-4欧拉图与汉密尔顿图27-5平面图7-6对偶图与着色37-7树与生成树7-8根树及其应用第七章学时安排（13学时，共6.5讲）7-1图的基本概念本节要熟悉下列概念（26个）：图、无向边、有向边、起始结点、终止结点、无向图、有向图、混合图、邻接点、邻接边、孤立结点、零图、平凡图、结点的度数、图的最大度与最小度、结点的入度、结点的出度、平行边、简单图、完全图、补图、子图、生成子图、子图的相对于图的补图、图的同构多重图、一、图的定义1、定义7-1.1图（graph）G由一个三元组V(G),E(G),G表示，其中：非空集合V(G)={v1,v2,…,vr}称为图G的结点集，其成员vi(i=1,2,…,r)称为结点或顶点（nodesorvertices）；集合E(G)={e1,e2,…,es}称为图G的边集，其成员ej(j=1,2,…s)称为边(edges)。函数G：E(G)→(V(G),V(G))，称为边与顶点的关联映射（associatvemapping）例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)abcde1e2e3e4e5e6若把图中的边ej看作总是和两个结点关联，那么一个图亦简记为G=V,E，其中非空集合V称为图G的结点集，集合E称为图G的边集。例2：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)一个图与结点、连接结点的边、边与结点的关联有关。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、图的分类：①无向图：每条边均为无向边的图称为无向图。②有向图：每条边均为有向边的图称为有向图。③混合图：有些边是无向边，有些边是有向边的图称为混合图。V1’v1v4v5v1v2v3v4V2’V3’V4’(a)无向图(b)有向图(c)混合图(孤立点)v2v3环1、G1=V1，E1是无向图，其中V1={v1，v2，v3，v4，v5，v6}，E1={e1，e2，e3，e4，e5，e6，e7}，e1=(v1，v3)，e2=(v1，v4)，e3=(v2，v4)，e4=(v3，v4)，e5=(v3，v6)，e6=(v4，v5)，e7=(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}练习：画出下面的图。4、点和边的关联：如ei=(u，v)或ei=u，v称u，v与ei关联。5、点与点的相邻：关联于同一条边的结点称为邻接点。6、边与边的邻接：关联于同一结点的边称为邻接边。7、孤立结点：不与任何结点相邻接的结点称为孤立结点。8、零图：仅有孤立结点的图。9、平凡图：仅由一个孤立结点构成的图。10、自回路(环)：关联于同一结点的边称为自回路，或称为环。见274页图7-1.3(c,c)是环2211、平行边：在有向图中，始点和终点均相同的边称为平行边，无向图中若两点间有多条边，称这些边为平行边，两点间平行边的条数称为边的重数。二、点的度数1、点的度数的定义定义7-1.2：在图G=V，E，vV，与结点v关联的边数称为该点的度数，记为deg(v)。孤立结点的度数为0。2、出度与入度定义7-1.3：在有向图中，vV，以v为始点的边数称为该结点的出度，记作deg+(v);以v为终点的边数称为该结点的入度，记作deg-(v)。显然有deg(v)=deg+(v)+deg-(v)如：G1是无向图，deg(v1)=3，deg(v2)=1G2是有向图，deg+(v1)=2，deg-(v1)=3，deg(v1)=5v1v2G1v1v3v4v2G23、最大度和最小度：图G最大度记为(G)=max{deg(v)|vV(G)}，最小度数记为(G)=min{deg(v)|vV(G)}。4、定理7-1.1：每个图中，结点度数总和等于边数的两倍。即deg(v)=2|E|vV该定理又称握手定理证明因为每条边必关联两个结点，而一条边给予关联的每个结点的度数为1。因此在每个图中，结点度数总和等于边数的两倍。5、定理7-1.2在任何图中,度数为奇数的结点必定是偶数个。证明设G中奇数度结点集合为V1,偶数度结点集合为V2，则有：deg(v)+deg(v)=deg(v)=2|E|vV1vV2vV由于deg(v)是偶数之和必为偶数，而2|E|是偶数，vV2故得deg(v)是偶数，而各个deg(vi)(viV1)是奇数，vV1这就要求偶数个deg(vi)求和，即|V1|是偶数。6、定理7-1.3：在任何有向图中，所有结点的入度之和等于所有结点的出度之和。证明因为每一条有向边必对应一个入度和一个出度，若一个结点具有一个入度或出度，则必关联一条有向边，所以有向图中，各结点入度之和等于边数，各结点出度之和也等于边数。因此，在任何有向图中，所有结点的入度之和等于所有结点的出度之和。28练习题设图G=（V，E），|V|=8，若G有3个度为3的结点，2个度为2的结点，其余的结点度数为1，问G有多少条边？解：deg(v)=2|E|=3*3+2*2+1*（8-3-2）=16所以|E|=8三、特殊的图1、多重图定义7-1.4：含有平行边的图称为多重图。2、简单图：不含平行边和环的图称为简单图。3、完全图定义7-1.5：简单图G=V，E中，若每一对结点间均有边相连，则称该图为完全图。有n个结点的无向完全图记为Kn。无向完全图：每一条边都是无向边不含有平行边和环每一对结点间都有边相连定义2：无向完全图G中作何结点都与其余的n-1的结点相连，则称G为无向完全图。30下图分别给出了一个结点、二个结点、三个结点、四个结点和五个结点的无向完全图。定理7-1.4在任何图中,n个结点的无向完全图Kn的边数为n(n-1)/2。证明n个结点中任取两个结点的组合数为Cn2=n(n-1)/2故的边数为|E|=n(n-1)/232如果在Kn中，对每一条边任意确定一个方向，则称该图为n个结点的有向完全图。显然它的边数也为n(n-1)/2。练习：279页(1)课后习题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]=n(n-1)2–∑2(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))25、相对于完全图的补图定义7-1.6：给定一个简单图G，由G中所有结点和所有能使G成为完全图的添加边组成的图，称为G的相对于完全图的补图，或简称为G的补图，记为。即G=V，E1，=V，E2，其中E2={(u，v)u，vV，(u，v)E1}。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全图K5(b)图G(c)图G的补图练习279页（2）GGG6、子图定义7-1.7：设图G=V，E，如果有图G’=V’，E’，且E’E，V’V，则称G’为G的子图。当V’=V时，则称G’为G的生成子图。例如，图(b)的G和图(c)的G’都是图(a)的K5的子图。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全图K5(b)图G(c)图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、同构定义7-1.9：设图G=V，E及图G’=V’，E’，如果存在一一对应的映射g：vivi’且e=(vi，vj)(或vi，vj)是G的一条边，当且仅当e’=(g(