图论导引(原书第2版) 典藏版 机械工业出版社 下载 pdf 百度网盘 epub 免费 2025 电子书 mobi 在线

本书全面介绍了图论的基本概念、基本定理和算法，帮助读者理解并掌握图的结构和的技巧.另外，书中包含很多图论的新研究成果，并介绍了一些悬而未决的图论问题，证明与应用并举是本书的一个重要特点，书中对所有定理和命题给出了完整的证明，同时讨论了大量的提供了1200多道习题。本书可以作为高等院校数学系本科生和研究生、计算机专业和其他专业研究生的图可以作为有关教师和工程技术人员的参考书。

译者序

前言

符号表

第1章 基本概念

1.1 什么是图

定义

图模型

矩阵和同构

分解和特殊图

习题

1.2 路径、环和迹

图的连通性

二部图

欧拉回路

习题

1.3 顶点度和计数

计数和双射

极值问题

图序列

习题

1.4 有向图

定义和例子

顶点度

欧拉有向图

定向和竞赛图

习题

第2章 树和距离

2.1 基本性质

树的性质

树和图中的距离

不相交生成树（选学）

习题

2.2 生成树和枚举

树的枚举

图的生成树

分解和优美标记

分叉和欧拉有向图（选学）

习题

2.3 很优化和树

最小生成树

最短路径

计算机科学中的树（选学）

习题

第3章 匹配和因子

3.1 匹配和覆盖

优选匹配

Hall匹配条件

最小-优选定理

独立集和覆盖

支配集（选学）

习题

3.2 算法和应用

优选二部匹配

加权二部匹配

稳定匹配（选学）

快速二部匹配（选学）

习题

3.3 一般图中的匹配

Tutte 1-因子定理

图的f-因子（选学）

Edmonds开花算法（选学）

习题

第4章 连通度和路径

4.1 割和连通度

连通度

边-连通度

块

习题

4.2 k-连通图

2-连通图

有向图的连通度

k-连通图和k-边连通图

Menger定理的应用

习题

4.3 网络流问题

优选网络流

整数流

供应和需求（选学）

习题

第5章 图的着色

5.1 顶点着色和上界

定义和实例

上界

Brooks定理

习题

5.2 k-色图的结构

大色数图

极值问题和Turan定理

颜色-临界图

强制细分

习题

5.3 计数方面的问题

真着色的计数

弦图

完美图点滴

无环定向的计数（选学）

习题

第6章 可平面图

6.1 嵌入和欧拉公式

平面作图

对偶图

欧拉公式

习题

6.2 可平面图的特征

Kuratowski定理的预备知识

凸嵌入

可平面性测试（选学）

习题

6.3 可平面性的参数

可平面图的着色

交叉数

具有更高亏格的表面（选学）

习题

第7章 边和环

7.1 线图和边着色

边着色

线图的特征（选学）

习题

7.2 哈密顿环

必要条件

充分条件

有向图中的环（选学）

习题

7.3 可平面性、着色和环

Tait定理

Grinberg定理

鲨鱼图（选学）

流和环覆盖（选学）

习题

第8章 其他主题（选学）

8.1 完美图

完美图定理

弦图的再研究

其他类型的完美图

非完美图

强完美图猜想

习题

8.2 拟阵

遗传系统和示例

拟阵的性质

生成函数

拟阵的对偶性

拟阵的子式和可平面图

拟阵的交

拟阵的并

习题

8.3 Ramsey理论

鸽巢原理的再研究

Ramsey定理

Ramsey数

关于图的Ramsey理论

Sperner引理和带宽

习题

8.4 其他极值问题

图的编码

分叉和流言

序列着色和可选择性

使用路径和环的划分

周长

习题

8.5 随机图

存在性和期望值

几乎所有图均具有的性质

阈值函数

演变和图参数

连通度、团和着色

鞅

习题

8.6 图的特征值

特征多项式

实对称矩阵的线性代数

特征值和图参数

正则图的特征值

特征值和扩张图

强正则图

习题

附录A 数学基础

附录B 很优化和复杂度

附录C 部分习题的提示

附录D 术语表

附录E 补充阅读材料

附录F 参考文献

道格拉斯·B.韦斯特（Douglas B.West），美国伊利诺伊大学厄巴纳分校数学系教授。1978年他于马萨诸塞理工学院获得数学专业博士学位。他的研究方向为离散数学中的极值问题、结构问题以及算法问题。除本书外，他还著有《Mathematical Thinking:Problem-Solving and Proofs》《Combinatorial Mathematics》和《The Art of Combinatorics》等书。

暂无出版社相关信息，正在全力查找中！

暂无相关书籍摘录，正在全力查找中！

在线阅读地址：图论导引(原书第2版) 典藏版 机械工业出版社在线阅读

在线听书地址：图论导引(原书第2版) 典藏版 机械工业出版社在线收听

在线购买地址：图论导引(原书第2版) 典藏版 机械工业出版社在线购买

暂无原文赏析，正在全力查找中！

前言

图论是训练离散数学证明技巧的乐园,其结果在计算科学、社会科学和自然科学等多个领域具有广泛应用.本书可作为本科生或低年级研究生1~2个学期的图论课程的教材.本书不要求任何图论的预备知识.尽管本书包含许多算法和应用,但重点是理解图的结构和解决图论问题的技巧目前已经有许多图论的教科书.由J.A. Bondy和U.SR. Murty撰写的优秀教材《 Graph Theorywith Applications,( Macmillan/ North- Holland1976])把重点放在证明和应用两个方面,本书的草稿参照了该书.图论至今仍是一门年轻的学科,应该如何介绍图论的题材,大家仍然没有一致的看法主题的挑选和顺序的安排,证明方法、目标和基本题目的选择等,一直是众说纷纭.作者在多次修改本书的过程中认识到,对于这些问题做决定是很困难的.本书是作者对这些争议的一点贡献第2版的修订主要是为了更易于学生学习和更便于教师教学.本书的总体内容没有很大的变化,但是对内容的表述方式做了修改,使其更容易理解,这一点在本书的前儿部分尤其明显.有关版所做的某些修改,稍后将详细讨论,此处仅做一下概述非选学节中的选学材料现在用号标明.这些内容不会在后续内容中使用,因而可以跳过多数选修内容忽略以后,本书可以作为一学期的图论教学内容.如某一小节标记为“选学”则整个小节的内容都是可选修的,而不再标记该小节中的各个项·对于缺乏基础知识的学生,附录A概述了有关集合、逻辑、归纳法、计数、二项式系数关系和鸽巢原理等方面的相关知识对于很多证明都重新进行了更细致的叙述,并增加了更多的例子增加了350多道习题,其中多数是第1~7章中的比较容易的题目.这样,本书的总习题量超过了1200道增加了100多幅插图.本书的插图总量超过了400幅.为区别插图中包括的几种类型的边书中把原有的实线和虚线改变为粗线和实线,增加了插图的清晰度相对简单的问题都集中放在各节习题的前面部分,用来作为热身练习.一些习题进行了改写,使其语义更加清楚对习题的提示做了补充,增加了一个“部分习题的提示”的附录·为了易于查找,概念术语都用黑体字给出,其中绝大多数都出现在概念定义中·为了易于查找,将术语集中在附录D中有关欧拉回路、有向图和 Turan定理的内容经过了重新编排,以提高学习效率·第6章和第7章交换了顺序以便先介绍平面性的思想,与复杂性有关的部分经过改编安排在附录中·改正了专业术语的错误,并更加强调与本书内容直接相关的术语特点本书特点就是使学生能够深入理解本书的内容,本书包括对证明技巧的讨论、1200多道习题400多幅插图以及许多例子,本书正文中出现的结论都有详细完整的证很多本科生在开始学习图论前很少涉足证明技巧,附录A提供的背景阅读材料有助于初学者提高这方面的技巧.如果初学者在理解和书写证明时有困难,请结合第1章仔细阅读附录A.虽然本书前面的一些章节仍然讨论了一些证明技巧(特别是归纳法),但是更多的背景知识(特别是集合函数、关系和初等计数)已经安排在附录A中大多数习题都需要证明.很多本科生在论证问题方面的实践不足,这将影响他们对于图论和其他数学知识的兴趣,即使抛开数学,论证问题方面的智能训练也是极其重要的,作者希望学生喜欢这种训练,在求解问题时,学生应该注意语言的使用(“说出的即是你要表达的”),而且表达准确(“表达的即是你要说出的虽然图论中许多术语本身就表明了它们各自的定义,但太多的专业术语定义会影响内容的可读性,数学家喜欢一开始就给出一系列定义,但学生们大都愿意熟练掌握一个概念后再去接受下一个概念,这样他们会学得更好.学生的这个意愿和审稿者的建议使作者推迟了很多定义的给出,直到需要的时候.例如,笛卡儿积的定义在5.1节的着色问题部分给出,线图的定义则分别在4.2节的 Menger定理部分和7.1节的边着色部分给出,诱导子图的定义和连接的定义分别推迟到1.2节和3.1节给出书中已经改变了对有向图介绍的位置,将其推迟到了1.4节.如果在介绍图的同时介绍有向图,会使学生产生迷惑.在第1章的最后介绍有向图相对容易学习,学生能够在了解两种图的差别的同时加强对基本概念的理解.在连通性问题上,本书仍会将这两个模型放在一起讨论本书比其他图论书籍包含了更多的内容,作为“其他主题”的可选章节,最后一章汇集了很多图论近期新研究结果,使得本书适合不同层次的读者使用.本科生的教学内容可以由前七章组成(去掉大部分选学内容),第8章可作为对相应主题感兴趣的学生的阅读材料.研究生的教学内容可以采用如下结构:第1章和第2章作为推荐阅读材料,在课堂上快速进入第3章,并讲授第8章的一些主题.第8章以及前面章节的选学内容也可作为高级图论课程的基本内容很多图论中的结论都有多个证明,这样有助于提高学生采用多种方法处理问题的灵活性.对于同一个问题,本书可能在注记中谈及一些不同的证明方法,另外一些留作练习很多习题都有提示,一些提示在习题中直接给出,另一些在附录C中给出.标记了“一”的问题简单,标记了“艹”的问题比较难,标记了“+”的问题不应该作为本科生的作业.标记了“!”的则特别有价值、有启发性或有趣.标记了“*”的问题涉及可选内容每节习题都以标记“一”的问题开始,根据相关章节内容的先后顺序排列,这部分问题的结束由组点来标记.这部分问题要么是检查对概念的理解,要么是对相关章节内容的结论的直接应用作者在课堂上推荐一些这样的问题作为热身练习,在完成主要的作业题(多数这样的习题标记了!”)之前检査学生对基本概念的理解,多数标记“一”的问题是很好的考试题.如果在考试中使用其他习题,从附录C中选取一些提示是很好的做法涉及多个概念的习题在最后一个相关概念介绍完之后给出.正文中一个概念介绍完后有时会有指针指向与该概念相关的习题.全书有很多这样的指针,每一节对本节习题的引用仅由该习题在这节的习题中的相对编号给出,对其他习题的交叉引用将通过其章、节和习题编号给出组织和修改本书第1版力求内容的承接关系以及证明难度和算法复杂性循序渐进在第2版中,本书继续保持这种风格.欧拉回路和哈密顿环仍在不同章节,并且离得更远·欧拉回路的简单介绍在1.2节,其中包括了与之密切相关的材料.原来2.4节的部分内容移到其他章节的相关部分,并删除了 Fleury算法