第五章图的基本概念 图论起源于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称为弧集