图的基本概念-无向图及有向图

离散数学CH7图的基本概念1无向图及有向图1图论的起源图论是组合数学的一个分支,它起源于1736年欧拉的第一篇关于图论的论文，这篇论文解决了著名的“哥尼斯堡七桥问题”，从而使欧拉成为图论的创始人。哥尼斯堡七桥问题解决方式莱昂哈德·欧拉（LeonhardEuler）在1735年圆满地解决了这一问题，证明这种方法并不存在，也顺带解决了一笔画问题。他在圣彼得堡科学院发表了图论史上第一篇重要文献。欧拉把实际的抽象问题简化为平面上的点与线组合，每一座桥视为一条线，桥所连接的地区视为点。这样若从某点出发后最后再回到这点，则这一点的线数必须是偶数。→→图论的起源欧拉最后给出任意一种河──桥图能否全部走一次的判定法则。如果通奇数座桥的地方不止两个，那么满足要求的路线便不存在了。如果只有两个地方通奇数座桥，则可从其中任何一地出发找到所要求的路线。若没有一个地方通奇数座桥，则从任何一地出发，所求的路线都能实现，他还说明了怎样快速找到所要求的路线。不少数学家都尝试去解析这个事例。而这些解析，最后发展成为了数学中的图论。5欧拉图定义一个图,如果能够从一点出发,经过每条边一次且仅一次再回到起点,则称为欧拉图欧拉在论文中给出并证明了判断欧拉图的充分必要条件定理,并证明了七桥图不是欧拉图。从这个问题可以看出：图：图用点代表各个事物,用边代表各个事物间的二元关系。所以，图是研究集合上的二元关系的工具，是建立数学模型的一个重要手段。2、一百多年以后“七桥”问题以后，图论的研究停滞了一百多年，直到1847年，基尔霍夫用“树”图解决了电路理论中的求解联立方程的问题，十年后凯莱用“树”图计算有机化学中的问题。在这一时期流行着两个著名的图论问题：哈密尔顿回路问题和“四色猜想”问题。3.哈密尔顿回路问题1856年,英国数学家哈密尔顿设计了一个周游世界的游戏，他在一个正十二面体的二十个顶点上标上二十个著名城市的名字，要求游戏者从一个城市出发，经过每一个城市一次且仅一次，然后回到出发点。哈密尔顿回路图此路线称为：哈密尔顿回路，而此图称为：哈密尔顿图。4、“四色猜想”问题人们在长期为地图(平面图)上色时发现，最少只要四种颜色，就能使得有相邻国界的国家涂上不同的颜色四色猜想的证明一直没有解决，直到一百多年后，在计算机出现以后，于1976年用计算机算了1200多小时，才证明了四色猜想问题。5、又过了半个世纪四色猜想问题出现后，图论的研究又停滞了半个世纪，直到1920年科尼格写了许多关于图论方面的论文，并于1936年发表了第一本关于图论的书。此后图论从理论上到应用上都有了很大发展。特别是计算机的出现使图论得到飞跃的发展。学好图论十分重要图论是组合数学的一个分支，与其它数学分支如群论、矩阵论、集合论、概率论、拓扑学、数值分析等有着密切的联系。图论给含有二元关系的系统提供了数学模型，因而在许多领域里都具有越来越重要的地位，并且在物理、化学、信息学、运筹学等各方面都取得了丰硕的成果。从二十世际50年代以来，由于计算机的迅速发展，有力地推动了图论的发展，使得图论成为数学领域里发展最快的分支之一。第7章图的概念本章学习：1.无向图及有向图2.通路、回路、图的连通性3.图的矩阵表示4.最短路径及关键路径14今日内容无向图及有向图图的一些相关概念度握手定理子图相关概念图同构15预备知识有序积:A×B={x,y|x∈A∈y∈B}有序对:x,y≠y,x无序积:A&B={(x,y)|x∈A∈y∈B}无序对:(x,y)=(y,x)多重集:{a,a,a,b,b,c}≠{a,b,c}重复度:a的重复度为3,b的为2,c的为1161、无序积：A&B设A、B为两集合，称{{a,b}|a∈A∧b∈B}为A与B的无序积，记作A&B。为方便起见，将无序对{a,b}记作(a,b)。(a,b)＝(b,a)例：设A={a,b},B={c,d},则A&B＝？A&A＝？A&B={(a,c),(a,d),(b,c),(b,d)}A&A={(a,a),(a,b),(b,b)}172、无向图一个无向图G是一个二元组V,E,即G=V,E,其中:①.V是一个非空集合,称为G的顶点集,V中元素称为顶点或结点;②.E是无序积V&V的一个多重子集,称E为G的边集,E中元素称为无向边或简称边。•用小圆圈表示V中顶点,若(a,b)∈E,就在a,b之间连线段表示边(a,b),其中顶点的位置、连线的曲直及是否相交都无关紧要。18无向图示例给定无向图G＝V,E，其中V＝{v1,v2,v3,v4,v5}，E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}.3、有向图一个有向图D是一个二元组V,E,即D=V,E,其中：①.V同无向图中的顶点集;②.E是笛卡儿积的多重子集,其元素称为有向边,也简称边.20有向图示例给定有向图D=V,E，其中V＝{a,b,c,d}，E＝{a,a,a,b,a,b,a,d,c,d,d,c,c,b}。图的一些概念和规定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相邻。例：点边之间的关联次数27例：点点、边边之间的相邻关系28顶点的度数定义设G＝V,E为一无向图，v∈V，称v作为边的端点次数之和为v的度数，简称为度，记做dG(v)。在不发生混淆时，简记为d(v)。设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)。d(v1)=4d(v2)=4d(v3)=3d(v4)=1d(v5)=030d+(v1)=2d+(v2)=1d+(v3)=3d+(v4)=1d+(v5)=1d-(v1)=1d-(v2)=3d-(v3)=0d-(v4)=3d-(v5)=1d(v1)=3d(v2)=4d(v3)=3d(v4)=4d(v5)=231最大(出/入)度,最小(出/入)度在无向图G中，最大度:Δ(G)=max{dG(v)|v∈V(G)}最小度:δ(G)=min{dG(v)|v∈V(G)}在有向图D中，最大出度:Δ+(D)=max{dD+(v)|v∈V(D)}最小出度:δ+(D)=min{dD+(v)|v∈V(D)}最大入度:Δ-(D)=max{dD-(v)|v∈V(D)}最小入度:δ-(D)=min{dD-(v)|v∈V(D)}简记为Δ,δ,Δ+,δ+,Δ-,δ-32握手定理（图论基本定理）定理7.1设图G=V,E为无向图或有向图，V={v1,v2,…,vn},,|E|=m，则说明任何无向图中，各顶点度数之和等于边数的两倍。证明G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，当然，m条边，共提供2m度。推论：任何图中，度为奇数的顶点个数为偶数。12niidvm33问题研究问题：在一个部门的25个人中间，由于意见不同，是否可能每个人恰好与其他5个人意见一致？解答：不可能。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不可能的。说明：(1)很多离散问题可以用图模型求解。(2)为了建立一个图模型，需要决定顶点和边分别代表什么。(3)在一个图模型中，边经常代表两个顶点之间的关系。握手定理定理7.2设有向图D=V,E，V={v1,v2,…,vn},,|E|=m，则11nniiiidvdvm35度数列设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,3出度列：4,0,2,1入度列：1,3,1,2(4，4，3，1，0)(3，4，3，4，2)练习：39可图化的充要条件定理设非负整数列d＝(d1，d2，…，dn)，则d是可图化的当且仅当n1)2(mod0iid证明必要性。由握手定理显然得证。充分性。由已知条件可知，d中有偶数个奇数度点。奇数度点两两之间连一边，剩余度用环来实现。5331例7.1：1.(3,3,2,3),(5,2,3,1,4)能成为图的度数序列吗？为什么？2.已知图G中有10条边，4个3度顶点，其余顶点的度数均小于等于2，问G中至少有多少个顶点？为什么？解：1.由于这两个序列中，奇数度顶点个数均为奇数，由握手定理的推论可知，它们都不能成为图的度数序列。2.显然，图G中的其余顶点度数均为2时G图的顶点数最少.设G图至少有x个顶点.由握手定理可知，3×4+2×(x-4)=2×10解得:x=8所以G至少有8个顶点。41简单图与多重图定义在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数。在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点和终点相同(也就是它们的方向相同)，则称这些边为平行边。含平行边的图称为多重图。既不含平行边也不含环的图称为简单图。43简单图与多重图示例完全图定义7.7设G为n阶无向简单图，若G中每个顶点均与其余的n-1个顶点相邻，则称G为n阶无向完全图，简称n阶完全图，记做Kn(n≥1)。