第二部分图的基本概念
第二部分 图的基本概念
图论问题的起源 18世纪东普鲁士哥尼斯堡被普列戈 尔河分为四块,它们通过七座桥相互连接, 如下图当时该城的市民热衷于这样一个 游戏:“一个散步者怎样才能从某块陆地 出发,经每座桥一次且仅一次回到出发 点?
图论问题的起源 18世纪东普鲁士哥尼斯堡被普列戈 尔河分为四块,它们通过七座桥相互连接, 如下图.当时该城的市民热衷于这样一个 游戏:“一个散步者怎样才能从某块陆地 出发，经每座桥一次且仅一次回到出发 点？” S N A B
哥尼斯堡七桥问题 如何不重复地走完七桥后回到起点? 陆地 岛屿 屿 陆地 B
陆地 岛屿 岛屿 陆地 哥尼斯堡七桥问题 如何不重复地走完七桥后回到起点？ 。 。 。 A 。 B C D
当时人们热衷于这样的游戏:设想从任一个地 方出发通过每座桥一次且仅一次后回到原地, 这是否可能?但多次实践都发现不行。 1727年欧拉的朋友向欧拉提出了这个问题是否 有解? 1736年欧拉用图论的方法解决了这个问题写 了第一篇图论的论文,成为图论的创始人。 后来称此问题为哥尼斯堡七桥问题
当时人们热衷于这样的游戏：设想从任一个地 方出发通过每座桥一次且仅一次后回到原地, 这是否可能?但多次实践都发现不行。 1727 年欧拉的朋友向欧拉提出了这个问题是否 有解？ 1736 年欧拉用图论的方法解决了这个问题,写 了第一篇图论的论文,成为图论的创始人。 后来称此问题为哥尼斯堡七桥问题
但在此之后100年间,没有大的进展。 直到 Kirchhoff克希看表用树的理论解决了电 问题。这 的研究进入了一个 最们的量视画论° 直到1920年科尼格( Konig撰写了许多图论方 峰我请号罐落活,意 果 了200年来图论研究的主要成 些后的5年 历了二场爆炸性的发展, 学科学 独立的学料
• 但在此之后100年间，没有大的进展。 • 直到Kirchhoff(克希霍夫)用树的理论解决了电 网络问题。这些结果引起了人们的重视,图论 的研究进入了一个发展时期。 • 直到1920年, 科尼格(Konig)撰写了许多图论方 面的论文。在1936年科尼格(Konig)发表了第 一本图论书籍《有限图与无限图理论》, 总结 了200年来图论研究的主要成果。 • 此后的50年, 图论经历了一场爆炸性的发展, 成为数学科学中一门独立的学科
几十年来图论在理论上和应用上都得到很 大的发展,特别是在近30多年来由于计算 机的广泛应用而又得到飞跃的发展。 在计算机科学、运筹学、化学、物理和社 会科学等方面都取得了不少成果,对计算 机学科中的操作系统研究、编译技术、人 工智能和计算机网络等方面都有广泛的应 用。 这里主要讨论图的基本概念和算法,为今后 的学习和研究打下基础
• 几十年来图论在理论上和应用上都得到很 大 的发展, 特别是在近30多年来由于计算 机的广泛应用而又得到飞跃的发展。 • 在计算机科学、运筹学、化学、物理和社 会科学等方面都取得了不少成果，对计算 机学科中的操作系统研究、编译技术、人 工智能和计算机网络等方面都有广泛的应 用。 • 这里主要讨论图的基本概念和算法, 为今后 的学习和研究打下基础
本章首先给出图、简单图、完全 图、子图、路和图的同构等概念,接 着研究了连通图性质和规律,给出了 邻接矩阵、可达性矩阵、连通矩阵和 完全关联矩阵的定义。最后介绍了欧 拉图与哈密尔顿图
本章首先给出图、简单图、完全 图、子图、路和图的同构等概念，接 着研究了连通图性质和规律，给出了 邻接矩阵、可达性矩阵、连通矩阵和 完全关联矩阵的定义。最后介绍了欧 拉图与哈密尔顿图
图的定义 (无向图)一个无向图G是一个有序二元组, 记作G=,其中V是一个非空集合,V中的元素称为 结点或顶点;E是无序积V&V的多重子集(元素可重复出现 的集合),称E为G的边集,E中的元素称为无向边或简称边。 (有向图)一个有向图G是一个有序二元组,记 作G=,其中V是一个非空的结点集;E是笛卡尔积 V的多重子集,其元素称为有向边,也简称边或弧
图的定义 （无向图）一个无向图 G 是一个有序二元组 V,E ， 记作G =V, E ，其中V 是一个非空集合，V 中的元素称为 结点或顶点；E 是无序积V &V 的多重子集（元素可重复出现 的集合），称 E 为 G 的边集，E 中的元素称为无向边或简称边。 （有向图） 一个有向图 G 是一个有序二元组V,E ，记 作G =V,E ，其中 V 是一个非空的结点集；E 是笛卡尔积 V× V 的多重子集，其元素称为有向边，也简称边或弧
例如G=={1,n2,3,42n3},E={(n,n2) (v2,v2)(v2,v3)(,v3)(v,v3)(v3v4)},G的图形如图213所示。 例如G=,其中V={v,"2,v3,n4,vs}, E={2},G的图形如图214所示 V● VI e e 图21.3 图214
例如G =V, E , V = v1 , v2 ,v3 ,v4 ,v5 , {( , ), 1 2 E = v v ( , ),( , ),( , ),( , ),( , )} 2 2 2 3 1 3 1 3 3 4 v v v v v v v v v v ,G 的图形如图 2.1.3 所示。 例如G =V,E ，其中V = v1 , v2 , v3 , v4 , v5 , { , , , , , , , , , , E = v1 v1 v1 v2 v2 v3 v3 v2 v2 v4 , } v3 v4 , G 的图形如图 2.1.4 所示。 图 2.1.4 4 v 3 v 2 v 1 v 1 e 3 v 4 v 4 e 图 2.1.3 6 e 1 v 5 e 2 e 2 v 3 e 5 v
例画出下列图形。 (1)G=,其中V={v 19239V49V5∫9 E={(v1,V1),(v12),(v2,V3),(v2,v3 (v1yV5),(v2,v5),(v4,V5)。 e6 4 O⊙5
例 画出下列图形。 (1) G=,其中V={v1 ,v2 ,v3 ,v4 ,v5 }, E={(v1 ,v1 ), (v1 ,v2 ), (v2 ,v3 ), (v2 ,v3 ), (v1 ,v5 ), (v2 ,v5 ), (v4 ,v5 )}。 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6