图论导引

《图论导引(第二版)》给鲜树菜使久宜是2014年电来自子工业出版社出版的图书。

• 中文名 图论导引(第二版)
• 外文名 Introduction to Graph Theoty(Second Edition)

图书信息

　　著 者:Douglas B. West(道格拉斯 B.韦斯特)

　　作 译 者:骆吉检洲,李建中

　　出版时间:演老补器飞才个需跟触终2014-10

　　千 字 数:736

内容简介

　　本书系统地介绍了图论的基本概念、基本定理和算法，同时还介绍了一些悬而未决的图论问题和图论的新研究成果，旨在帮银乱助读者理解并掌握图的结构和解决图论问题的技巧。

　　全书包含8章和7个附录。第1~4章介预刘慢初介绍图的概念、树和距离、匹配问题和图的分解问题、图的连通性等基本内容;第5~8章分别介绍了组合图论、拓扑图论的知识，图论中的边和环，以及图论来自的其他主题。书中配有大量例题和超过1200道习题，使读者容易理解书中的概念和定理，并掌握证明技巧。本书内容丰富，具有很360百科多可选择阅读的章节，可以环等与众附属在够供不同层次的读者使用。

目 录

　　第1章 基本概念

　　11 什么是图

　　1.1.1 定义

　　1.1.2 图模型

　　1.1.3 矩阵与同构

　　1.1.4 分解和特殊图

　　1.1.5 习题

　　12 路径、 环和迹

　　1.2.1 图的连通

　　1.2.2 二分图

　　1践述浓减通.2.3 欧拉回路

　　1.2.4 习题

　　13 顶点度和计数

　　1.3.1 计数和双射

　　1.3.2 极值问题

　　1.3.3 图解序列

　　1.3.4 习题

　　14 有向图

　于因没呀工都单越红　1.4.1 定义和例子

　　1.4.2 顶点度

　　1.4.3 欧拉有向图

　另命治殖沿满伯　1.4.4 定向图和竞赛图

　　1.4.5 习题

　　第2章 树和距离

　　21 基本性质

　　2.1.1 树的性质

　　2突伤格斯力原.1.2 树和图中的距离

　　2.1.3 不相交生成树(选学)

　　2.1.4 习题

　　22 生成树和枚举

　　2.2.1 树的枚举

　　2.2.2 图的生成树

　　2.2.3 分解和优美标记

载县民轻全电期呀段务　　2.2.4 分叉与欧拉有向图

　　(选学)

　　2.2.5 习题

　　23 优化和树

　　2.3.1 最小生成树

　　2.来自3.2 最短路径

　　2.3.3 计算机科学中的树

　　(选学)

　　2.3.4 习题

　　第3章 匹配和因子

　　31 匹配与覆盖

　　3.1.1 最大匹配

　　3.1.2 Hall匹配条件

　　3.1.3 最小最大定理

　　3.1.4 独立集与覆盖

　　3.1.5 支配集吗比镇连挥万不(选学)

　　3.1.6 习诗庆属艺条题

　　32 算法及应用

　　3.2.1 最大二分匹配

　　3.2.2 加权二分360百科匹配

　　3.2.3 稳定匹配(选学)

　　3.2.4 快速二分匹配(选学)

　　3.2.5 习题

　　3活识征线感他矛3 一般图中的匹配

　　3.3.帮下院甚报排评挥开爱扬1 Tutte 1因子定理

　　3.3.2 图的f因子(选学)

　　3.3.3 Edmonds开花算法

　　(选学)

　　3.3.4 习题

　　第4章 连通度和路径

　　41 割与连通度

　　4.1.1 连通度

　　4.1.2 边连通度通常

　　4.1.3 块

　　42 k通图

　　4.2.1 2连通图

　　4.2.2 有向五阳那策喜何袁谈械天许图的连通度

　　4.2顾卷席风画巴院差.3 k通图与k边连通图

　　4.2.4 Menger定理的应用

　　4.2.5 习题

　　43 网络流问题

　　4.3.1 最大网络流

　　4.3.2 整数流

　　4.3.3 供应与需求(选次易免究学)

　　4.3.4 习题

　　第5章 图的着色

　　51 顶点着色和上界

　　5.1.1 定义和实例

　　5.1.2 上界

　　手该5.1.3 Brooks定理

　　5.1.4 习算星席念父照爱题

　　52 k色图的构造

　　5.2.1 大色数图

　　5.2.2 极值问题与Turn

　　定理

　　5.2.3 颜色立复构河留际势临界图

　　5.2.4 强制细分

　　5.2.5 抗华象降财空错习题

　　53 计缩施个具算分硫居章数方面的问题

　　5.3.1 真着色的计数

　　5.3.2 弦图

　　5.3.3 完美图点滴

　　5.3.4 无七固布杂原概计爱苗记环定向的计数

　　(选学)

　　5.3.5 习题

　　第6章 可平面图

　　61 嵌入与欧拉公式

　　6.1.1 平面作图

　　6.1.2 对偶图

　　6.1.3 欧拉(Euler)公式

　　6.1.4 习题

　　62 可平面图的特征

　　6.2.1 Kuratowski定理的

　　预备知识

　　6.2.2 凸嵌入

　　6.2.3 可平面性的测试

　　(选学)

　　6.2.4 习题

　　63 可平面性的参数

　　6.3.1 可平面图的着色

　　6.3.2 交叉数

　　6.3.3 具有更高亏格的表面

　　(选学)

　　6.3.4 习题

　　第7章 边和环

　　71 线图与边着色

　　7.1.1 边着色

　　7.1.2 线图的性质(选学)

　　7.1.3 习题

　　72 哈密顿环

　　7.2.1 必要条件

　　7.2.2 充分条件

　　7.2.3 有向图中的环(选学)

　　7.2.4 习题

　　73 可平面性、 着色与环

　　7.3.1 Tait定理

　　7.3.2 Grinberg定理

　　7.3.3 鲨鱼图(选学)

　　7.3.4 流与环覆盖(选学)

　　7.3.5 习题

　　第8章 其他主题

　　81 完美图

　　8.1.1 完全图定理

　　8.1.2 弦图的再研究

　　8.1.3 其他完美图类

　　8.1.4 非完美图

　　8.1.5 强完美图猜想

　　8.1.6 习题

　　82 拟阵

　　8.2.1 遗传系统及示例

　　8.2.2 拟阵的性质

　　8.2.3 生成函数

　　8.2.4 拟阵的对偶

　　8.2.5 拟阵的子式与可

　　平面对偶

　　8.2.6 拟阵的交

　　8.2.7 拟阵的并

　　8.2.8 习题

　　83 拉姆齐理论

　　8.3.1 鸽巢原理的再研究

　　8.3.2 拉姆齐(Ramsey)定理

　　8.3.3 拉姆齐数

　　8.3.4 图的拉姆齐理论

　　8.3.5 Sperner引理和带宽

　　8.3.6 习题

　　84 其他极值问题

　　8.4.1 图的编码

　　8.4.2 分叉和流言

　　8.4.3 序列着色和可选择性

　　8.4.4 由路径和环构成的

　　划分

　　8.4.5 周长

　　8.4.6 习题

　　85 随机图

　　8.5.1 存在性和数学期望

　　8.5.2 几乎所有图均具有的

　　性质

　　8.5.3 阈值函数

　　8.5.4 图的演变和图的参数

　　8.5.5 连通度、 团和着色

　　8.5.6 鞅

　　8.5.7 习题

　　86 图的特征值

　　8.6.1 特征多项式

　　8.6.2 线性代数和实对称阵

　　8.6.3 特征值和图参数

　　8.6.4 正则图的特征值

　　8.6.5 特征值与扩张图

　　8.6.6 强正则图

　　8.6.7 习题

　　附录A 数学基础

　　附录B 最优化和复杂度

　　附录C 部分习题提示

　　附录D 术语表

　　附录E 补充阅读

　　附录F 参考文献

　　附录G 术语对照表