图论课件第1章图的基本概念.pptVIP

图论及其应用;《图论及其应用》 作者: 张先迪、李正良 购买地点：教材科;参考文献;[5] 李尉萱，《图论》，湖南科学技术出版社，1979 [6] 美，Douglas B.West《图论导引》，机械工业出版社，2007 李建中，骆吉洲译 [7] 杨洪，《图论常用算法选编》，中国铁道出版社，1988 [8] 陈树柏，《网络图论及其应用》，科学出版社，1982;[9] Chris Godsil，Gordon Royle 《Algebraic Graph Theory》，世界图书出版公司北京公司，2004 [10] 王朝瑞，《图论》，高等教育出版社，1983;第一章 图的基本概念;1、研究对象;3、应用状况;1、图的定义;图可以用图形表示：V中的元素用平面上一个黑点表示，E 中的元素用一条连接V中相应点对的任意形状的线表示。;图的相关概念：;顶点u与v相邻接：顶点u与v间有边相连接；其中u与v称为 该边的两个端点；;用点抽象分子式中的碳原子和氢原子，用边抽象原子间 的化学键。;(2) 商业中的图论模型;用点表示城市，两点连线当且仅当两城市有航线。为了 求出两城市间最短航线，需要在线的旁边注明距离值。;(4) 任务分配问题;(5) 考试时间安排问题; 一种可行的安排方案为：第一时间：a, d, e;第二时间： b, f ；最后：c.; 问题归结为在模型图中寻求所谓的“哈密尔顿圈”问题。 将在第四章介绍。; 在图论中，一个很值得研究的问题是如何比较两个 图的异同，这就是图的同构问题。; 判定图的同构是很困难的，属于NP完全问题。对于规模 不大的两个图，判定其是否同构，可以采用观察加推证的 方法。; 例3 证明下面两图同构。; 例4 指出4个顶点的非同构的所有简单图。;(四)、完全图、偶图与补图; 2、所谓具有二分类（X, Y）的偶图（或二部图）是指一个图， 它的点集可以分解为两个(非空)子集X和Y，使得每条边的一个 端点在X中，另一个端点在Y中.;3、对于一个简单图G =（V, E），令集合;所以：;奇数度的顶点称为奇点，偶数度的顶点称偶点。 ;推论1 在任何图中，奇点个数为偶数。;证明：由握手定理有：;图G 的“拓扑不变量”是指与图G有关的一个数 或数组(向量)。它对于与图G同构的所有图来说，不会发生改变。;两两配对后分别在每配对点间先连???条边，然后 在每个顶点画dj-1/2个环。该图的度序列就是已知 数组。;定理：非负整数组;情形2：点v1与点vd1+2，….vn的某些顶点邻接。在这种 情况下，作如下假设：设v1与vj0邻接，但当kj0时， v1与vk不邻接；又设v1与vi0不邻接，但当ki0时，v1 与点vk邻接。;如此进行下去，最后可以变情形2为情形1。;定理: (厄多斯1960)非负整数组;定理: 一个满足d2=dn-1的图序列;3、图的频序列及其性质;定义： 设n阶图G的各点的度取s个不同的非负整数 d1,d2,…, ds。又设度为di的点有bi个 (i = 1,2,…,s)，则 ;作业;Thank You !