第五章图的基本概念 图论起源于1736年欧拉(Ener)的第一篇 图论论文,解决了“哥尼斯堡的七桥问 题”。在哥尼斯堡的匹格河上有七座桥, 如图所示。 A B c 77
第五章 图的基本概念 • 图论起源于1736年欧拉(Enler)的第一篇 图论 论文, 解决了“哥尼斯堡的七桥问 题” 。在哥尼斯堡的匹格河上有七座桥, 如图所示
很显然,通过哥尼斯堡 七座桥中每一座一次 自且仅一次的问题等价 B C于在图53(b)中找 条闭链, 使得它的每一边出现 D 次且仅一次,也就是 (b)1如何一笔画的问题。 后来称此问题为哥尼斯堡七桥问题。 在图a中,用边表示桥顶点表示岛屿和河的 两岸便得到一个图,如图b所示
• 当时人们热衷于这样的游戏：设想从任一 个地方出发通过每座桥一次且仅一次后回 到原地, 这是否可能?但多次实践都发现不 行 • 1727 年欧拉的朋友向欧拉提出了这个问题 是否有解？ • 1736 年欧拉用图论的方法解决了这个问题, 写了第一篇图论的论文,成为图论的创始人。 • 后来称此问题为哥尼斯堡七桥问题。 • 在图a中,用边表示桥,顶点表示岛屿和河的 两岸,便得到一个图,如图b所示。 很显然,通过哥尼斯堡 七座桥中每一座一次 且仅一次的问题等价 于在图5.13 (b)中找一 条闭链, 使得它的每一边出现 一次且仅一次, 也就是 如何一笔画的问题
但在此之后100年间,没有大的进展。 直到 Kirchhof(克希霍夫)用树的理论解决了电网络问题, 1857年 Cayley(凯莱)用统计不同构树的方法来计算 CnH2m+同分异构体数目, 这些结果引起了人们的重视,图论的研究进入了一个发展 时期, 在此期间,出现了两个著名的问题:四色问题和 Hamilton 回路问题成为不少数学家的研究目标。 但在19世纪后期和二十世纪初,图论的研究再次处于停 顿状态。 直到1920年,科尼格( Konig攥写了许多图论方面的论文, 在1936年科尼格(Kong发表了第一本图论书籍《有限图 与无限图理论》,总结了200年来图论研究的主要成果
• 但在此之后100年间，没有大的进展。 • 直到Kirchhoff(克希霍夫)用树的理论解决了电网络问题， • 1 8 5 7年 Cayler(凯莱 )用统计不同构树的方法来计算 CnH2n+1同分异构体数目, • 这些结果引起了人们的重视,图论的研究进入了一个发展 时期, • 在此期间,出现了两个著名的问题:四色问题和Hamilton 回路问题,成为不少数学家的研究目标。 • 但在19世纪后期和二十世纪初，图论的研究再次处于停 顿状态。 • 直到1920年,科尼格(Konig)攥写了许多图论方面的论文, • 在1936 年科尼格(Konig)发表了第一本图论书籍《有限图 与无限图理论》，总结了200年来图论研究的主要成果
此后的50年,图论经历了一场爆炸性的发展, 成为数学科学中一门独立的学科。 主要分支有图论、超图理论、极值图论、算法 图论、网络图论和随机图论等。 几十年来图论在理论上和应用上都得到很大的 发展,特别是在近30多年来由于计算机的广泛应 用而又得到飞跃的发展。 在计算机科学、运筹学、化学、物理和社会科 学等方面都取得了不少成果,对计算机学科中 的操作系统研究、编译技术、人工智能和计算 机网络等方面都有广泛的应用。 这里主要讨论图的基本概念和算法,为今后的 学习和研究打下基础
• 此后的50年，图论经历了一场爆炸性的发展， 成为数学科学中一门独立的学科。 • 主要分支有图论、超图理论、极值图论、算法 图论、网络图论和随机图论等。 • 几十年来图论在理论上和应用上都得到很大的 发展,特别是在近30多年来由于计算机的广泛应 用而又得到飞跃的发展。 • 在计算机科学、运筹学、化学、物理和社会科 学等方面都取得了不少成果，对计算机学科中 的操作系统研究、编译技术、人工智能和计算 机网络等方面都有广泛的应用。 • 这里主要讨论图的基本概念和算法，为今后的 学习和研究打下基础
5.1引言 一、图的定义: 在集合论中离散对象之间的关系可以用关 系图来描述,这种图就是图论中所述的有向 图 定义51:设V是一个非空集E是V上的二元 关系称有序对(V,E为有向图记为G=(V,E) 或G(V,E)V中的元素称为顶点(或点),V称 顶点集。E是V×V的子集,E中的元素是有 序对称为弧,E称为弧集
5.1 引言 • 一、图的定义： • 在集合论中离散对象之间的关系可以用关 系图来描述,这种图就是图论中所述的有向 图。 • 定义5.1：设V是一个非空集,E是V上的二元 关系,称有序对(V, E)为有向图,记为G=(V,E) 或G(V,E)。V中的元素称为顶点(或点),V称 顶点集。E是V×V的子集,E中的元素是有 序对,称为弧,E称为弧集
对于弧(来讲在关系中a称 为有序对中的第一个元素b称 的点而为第二个元素。 音神O点 在图论中,称a为起点,b为终 b c)b称a与弧(a,b)关联,b与弧(a,b) 关联。 g弧(c,c),f,这种起点与终点相 同的弧就称为自环 在图中,g与E中任何元素(弧) 都不关联,称为孤立点。 例如有向图G=(V,E,V={a,b,d,e,fg}, °E={(a,b),(a,c),(b,c),(c,a),(c,c),(c,e),(d,a,(d2c),(f,e) (f,)}, 弧(a,b表示从顶点a到顶点b的一条带箭头的线
• 例如有向图G=(V,E),V={a,b,c,d,e,f,g}, • E={(a,b),(a,c),(b,c),(c,a),(c,c),(c,e),(d,a),(d,c),(f,e), (f,f)}, • 弧(a,b)表示从顶点a到顶点b的一条带箭头的线。 对于弧(a,b)来讲,在关系中a称 为有序对中的第一个元素,b称 为第二个元素。 在图论中，称a为起点，b为终 点。 称a与弧(a,b)关联，b与弧(a,b) 关联。 弧(c,c),(f,f)这种起点与终点相 同的弧就称为自环。 在图中，g与E中任何元素(弧) 都不关联，称为孤立点
b称为弧(a,b)的端点,a ()音 对应的孤④,b称为自 一中任何弧都不关联 9点。与一条弧相关联 接的或相邻的。一顶 d3这些弧是弧邻接或弧 相邻。 例如上图中a与b相邻;c与d相邻;(a,b)与(b,c) 弧相邻
• 定义5.2：顶点a和b称为弧(a,b)的端点,a 为起点,b为终点。称a和b与弧(a,b)关联。 若顶点a和b相同,则对应的弧(a,b)称为自 环。若V中某顶点与E中任何弧都不关联, 则该顶点称为孤立点。与一条弧相关联 的两个顶点称为邻接的或相邻的。一顶 点关联于几条弧,称这些弧是弧邻接或弧 相邻。 例如上图中a与b相邻;c与d相邻;(a,b)与(b,c) 弧相邻
察它的顶点与弧的连接关 有的性质。至于各顶点之 长短曲直都是无关紧要的 的元素都是有序对,若改 eV面介绍的无向图。 个非空集,E是以中两 3 集为元素的集合,称有 4 7 该图的 15V23495 6},E={{v1,V2,{v1,w5,{v2,V2}, {v2v3},{v2,V4},{v2,v53,v2,v53,{v32V4,{v4,v5} 边{v1,V2}关联于顶点a,b, 而{v2V2}这种关联的两个顶点是相同的称为自环。 而v不关联任何边,也称为孤立点。 顶点v同时关联边{v2,V4},{v3,V4},{v4,vs},称这些边为边邻接另外 在上图中,边{v2Vs}出现了两次,象这种两个顶点之间出现不止 一条的边称为多重边
• 在研究有向图时,只考察它的顶点与弧的连接关 系以及整个图形所具有的性质。至于各顶点之 间的相对位置及弧的长短曲直都是无关紧要的。 • 对于有向图，弧集中的元素都是有序对，若改 成无序对，则就是下面介绍的无向图。 • 定义5.3：设V是一个非空集,E是以V中两 个元素组成的多重集为元素的集合, 称有 序 对 ( V,E)为 无向图 ,也记为 G=(V,E)或 G(V,E)。V中的元素称为顶点或点,V称为 顶点集, E中的元素称为边,E称为边集。 • E中元素现在也是集合，由于可能出现{a,a} 这种情况，所以说E中元素是V中两个元 素组成的多重集。 该 图 的 V={v1 ,v2 ,v3 ,v4 ,v5 ,v6 }，E={{v1 ,v2 },{v1 ,v5 ,}，{v2 ,v2 }, {v2 ,v3 },{v2 ,v4 },{v2 ,v5 },{v2 ,v5 },{v3 ,v4 },{v4 ,v5 }}， 边{v1 ,v2 }关联于顶点a,b， 而{v2 ,v2 }这种关联的两个顶点是相同的称为自环。 而v6不关联任何边，也称为孤立点。 顶点v4同时关联边{v2 ,v4 },{v3 ,v4 },{v4 ,v5 }，称这些边为边邻接另外 在上图中，边{v2 ,v5 }出现了两次，象这种两个顶点之间出现不止 一条的边称为多重边
定义57:若图G=(V,E)中,连结两个顶点 之间的边可以不止一条这些边称为多重 边,则图G称为多重图。无自环的非多重 图称为简单图。边集为空集的图称为零 图。只有一个顶点的图称为平凡图。若 G中每两个顶点之间恰有一条边,则称G 为完全图。n个顶点的完全图记为Kn 在定义5.7中零图是指没有边的图,其每 个顶点为孤立点但顶点集V不能是空集。 同样在有向图中,也可定义多重弧,多 重有向图和简单有向图
• 定义5.7：若图G=(V,E)中, 连结两个顶点 之间的边可以不止一条这些边称为多重 边,则图G称为多重图。无自环的非多重 图称为简单图。边集为空集的图称为零 图。只有一个顶点的图称为平凡图。若 G中每两个顶点之间恰有一条边, 则称G 为完全图。n个顶点的完全图记为Kn。 • 在定义5.7 中,零图是指没有边的图,其每 个顶点为孤立点,但顶点集V不能是空集。 • 同样在有向图中，也可定义多重弧，多 重有向图和简单有向图
为了叙述方便起见简称无向图为图如果 在图(有向图)中顶点标以名称如上图中顶 点标a,b,c,d,e,f,这样的图(有向图称为标 定图有向图,否则称为非标定图(有向图) 下面主要考虑标定图。 如果一个图的顶点集和边集是有限的则称 该图为有限图,类似地定义有限有向图 我们这里讨论的图和有向图是指有限图和 有限有向图。 图(有向图的最本质的内容就是顶点与边 (弧)的关联关系。为了描述这一关系现在 引进一个重要的概念,即顶点的度数
• 为了叙述方便起见,简称无向图为图,如果 在图(有向图)中顶点标以名称,如上图中顶 点标a,b,c,d,e,f,g,这样的图(有向图)称为标 定图(有向图),否则称为非标定图(有向图)。 下面主要考虑标定图。 • 如果一个图的顶点集和边集是有限的,则称 该图为有限图, 类似地定义有限有向图。 我们这里讨论的图和有向图是指有限图和 有限有向图。 • 图(有向图)的最本质的内容就是顶点与边 (弧)的关联关系。为了描述这一关系,现在 引进一个重要的概念, 即顶点的度数