《苏友无密码课件图的基本概念》由会员分享，可在线阅读，更多相关《苏友无密码课件图的基本概念（58页珍藏版）》请在金锄头文库上搜索。
1、第四部分 图论,图论是研究由线连接的点集的理论, 它起源于18世纪. 1736年欧拉(Euler)研究了著名的哥尼斯堡七桥问题. 由此开创了一个新的数学分支图论. 在19世纪和20世纪的前半期, 图论主要研究一些游戏问题, 诸如迷宫问题、博弈问题和棋盘上马的行走路线问题等. 1847年, 基尔霍夫(Kirchhoff)应用图论的方法来分析电网络, 奠定了现代网络理论的基础. 1936年, 哥尼格发表了第一本图论专著, 从此, 图论成为一门独立的学科.,北京林业大学信息学院 苏喜友,1,第四部分 图论,图论的应用范围很广, 它不但能应用于自然科学, 也能应用于社会科学. 例如, 它可应用于电信网
2、络、电力网络、运输能力、开关理论、编码理论、控制论、反馈理论、随机过程、可靠性理论、化学化合物的辨认、计算机的程序设计、故障诊断、人工智能、印刷电路板设计、图案识别、地图着色、情报检索, 还可应用于语言学、社会结构、经济学、运筹学、兵站学、遗传学等方面.,北京林业大学信息学院 苏喜友,2,Chap.7 图的基本概念,1 无向图和有向图 2 通路、回路、图的连通性 3 图的矩阵表示,北京林业大学信息学院 苏喜友,3,1 无向图和有向图,一、图的定义 Def.1 设A是一个非空集合, x,yA, 称x,y为A上的无序偶(对), 记作(x,y). 如, (a,c),(c,a),(a,b),(a,a)
3、都是集合a,b,c上的无序偶, 且(a,c)=(c,a).Def.2 无向图G(Graph)是一有序对V,E, 即 G=V,E, 其中V是非空集合, E是V上的无序对的多重集合, 分别称V和E是无向图G的顶点集和边集. V中元素称为顶点或结点, E中元素称为无向边或简称为边.,北京林业大学信息学院 苏喜友,4,1 无向图和有向图,Def.3 有向图D是一有序对V,E, 即D=V,E,其中V是非空集合, E是V上的有序对的多重集合, 分别称V和E是有向图D的顶点集和边集. V中元素称为顶点或结点, E中元素称为有向边或简称为边(或弧). 一般情况下, 图均以图形形式表示. 如,北京林业大学信息学
4、院 苏喜友,5,1 无向图和有向图,术语与说明：(1)当不需要区分无向图和有向图时, 我们统称为图, 用G表示. G既可表示无向图, 也可表示有向图, 但D只能表示有向图.(2)V(G), E(G)分别表示图G的顶点集和边集. V(G)和E(G)都是有限集的图, 称为有限图, 否则称为无限图. 本课程只讨论有限图.(3)一个有n个顶点和m条边的图称为(n,m)图或n阶图.(4)若E(G)=, 称G为零图. 只有一个顶点的图称为平凡图.,北京林业大学信息学院 苏喜友,6,1 无向图和有向图,(5)设ek=(vi,vj)(或ek=vi,vj), 则称vi和vj是邻接的 (或相邻的), vi和vj是
5、边ek的端点, ek与vi(或vj)彼此 相关联.若vi=vj, 则称ek与vi(或vj)的关联次数为2, 若 vivj, 则称ek与vi(或vj)的关联次数为1, 若ek与vi不 关联, 则称ek与vi的关联次数为0.关联同一顶点的两条边称为相邻的.无边关联的顶点称为孤立点.对于有向边ek=vi,vj, 称vi是ek始点, vj是ek的终 点, ek关联于vi, ek关联到vj, vi邻接到vj, vj邻接于vi.,北京林业大学信息学院 苏喜友,7,1 无向图和有向图,(6)如果一条边的两个端点重合, 则称这条边为自回路或自环(环). 关联于同一对顶点的边若多于一条(对于有向图, 边的方向相
6、同), 则称这些边为平行边. 平行边的条数称为重数.(7)含有平行边的图称为多重图. 不含平行边的图, 即非多重图称为线图. 不含平行边和环的图, 即无环的线图称为简单图.,北京林业大学信息学院 苏喜友,8,1 无向图和有向图,二、顶点的度数 Def.4 (1)设G=V,E是无向图, vV, v作为边的端点的次数称为v的度数, 简称为度, 记作d(v).(2)设D=V,E是有向图, vV, v作为边的始点的次数称为v的出度, 记作d+(v), v作为边的终点的次数称为v的入度, 记作d-(v); v的出度和入度之和称为v的度数, 记作d(v), 即d(v)=d+(v)+d-(v).(3)度数为
7、1的顶点称为悬挂点, 悬挂点所关联的边称为悬挂边.,北京林业大学信息学院 苏喜友,9,1 无向图和有向图,称(G)=maxd(v)|vV), (G)=mind(v)|vV分别为图G的最大度数和最小度数. 称+(D)=maxd+(v)|vV)为有向图D的最大出度; +(D)=mind+(v)|vV)为有向图D的最小出度; -(D)=maxd-(v)|vV)为有向图D的最大入度; -(D)=mind-(v)|vV)为有向图D的最小入度.,北京林业大学信息学院 苏喜友,10,1 无向图和有向图,Th.1(握手定理) 设G=V,E是具有顶点集V=v1,v2,vn的(n,m)图, 则证.图中任何一条边均
8、有两个端点, 在计算各顶点 度数时, 每条边提供2度, 则m条边提供2m度.,北京林业大学信息学院 苏喜友,11,1 无向图和有向图,推论 在任何图中, 度数为奇数的顶点的个数为偶数.证.设V1=v|vV且d(v)为奇数, V2=v|vV且 d(v)为偶数.显然, V1V2=, V1V2=V. 由握手定理, 有d(v)=d(v)+d(v)=2m, 因d(v)和2m为偶数, 所以d(v)也必定为偶数, 而偶数个奇数才能为偶数, 故|V1|为偶数.,vV,vV1,vV2,vV2,vV1,北京林业大学信息学院 苏喜友,12,1 无向图和有向图,Th.2 设有向图D=V,E, V=v1,v2,vn,
9、|E|=m,则证.在有向图D中, 每条边均有一个始点和一个终点,即每条边各提供一个出度和一个入度, 故m条边共提供m个出度和m个入度.设G=V,E, V=v1,v2,vn, 称(d(v1),d(v2),d(vn)为G的顶点度数序列, 简称为G的度数列.,北京林业大学信息学院 苏喜友,13,1 无向图和有向图,Exp.1 判断下列4组数能否构成无向简单图的度数列, 为什么?(1)1,2,3,4. (2)2,2,2,3.(3)1,3,3,3. (4)2,2,4,4,5,5. 解.(1)不能. 因4个顶点的无向简单图中不可能有4度顶点.(2)不能. 因奇度顶点个数为奇数.(3)不能. 虽然满足握手定
10、理的推论和每个顶点度数均小于4, 但它有一个悬挂点, 因而其余三个顶点的度数不可能都为3, 至多有一个顶点的度数为3, 否则它不是无向简单图. 如右图.,北京林业大学信息学院 苏喜友,14,1 无向图和有向图,(4)2,2,4,4,5,5. 不能. 因虽然满足握手定理的推论和每个顶点的度数均小于图的顶点数6, 但它有2个2度顶点和2个5度顶点, 这意味着2个5度顶点与其余每个顶点均相邻, 2个2度顶点除了与这2个5度顶点分别邻接外, 不可能再与其它顶点邻接, 因此余下的2个顶点最多为3度顶点,否则它不是无向简单图. 如下图.,北京林业大学信息学院 苏喜友,15,1 无向图和有向图,Exp.2
11、已知图G中有1个1度顶点, 2个2度顶点, 3个3度顶点, 4个4度顶点, 问G中有多少条边? 解.设G中有m条边, 由握手定理知,2m=11223344=30, 所以, m=15. 即G中有15条边.,北京林业大学信息学院 苏喜友,16,1 无向图和有向图,三、补图与子图 Def.5 (1)设G=V,E是n阶无向简单图, 若G中每一个顶点都与其余n-1个顶点邻接, 则称G为n阶无向完全图, 记作Kn.(2)设D=V,E是n阶有向简单图, 若任意一对不同的顶点之间都有一对方向相反的边与这两顶点关联, 则称D为n阶有向完全图.,K3,K4,K5,3阶有向完全图,北京林业大学信息学院 苏喜友,17
12、,1 无向图和有向图,由定义, n阶无向完全图的边数 n阶有向完全图的边数Def.6 所有顶点的度数均为某个自然数k的无向简单图称为k正则图. 由定义, n阶无向完全图Kn为n-1正则图, 而正则图不一定是完全图. 如下图所示.右图为2正则图, 但不是完全图.,北京林业大学信息学院 苏喜友,18,1 无向图和有向图,Def.7 设G=V,E是n阶无向简单图, 以V为顶点集, 以使G成为完全图Kn的所有添加边组成的集合为边集的图, 称为G的相对于kn的补图, 简称为G的补图, 记作G. 有向简单图的补图可类似定义.(a)(b)互为补图, (c)(d)互为补图.,北京林业大学信息学院 苏喜友,19
13、,1 无向图和有向图,Def.8 设有两个图G=V,E和G=V,E.(1)若VV且EE, 则称G是G的子图, G是G的母图, 记作GG.(2)若GG, 且VV或EE, 则称G是G的真子图, 记作GG.(3)若GG, 且V=V, 则称G是G的生成子图.(4)若GG, 且V, E为E中两个端点均属于V的边的集合, 则称G为G的由V导出的子图,简称为图G的导出子图.(5)若GG, 且E, V为E中的边关联的顶点的集合, 则称G为G的由E导出的子图.,北京林业大学信息学院 苏喜友,20,1 无向图和有向图,例如,G,G1,G2都是G的子图, G1,G2是G的真子图. G,G2是G的生成子图. G1是V
14、1=v1,v2,v4,v5,v6导出的子图, 也是由E1=e1,e4,e5,e6,e7,e9导出的子图. G2是由E2=e1,e2,e3,e4,e5,e6导出的子图, 但不是V2=v1,v2,v3,v4,v5,v6导出的子图.,北京林业大学信息学院 苏喜友,21,1 无向图和有向图,四、图的同构 Def.9 设有两个图G=V,E和G=V,E, 若存在双射函数f:VV, 使得对任意的e=(vi,vj)E (或vi,vjE)当且仅当e=(f(vi),f(vj)E(或f(vi),f(vj)E), 且e与e重数相同, 则称G与G同构, 记作G G.到目前为止, 还没有找到判断两个图是否同构的简便方法,
15、 只能根据定义对给定的图进行判断.,北京林业大学信息学院 苏喜友,22,1 无向图和有向图,例如,(1)(2)同构, (3)(4)同构.,北京林业大学信息学院 苏喜友,23,1 无向图和有向图,对于同构, 形象地说, 若图的顶点可以任意挪动位置, 而边是完全弹性的, 只要在不拉断边的条件下, 这个图可以变形为另一个图, 那么这两个图就是同构的.所以, 对于两个直观看上去完全不同的两个图,但如果它们同构, 则总能由一个图变形为另一个图.,北京林业大学信息学院 苏喜友,24,1 无向图和有向图,例如,(1)与(2)同构, (1)可变形为(2).,(3)与(4)同构, (3)可变形为(4).,北京林
16、业大学信息学院 苏喜友,25,1 无向图和有向图,两个图同构的必要条件:(1)顶点数相同, |V|=|V|;(2)边数相同, |E|=|E|;(3)度数相同的顶点数相同.利用必要条件可以判断两个图不同构.图的同构关系具有自反性、对称性和传递性,所以, 图的同构关系是一种等价关系.,北京林业大学信息学院 苏喜友,26,1 无向图和有向图,Exp.3 (1)画出4阶3条边的所有非同构的无向简单图.(2)画出5阶3条边的所有非同构的无向简单图.(3)画出3阶2条边的所有非同构的有向简单图. 解.对于同构的无向图G与G, 可调整一个图的顶点次序, 使G与G有相同的度数列. 所以如两个图度数列不同, 则它们是不同构的. 故求非同构的图, 只要找出所有互不相同的度数列即可.,
