图论第一节.ppt

* 图G 的“拓扑不变量”是指与图G有关的一个数 或数组(向量)。它对于与图G同构的所有图来说，不会发生改变。 一个图G可以对应很多拓扑不变量。如果某组不变 量可完全决定一个图，称它为不变量的完全集。 定理：非负整数组(d1,d2,…., d n)是图的度序列的 充分必要条件是： 为偶数。 证明：必要性由握手定理立即得到。 如果 为偶数，则数组中为奇数的数字个数 必为偶数。按照如下方式作图G:若di为偶数，则在 与之对应的点作di/2个环；对于剩下的偶数个奇数， * 图 论 图论是一个历史悠久而近些年又飞速发展的数学分支。它起源于1736年瑞士数学家欧拉利用图解决哥尼斯堡七桥问题。它是离散数学的的一个重要分支，是组合数学的一部分。 * 它是通过点和线组成的拓扑图形，较为方便的模拟自然界和人类社会的各种系统并建立相应的数学模型，根据图的性质进行分析，提供研究各种系统的理论。 随着计算机在社会中作用的变大，图论的应用日益广泛，应用遍及计算机科学、信息科学、人工智能、网络理论、系统工程、控制论、运筹学，物理，量子化学以及经济管理等各个领域。 * * 参考文献 [1] 美，帮迪《图论及其应用》 [2] 美，Gary Chartrand《图论导引》，人民邮电出版社，2007 [3] Bela Bollobas，《现代图论》，科学出版社，2001 中国科学院研究生教学丛书 [4] 美，Fred Buckley《图论简明教程》，清华大学出版社，2005 李慧霸 王风芹译 * [5] 李尉萱，《图论》，湖南科学技术出版社，1979 [6] 美，Douglas B.West《图论导引》，机械工业出版社，2007 李建中，骆吉洲译 [7] Chris Godsil，Gordon Royle 《Algebraic Graph Theory》，世界图书出版公司北京公司，2004 * 第一章 图的基本概念 本次课主要内容 图的概念与图论模型 (一)、图论课程简介 (二)、图的定义与图论模型 (三)、图的同构 (四)、完全图、偶图与补图 * 1、研究对象 图论是研究点与线组成的“图形”问题的一门科学。属于应用数学分支。 (一)、图论课程简介 2、发展历史 图论起源于18世纪的1736年，标志事件是“哥尼斯堡七桥问题 数学家欧拉被称为“图论之父” 20世纪30年代出版第一本图论著作 * 3、应用状况 图论的应用已经涵盖了人类学、计算机科学、化学、环境保护、流体动力学、心理学、社会学、交通管理、电信以及数学本身等。 目前，图论已形成很多分支：如结构图论、网络图论、代数图论、拓扑图论等 4、教学安排 主要介绍图的一些基本概念、基本理论和图论的典型应用。60学时。 * 1、图的定义 (二)、图的定义与图论模型 一个图是一个序偶V,E，记为G=(V,E),其中： (1) V是一个有限的非空集合，称为顶点集合,其 元素称为顶点或点。用|V|表示顶点数； (2) E是由V中的点组成的无序对构成的集合，称 为边集，其元素称为边，且同一点对在E中可以 重复出现多次。用|E|表示边数。 * 图可以用图形表示：V中的元素用平面上一个黑点表示，E 中的元素用一条连接V中相应点对的任意形状的线表示。 例1、设图G＝V,E。这里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阶图； (n, m) 图：顶点数为n,边数为m的图称为(n, m) 图； 边的重数：连接两个相同顶点的边的条数称为边的重数； 重数大于1的边称为重边； 环：端点重合为一点的边称为环； 简单图：无环无重边的图称为简单图；其余的图称为 复合图； * 顶点u与v相邻接：顶点u与v间有边相连接；其中u与v称为 该边的两个端点； 顶点u与边e相关联：顶点u是边e的端点； 边e1与边e2相邻接：边e1与边e2有公共端点； 2、图论模型 为了抽象和简化现实世界，常建立数学模型。图是关系的 数学表示，为了深刻理解事物之间的联系，图是常用的数学 模型。 (1) 化学中的图论模型 19世纪，化学家凯莱用图论研究简单烃——即碳氢化合物 * 用点抽象分子式中的碳原子和氢原子，用边抽象原子间 的化学键。 通过这样的建模，能很好研究简单烃的同分异构现象 例如：C4H10的两种同分异构结构图模型为： h