几十年来图论在理论上和应用上都得到很 大的发展,特别是在近30多年来由于计算 机的广泛应用而又得到飞跃的发展。 在计算机科学、运筹学、化学、物理和社 会科学等方面都取得了不少成果,对计算 机学科中的操作系统研究、编译技术、人 工智能和计算机网络等方面都有广泛的应 用。 这里主要讨论图的基本概念和算法,为今后 的学习和研究打下基础
• 几十年来图论在理论上和应用上都得到很 大 的发展, 特别是在近30多年来由于计算 机的广泛应用而又得到飞跃的发展。 • 在计算机科学、运筹学、化学、物理和社 会科学等方面都取得了不少成果，对计算 机学科中的操作系统研究、编译技术、人 工智能和计算机网络等方面都有广泛的应 用。 • 这里主要讨论图的基本概念和算法, 为今后 的学习和研究打下基础
本章首先给出图、简单图、完全 图、子图、路和图的同构等概念,接 着研究了连通图性质和规律,给出了 邻接矩阵、可达性矩阵、连通矩阵和 完全关联矩阵的定义。最后介绍了欧 拉图与哈密尔顿图
本章首先给出图、简单图、完全 图、子图、路和图的同构等概念，接 着研究了连通图性质和规律，给出了 邻接矩阵、可达性矩阵、连通矩阵和 完全关联矩阵的定义。最后介绍了欧 拉图与哈密尔顿图
图的定义 (无向图)一个无向图G是一个有序二元组<V,E>, 记作G=<V,E>,其中V是一个非空集合,V中的元素称为 结点或顶点;E是无序积V&V的多重子集(元素可重复出现 的集合),称E为G的边集,E中的元素称为无向边或简称边。 (有向图)一个有向图G是一个有序二元组<V,E>,记 作G=<V,E>,其中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=<V,E>={1,n2,3,42n3},E={(n,n2) (v2,v2)(v2,v3)(,v3)(v,v3)(v3v4)},G的图形如图213所示。 例如G=<VE>,其中V={v,"2,v3,n4,vs}, E={<V1,>2<V,n2><V2,3><,2><V2n4><V3,v4>},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,E>,其中V={v 19239V49V5∫9 E={(v1,V1),(v12),(v2,V3),(v2,v3 (v1yV5),(v2,v5),(v4,V5)。 e6 4 O⊙5
例 画出下列图形。 (1) G=<V,E>,其中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