- 机械工业出版社
- 9787111641940
- 1-6
- 283953
- 46258059-8
- 平装
- 16开
- 2019-12
- 778
- 492
- 理学
- 数学
- 数学与应用数学
- 本科
作者简介
内容简介
本书全面介绍了图论的基本概念、基本定理和算法，帮助读者理解并掌握图的结构和解决图论问题的技巧. 另外，书中包含很多图论的新研究成果，并介绍了一些悬而未决的图论问题. 证明与应用并举是本书的一个重要特点，书中对所有定理和命题给出了完整的证明，同时讨论了大量的实例和应用，并提供了1 200多道习题.
本书可以作为高等院校数学系本科生和研究生、计算机专业和其他专业研究生的图论课程教材，也可以作为有关教师和工程技术人员的参考书.
目录
译者序前言符号表第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.2k-连通图2-连通图有向图的连通度k-连通图和k-边连通图Menger定理的应用习题4.3网络流问题最大网络流整数流供应和需求(选学)习题第5章图的着色5.1顶点着色和上界定义和实例上界Brooks定理习题5.2k-色图的结构大色数图极值问题和Turn定理颜色-临界图强制细分习题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.3Ramsey理论鸽巢原理的再研究Ramsey定理Ramsey数关于图的Ramsey理论Sperner引理和带宽习题8.4其他极值问题图的编码分叉和流言序列着色和可选择性使用路径和环的划分周长习题8.5随机图存在性和期望值几乎所有图均具有的性质阈值函数演变和图参数连通度、团和着色鞅习题8.6图的特征值特征多项式实对称矩阵的线性代数特征值和图参数正则图的特征值特征值和扩张图强正则图习题附录A数学基础附录B最优化和复杂度附录C部分习题的提示附录D术语表附录E补充阅读材料附录F参考文献
