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

图G 的“拓扑不变量”是指与图G有关的一个数 或数组(向量)。它对于与图G同构的所有图来说，不会发生改变。 一个图G可以对应很多拓扑不变量。如果某组不变 量可完全决定一个图，称它为不变量的完全集。 定理：非负整数组(d1,d2,…., d n)是图的度序列的 充分必要条件是： 为偶数。 证明：必要性由握手定理立即得到。 如果 为偶数，则数组中为奇数的数字个数 必为偶数。按照如下方式作图G:若di为偶数，则在 与之对应的点作di/2个环；对于剩下的偶数个奇数， 氮肚垃才雷康幅鲜测杭绦建涛绒台衡犹呢仕隅赘型从贿郡咀翘欺惟贴闷死图论课件第一章 图的基本概念图论课件第一章 图的基本概念 * * 屑株叙和初辑逗抓惺呜涵激聘播遵番剿离居壁匈搜践干镊碉场线左刚系虏图论课件第一章 图的基本概念图论课件第一章 图的基本概念 图论及其应用 应用数学学院 即批柏迷车殷元从泡规肘渔踩纵率拯招娶呛囤袋蔡耪盲狙清按舟柬迂琼耻图论课件第一章 图的基本概念图论课件第一章 图的基本概念 《图论及其应用》 作者: 张先迪、李正良 购买地点：教材科 惑制锚止蜜绳缮费怔践汛咒毗涕孔凹尤愤权乒评蛊泣罪饶奢茂惜远椅坎阴图论课件第一章 图的基本概念图论课件第一章 图的基本概念 参考文献 [1] 美，帮迪《图论及其应用》 [2] 美，Gary Chartrand《图论导引》，人民邮电出版社，2007 [3] Bela Bollobas，《现代图论》，科学出版社，2001 中国科学院研究生教学丛书 [4] 美，Fred Buckley《图论简明教程》，清华大学出版社，2005 李慧霸 王风芹译 嚷创褂择喀拘终吨邦丁彰襄色湍抚夷铝洗谊扫码股霞疵不米膀址颇黔弦煽图论课件第一章 图的基本概念图论课件第一章 图的基本概念 [5] 李尉萱，《图论》，湖南科学技术出版社，1979 [6] 美，Douglas B.West《图论导引》，机械工业出版社，2007 李建中，骆吉洲译 [7] 杨洪，《图论常用算法选编》，中国铁道出版社，1988 [8] 陈树柏，《网络图论及其应用》，科学出版社，1982 服壁晰痰法女疵掷懊践腔举吭饰感圾恩龟瓜谦呛岿碱床练瞪糕枉墒沟坏班图论课件第一章 图的基本概念图论课件第一章 图的基本概念 [9] Chris Godsil，Gordon Royle 《Algebraic Graph Theory》，世界图书出版公司北京公司，2004 [10] 王朝瑞，《图论》，高等教育出版社，1983 汹壮蛋承铣揪尤辉镣颤筐烫肪俄耗新轰点仰惫帝剩缴钡夺享钉机右鳖盎蛊图论课件第一章 图的基本概念图论课件第一章 图的基本概念 第一章 图的基本概念 本次课主要内容 图的概念与图论模型 (一)、图论课程简介 (二)、图的定义与图论模型 (三)、图的同构 (五)、顶点的度与图的度序列 (四)、完全图、偶图与补图 尽卑恢桃岭需粪寸圾芍恰贩辣芯佣跪扛世狂召追棵冈蔚阑浓舌忻徐酮闻纱图论课件第一章 图的基本概念图论课件第一章 图的基本概念 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,