《图论及其应用》课程教学课件（PPT讲稿）第一章 图的基本概念 1-1 图论简介

参考文献 [1]美，邦迪 《图论及其应用》 I2]美，Gary Chartrand《图论导引》，人民邮电 出版社，2007 I3】Bela Bollobas,《现代图论》，科学出版社， 2001中国科学院研究生教学丛书 [4美，Fred Buckley《图论简明教程》，清华大学 出版社，2005李慧霸王风芹译

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 3 参考文献 [1] 美，邦迪《图论及其应用》 [2] 美，Gary Chartrand《图论导引》，人民邮电 出版社，2007 [3] Bela Bollobas，《现代图论》，科学出版社， 2001 中国科学院研究生教学丛书 [4] 美，Fred Buckley《图论简明教程》，清华大学 出版社，2005 李慧霸 王风芹译

[5]李尉萱，《图论》， 湖南科学技术出版社，1979 I6美，Douglas B.West《图论导引》， 机械工业出 版社，2007李建中，骆吉洲译 [7]杨洪，《图论常用算法选编》，中国铁道出版社， 1988 81陈树柏， 《网络图论及其应用》，科学出版社， 1982

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 4 [5] 李尉萱，《图论》，湖南科学技术出版社，1979 [6] 美，Douglas B.West《图论导引》，机械工业出 版社，2007 李建中，骆吉洲译 [7] 杨洪，《图论常用算法选编》，中国铁道出版社， 1988 [8] 陈树柏，《网络图论及其应用》，科学出版社， 1982

[9]Chris Godsil,Gordon Royle Algebraic Graph Theory》,世界图书出版公司北京公司，2004 [10]王朝瑞，《图论》，高等教育出版社，1983

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 5 [9] Chris Godsil，Gordon Royle 《Algebraic Graph Theory》，世界图书出版公司北京公司，2004 [10] 王朝瑞，《图论》，高等教育出版社，1983

第一章图的基本概念 本次课主要内容 图的概念与图论模型 (一)、图论课程简介 (二)、图的定义与图论模型 (三)、图的同构

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 第一章 图的基本概念 本次课主要内容 图的概念与图论模型 (一)、图论课程简介 (二)、图的定义与图论模型 (三)、图的同构

(一)、图论课程简介 1、研究对象 图论是研究点与边组成的“图形”问题的一门科 学。属于离散数学分支 2、发展历史 图论起源于18世纪的1736年，标志事件是“哥尼 斯堡七桥问题。 数学家欧拉被称为“图论之父”. 20世纪30年代出版第一本图论著作

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 1、研究对象 图论是研究点与边组成的“图形”问题的一门科 学。属于离散数学分支. (一)、图论课程简介 2、发展历史 图论起源于18世纪的1736年，标志事件是“哥尼 斯堡七桥问题. 数学家欧拉被称为“图论之父”. 20世纪30年代出版第一本图论著作

目前，图论已形成很多分支：如随机图论、网络 图论、代数图论、拓扑图论、极值图论等。 3、应用状况 图论的应用已经涵盖了人类学、计算机科学、化 学、环境保护、非线性物理、心理学、社会学、交 通管理、电信以及数学本身等。 4、教学安排 主要介绍图的一些基本概念、基本理论和图论的 典型应用

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 8 3、应用状况 图论的应用已经涵盖了人类学、计算机科学、化 学、环境保护、非线性物理、心理学、社会学、交 通管理、电信以及数学本身等。 目前，图论已形成很多分支：如随机图论、网络 图论、代数图论、拓扑图论、极值图论等。 4、教学安排 主要介绍图的一些基本概念、基本理论和图论的 典型应用

(二)、图的定义与图论模型 1、图的定义 一个图是一个序偶,记为G=(V,E),其中： (1)V是一个有限的非空集合，称为顶点集合，其 元素称为顶点或点。用V表示顶点数； (2)E是由V中的点组成的无序对构成的集合，称 为边集，其元素称为边，且同一点对在E中可以 重复出现多次。用E表示边数

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 9 1、图的定义 (二)、图的定义与图论模型 一个图是一个序偶，记为G=(V,E),其中： (1) V是一个有限的非空集合，称为顶点集合,其 元素称为顶点或点。用|V|表示顶点数； (2) E是由V中的点组成的无序对构成的集合，称 为边集，其元素称为边，且同一点对在E中可以 重复出现多次。用|E|表示边数

图可以用图形表示：V中的元素用平面上一个黑点表示，E 中的元素用一条连接V中相应点对的任意形状的线表示。 例1、设图G=。这里V={WVV3V4} E=ferezeseseseh, e1=(V1,V2),e2=(V1,v3),e3=(V1,V4), e4=(V2,vg),e5=(Vg,2〉，e6=(v3,g)。 10

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 10 图可以用图形表示：V中的元素用平面上一个黑点表示，E 中的元素用一条连接V中相应点对的任意形状的线表示。 例1、设图G＝。这里V＝{v1 ,v2 ,v3 ,v4 } E＝{e1 ,e2 ,e3 ,e4 ,e5 ,e6 }， e1 ＝(v1 ,v2 )，e2 ＝(v1 ,v3 )，e3 ＝(v1 ,v4 )， e4 ＝(v2 ,v3 )，e5 ＝(v3 ,v2 )，e6 ＝(v3 ,v3 )。 v1 v2 v3 v4 e1 e2 e3 e4 e5 e6

图的相关概念： 有限图：顶点集和边集都有限的图称为有限图； 平凡图：只有一个顶点的图称为平凡图： 空图：边集为空的图称为空图； n阶图：顶点数为n的图称为n阶图； (m,m)图：顶点数为n,边数为m的图称为(n,m)图； 边的重数：连接两个相同顶点的边的条数称为边的重数； 重数大于1的边称为重边； 环：端点重合为一点的边称为环； 简单图：无环无重边的图称为简单图；其余的图称为 复合图：

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 11 图的相关概念： 有限图：顶点集和边集都有限的图称为有限图； 平凡图：只有一个顶点的图称为平凡图； 空图：边集为空的图称为空图； n阶图：顶点数为n的图称为n阶图； (n, m) 图：顶点数为n,边数为m的图称为(n, m) 图； 边的重数：连接两个相同顶点的边的条数称为边的重数； 重数大于1的边称为重边； 环：端点重合为一点的边称为环； 简单图：无环无重边的图称为简单图；其余的图称为 复合图；

顶点u与v相邻接：顶点u与v间有边相连接；其中u与v称为 该边的两个端点； 顶点u与边e相关联：顶点u是边e的端点； 边e,与边e,相邻接：边e1与边e2有公共端点； 2、图论模型 为了抽象和简化现实世界，常建立数学模型。图是关系的 数学表示，为了深刻理解事物之间的联系，图是常用的数学 模型。 (1)化学中的图论模型 19世纪，化学家凯莱用图论研究简单烃一】 即碳氢化合物 12

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 12 顶点u与v相邻接：顶点u与v间有边相连接；其中u与v称为 该边的两个端点； 顶点u与边e相关联：顶点u是边e的端点； 边e1与边e2相邻接：边e1与边e2有公共端点； 2、图论模型 为了抽象和简化现实世界，常建立数学模型。图是关系的 数学表示，为了深刻理解事物之间的联系，图是常用的数学 模型。 (1) 化学中的图论模型 19世纪，化学家凯莱用图论研究简单烃——即碳氢化合物