10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20

所需积分/C币:50 2017-09-18 12:09:17 16.6MB PDF
收藏 收藏 1
举报

全书共分13章, 前3章介绍一些基础知识, 后面章节介绍了树、连通性、可遍历性、有向图、匹配和因子分解、可平面性、图的染色、Ramsey 数、距离及控制等内容。《图论导引》内容全面, 证明与应用实例并举, 还给出了证明方法, 书的最后提供了奇数号习题的解答或提示。 《图论导引》可作为高等院校相关专业本科生一学期课程的教材,也可供图论爱好者自学使用。 第1章 引言 1.1 图与图模型 1.2 连通图 1.3 若干常见的图类 1.4 多重图与有向图 第2章 度 2.1 顶点的度 2.2 正则图 2.3 度序列 2.4 延伸阅读:图与矩阵 2.5 专题探索:不规则图 第3章 同构图 3.1 同构的定
译者序 1736年,欧拉( Euler)在他的一篇论文中讨论了哥尼斯堡七桥问题,由此诞生 了一个全新的数学分支—图论( Graph theory).经过200多年的发展,图论已 发展成为一个理论与应用兼有的研究领域除经典图论之外,图论与代数(如矩阵 论和群论等)的结合形成了代数图论,与拓扑的结合形成了拓扑图论,与概率的结合 形成了随机图论,与谱几何的结合形成了谱图理论,等等.此外,它在有机化学上的 应用形成了化学图论,同时它在计算机和模式识别等领域也有很高的应用价值 本书是一本优秀的图论教材,由美国西密歇根大学教授 Gary Chartrand和Png Zhang合著.( hartland教授为国际著名的图论专家,他在图论领域发表了数量众 多的优秀论文,总数排名世界第4位.合作者包括Ed6s和 Frank Harary等著名数 学家 本书生动有趣地介绍了图论的常见专题,同时也包含一些待进一步研究或未解 决的问题,用于激发学生兴趣,培养创新能力.本书可作为本科生一学期课程教材, 也可供图论爱好者自学使用本书内容全面:证明与应用实例并举,还给出了证明方 法,书的最后提供了奇数号习题的解答或提示 本书由范益政、汪毅、龚世才和朱明翻译,全书最后由范益政统稿.限于译者 水平,译文中难免存在疏漏和错误,望广大读者批评指正 感谢人民邮电出版社北京图灵文化发展有限公司为我们提供机会,把这本优 秀教材推荐给国内广大读者,促进中国图论的发展.最后感谢国家自然科学基金 (10601001)的资助 译者 2007年1月 谨以此书献给那些以不同方式为推动图论发展做出杰出贡献的众名数学家们 Kla Wagner Gabriel Julius DDir Frank Oystein Philip Icy Hall Hass Tibor 入 Whitney Alfred Denes William Kerr ong hamilton Paul Erd Turan Kazimierz William Peter Kuratowski Tutte Tait Pel Leonhard Heawood Euler Claude Frucht Youn Arth Karl leng Anton Kotzig 从Ronr g到 KOnig的书 图论的传说正是如此, 而且越来越精彩 Blanche Descartes(1969) 前言 也许你并不感到惊讶,当我们自已在学习数学时,一直认为我们所学到的就是 那些已知的事实—那些自古就有的事实.直到后来,我们才明白这些事实(即 “定理”,已经成为我们词汇的一部分)并非早就存在,而正是人们发现了这些事实 的确,这些人的名字也成为我们学习内容的一部分 数学已经存在了几「年.在远古时代,一些特定的文化形成了它们独特的数学 这当然包括埃及、巴比伦、希腊、中国、印度和日本.在近代,这些都融合为统一的 国际数学.数学已经变得更加系统化,且已经被划分为有更加明确定义的若干领域 (尽管它们之间存在一些重要的交叉).有了这些变化,关于一个数学命题正确性的 阐述(或证明)也就变得更加结构化且更烦易于表达 本书的宗旨是向本科生(或者某些高中生)介绍数学的一个领域-—图论,它 诞生于18世纪上半叶.到19世纪下半叶这个领域才发展为数学的一个系统的分 支而直到20世纪上半叶,这门学科才有自己的著作出现.然而自20世纪下半叶开 始,这门学科发展迅猛 我们的意图是向读者介绍这门学科的若干主要专题,以及那些为发展和塑造该 领域做出贡献的人.一开始,大多数人都和你一样,喜欢数学并带着强烈的好奇心 正如其他事物(尽管不常提起)一样,数学也有其自身非严格的一面;我们也介绍其 中的若干事件.即使是最聪明的数学家,他也不可能涧悉一切,我们给出一些没有 研究透彻的专题,它的答案甚至这些问题也还是未知的这将为你提供一些机会,进 行一些创造性思考.事实上,也许下一个对此学科有重大影响的人就是你 促使图论变得有趣的原因之一,是可以用图为特定问题建模.这些问题在图的 帮助下得以展开研究(或可能被解决).正由于这一点,图模型在全书经常出现当 然,图论是数学的一个领域,因而必然涉及数学理论的研究 些概念以及它们 之间的联系.我们之所以选择本书所含的专题和结论,是因为它们或者非常有趣或 者非常重要,或者是这门学科的代表 如前所述,这本书是为本科生写的.正因为这一点,我们一般在合适的地方都给 出了定理的证明证明的方法带有启发性,且证明也不是太长.我们总希望本书的 内容不仅对学数学的学生,也对其他图论爱好者都是有益的、有趣的这本书同样 适用于自学 本书包含3个附录在附录1中,我们回顾一些重要的有关集合和逻辑的事实; 附录2主要讨论等价关系和映射;附录3介绍了一些证明的方法,考虑到本科生仍 然处于掌握证明的学习过程中,我们在每个迸明的开始之处都指出证明的方法.我 们知道,如果一个学习者在试图弄清楚一个证明时,这个证明读起来并不舒服且需 言前2 要很多的预备知识,那么他会很沮丧.因此,我们尽最大努力给出清晰的、表述流畅 的证明 我们感到,如果能够熟悉古往今来为图论做出贡献的人,对图论的喜爱也能得 以加强,这一点对于数学的其他领域,事实上对于任一个学术领域都是类似的.因 此,本书也包含些我们认为有趣的有关“图论人”的评注,我们相信这些人也是图 论故事的一部分,我们在正文中讨论他们,而不是仅作为脚注.我们经常忽略数学 是一个活的学科.图论是由人创造的,是一门正在进化发展的学科 本书也把若干节设置为“延伸阅读”.若该书作为教材使用,则这些部分可以省 略,并无负面影响.有时,一个延伸阅读就是图论的一个研究领域,我们认为它非常 有趣,但可能授课的老师不去讲它,或者是因为没有时间,或者这不是他的擅长.有 的时侯,延仲阅读可以提供一些图论杂闻:涉及的数学内容很少,仅仅是因为我们认 为它非常有趣 本书还有一些节设置为“专题探索”这些节包含了一些专题,学生可以去尝试, 可以去发挥想象.这就为学生提供一个发现问题的机会.总之,我们相信这会为某 些学生带来学习的乐趣 就本书作为课程教材而言,我们认为前3章可作为介绍性的内容这部分内容可 以讲得快一点.学生应该可以自己读懂它们授课老师也可以不讲连通性和 Menger 定理、8.3节、9.2节、10.3节和11.2节可以略去,第12章和第13章可根据老师个 人意愿选讲. 在本书的结尾,我们提供了奇数号习题的解答或提示、参考文献、人名素引 数学术语索引以及符号列表 撰写这本书的想法源于我们与 Mcgraw-Hi出版公司执行编辑 robert ross6 交流与讨论.我们对他的鼓励表示感谢.我们也向 Mcgraw-Hll出版公司的其他 员工的帮助表示感谢,包括 Daniel Seibert(编辑助理), Vicki Krug(高级策划编辑). 此外,我们对下面的审稿人致以最高的敬意,他们是: Jay bagga(鲍尔州立大学); Richard borie(阿拉巴马大学)、 Anthony evans(赖特州立大学)、 Mark ginn(阿巴拉 契亚州立大学)、 Mark goldberg(伦斯勒工业学院)、 arthur hobbs(得克萨斯农工大 学)、 Garth isaak(利哈伊大学)、 Daphne liu(加州州立大学洛杉矶分校)、 Alan mills 田纳西技术大学)、 Dan pritikin(迈阿密大学)、 John Reay(西华盛顿大学)和Yuc zhao(中佛罗里达大学) Gary Chartrand g inang 译者简介 范益攻交徽大学数学与计算科学学院教授,博士生导师.2001年获中国科学 与技术大学理学博士学位,2003~2005年在南京师范大学从事博士后研究上作,主 要研究方向为代数图论及其应用;已发表学术论文20多篇,其中有10篇被S(1收 录,8篇被HⅠ收录.主持国家自然科学基金《图的 Laplace理论及其在计算机枧觉 中的应用》和安徽省自然科学基金《谱图理论及其应用》等项目 汪毅安徽大学数学与计算科学学院讲师.主要研究方向为谱图及其应用 已发表学术论文10余篇 龚世才安徽理工大学副教授.主要研究方向为图论及其应用,已发表学术论 文10余篇 朱明安徽大学数学与计算科学学院研究生.主要研究方向为代数图论及其 应用,已发表学术论文2篇 目录 第1章引 64延伸阅读:早期的图论 11图与图模型 书籍……137 1.2连通图… 第7章有向图………141 13若于常见的图类 7.1强有向图… 141 14多重图与有向图 …24 72竞赛图…… 甲看● 第2章度… 27 73延仲阅读:次策……154 21顶点的度 2 7.4专题探索:酒瓶问题…158 2.2正则图 ……·33 第8章匹配与分解 161 23度序列 37 81|兀配 …·161 24延伸阅读:图与矩阵 82因子分解 170 2.5专题探索:不规则图……44 8.3分解与优美标号………184 第3章同构图 48 84延仲阅读:立即疯游戏……189 3.1同构的定义 …48 85延仲闯读: Petersen图……194 3.2同构关系 号·卩日【·甲萨 ……55 86专题探索:图的y标号 198 3.3延伸阅读:图与群……………57第9章可平面性… 34延伸阅读:重构与可解性……67 91平面图 201 第4章树 74 92图嵌入到曲面… 213 41割边 9.3延伸阅读:图的子式 221 42树 76 94专题探索:图嵌入到图…224 43最小生成树问题… 第10章染色 ……·229 4.4延伸阅读:生成树的个数……87 10.1四色问题 229 第5章连通性 102顶点染色 236 5.1割点 10.3边染色 52块 104延伸阅读: Heawood地图 53连通度 99 染色定理 255 54 Menger定理 108 10.5专题探索:局部染色……259 5.5专题探索:测地集 113第11章R armsey 数 264 第6章可遍历性 116 11.1图的 Ramsey数 264 61 Euler图………116 112 uran定理 6.2 Hamilton图 122 113专题探索;彩色 Ramsey 63专题探索: Hamilton链与 数 Hamilton数……… 133 11.4延伸读:Erd6s数 285 2目录 第12章距离 290 13.2专题探索:分层 329 121图的中心 290 13.3专题探索:关灯游戏………334 22远点 295 134延伸阅读:明天更美好…337 123延伸阅读:定位数 302附录1集合与逻辑 339 124延伸阅读:绕路距离和有向 附录2等价关系与映射………343 距离 306 附录3证明方法 347 12.5专题探索:频道分配……311奇数号习题的解答与提示 353 126专题探索:图与图之间的 参考文献 380 距离… 甲甲·■号·冒 316 人名索引……………………388 第13章控制 319数学术语索引 391 131图的控制数…………319符号列表 ………398 第1章引 1.1图与图模型 家大型的出版公司在科学、技术和计算领域内有10名编辑(分别用1,2,…, 10来标记)这10位编辑在每个月的第一个星期五都有一个固定的会议时间.他们 把自已分成7个委员会,会后再碰头讨论关系公司利益的一些具体问题,分别是: 做广告宣传、留住审稿人、联系新作者,还有财务问题、二手书和新版书、竞争品 种、院校代表等.这就有了本书的第一个例子 例1.1这10名编辑分成7个委员会:c1={1,2,3},C2={1,3,4,5}, {2,5,6,7},e4={4,7,8,9},cs={2,6,7},c6={8,9,10},c={1,3,9,10}.当这10 名编辑在星期五都出席的情形下,为了使这7个委员会都能够成功举行会议,他们 留出3个时间段由于有些编辑参与了两个委员会,所以这些委员会是不能同时开 会的.这种情况可以用图1.1所示的图形象地建立模型 C1 图11个图 在这个图中,用7个小圆圈分别代表7个委员会;如果两个小圆圈所代表的委 员会至少有一个共同的成员,那么在它们之间连一条直线段换句话说,两个小圆圈 委员会)间的直线段告诉我们,这两个委员会不能同时安排开会.这就给出了一个 图或“模型”,它反映了这些委员会以及其成员之间的重叠属性 ◇ 我们在图1.1中所画的就称为一个图.正式地说,图( graph)G是由有限非空 集合V及其二元子集E构成,其中V中元素称为顶点( vertex),E中元素称为边 (edge);集合V和E分别称为G的顶点集( vertex set)和边集( edge set).因 此图G是由V和E构成的二元组实际上是一个有序 ordered)的二元组],记为 G=(V,E)有时把V和E写成V()和E()以强调这些顶点集和边集是属于特 定图G的虽然G是图的一般记号,但也可以用F,H,G",G",G1,G2等记号.顶

...展开详情
试读 127P 10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    上传资源赚积分,得勋章
    最新推荐
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20 50积分/C币 立即下载
    1/127
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第1页
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第2页
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第3页
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第4页
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第5页
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第6页
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第7页
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第8页
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第9页
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第10页
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第11页
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第12页
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第13页
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第14页
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第15页
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第16页
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第17页
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第18页
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第19页
    10565-图灵数学·统计学丛书13-图论导引-[美]加里·查坦德-人民邮电出版社-20第20页

    试读已结束,剩余107页未读...

    50积分/C币 立即下载 >