图论导引（英文版·原书第2版·典藏版）
| 作者 |
| [美]道格拉斯·B.韦斯特（Douglas B.West） |
| 丛书名 |
| 华章数学原版精品系列 |
| 出版社 |
| 机械工业出版社 |
| ISBN |
| 9787111653592 |
| 简要 |
| 简介 |
| 内容简介书籍数学书籍 本书全面介绍了图论的基本概念、基本定理和算法，帮助读者理解并掌握图的结构和解决图论问题的技巧。另外，书中包含很多图论的新研究成果，并介绍了一些悬而未决的图论问题。证明与应用并举是本书的一个重要特点，书中对所有定理和命题给出了完整的证明，同时讨论了大量的实例和应用，并提供了1 200多道习题。本书可以作为高等院校数学系本科生和研究生、计算机专业和其他专业研究生的图论课程教材，也可以作为有关教师和工程技术人员的参考书。 |
| 目录 |
| 第1章 基本概念 1 1.1 什么是图 1 定义 1 图模型 3 矩阵和同构 6 分解和特殊图 11 习题 14 1.2 路径、环和迹 19 图的连通性 20 二部图 24 欧拉回路 26 习题 31 1.3 顶点度和计数 34 计数和双射 35 极值问题 38 图序列 44 习题 47 1.4 有向图 53 定义和例子 53 顶点度 58 欧拉有向图 60 定向和竞赛图 61 习题 63 第2章 树和距离 67 2.1 基本性质 67 树的性质 68 树和图中的距离 70 不相交生成树（选学） 73 习题 75 2.2 生成树和枚举 81 树的枚举 81 图的生成树 83 分解和优美标记 87 分叉和欧拉有向图（选学） 89 习题 92 2.3 最优化和树 95 最小生成树 95 最短路径 97 计算机科学中的树（选学） 100 习题 103 第3章 匹配和因子 107 3.1 匹配和覆盖 107 最大匹配 108 Hall匹配条件 110 最小–最大定理 112 独立集和覆盖 113 支配集（选学） 116 习题 118 3.2 算法和应用 123 最大二部匹配 123 加权二部匹配 125 稳定匹配（选学） 130 快速二部匹配（选学） 132 习题 134 3.3 一般图中的匹配 136 Tutte 1-因子定理 136 图的f-因子（选学） 140 Edmonds开花算法（选学） 142 习题 145 第4章 连通度和路径 149 4.1 割和连通度 149 连通度 149 边–连通度 152 块 155 习题 158 4.2 k–连通图 161 2–连通图 161 有向图的连通度 164 k–连通图和k–边连通图 166 Menger定理的应用 170 习题 172 4.3 网络流问题 176 最大网络流 176 整数流 181 供应和需求（选学） 184 习题 188 第5章 图的着色 191 5.1 顶点着色和上界 191 定义和实例 191 上界 194 Brooks定理 197 习题 199 5.2 k–色图的结构 204 大色数图 205 极值问题和Turán定理 207 颜色–临界图 210 强制细分 212 习题 214 5.3 计数方面的问题 219 真着色的计数 219 弦图 224 完美图点滴 226 无环定向的计数（选学） 228 习题 229 第6章 可平面图 233 6.1 嵌入和欧拉公式 233 平面作图 233 对偶图 236 欧拉公式 241 习题 243 6.2 可平面图的特征 246 Kuratowski定理的预备知识 247 凸嵌入 248 可平面性测试（选学） 252 习题 255 6.3 可平面性的参数 257 可平面图的着色 257 交叉数 261 具有更高亏格的表面（选学） 266 习题 269 第7章 边和环 273 7.1 线图和边着色 273 边着色 274 线图的特征（选学） 279 习题 282 7.2 哈密顿环 286 必要条件 287 充分条件 288 有向图中的环（选学） 293 习题 294 7.3 可平面性、着色和环 299 Tait定理 300 Grinberg定理 302 鲨鱼图（选学） 304 流和环覆盖（选学） 307 习题 314 第8章 其他主题（选学） 319 8.1 完美图 319 完美图定理 320 弦图的再研究 323 其他类型的完美图 328 非完美图 334 强完美图猜想 340 习题 344 8.2 拟阵 349 遗传系统和示例 349 拟阵的性质 354 生成函数 358 拟阵的对偶性 360 拟阵的子式和可平面图 363 拟阵的交 366 拟阵的并 369 习题 372 8.3 Ramsey理论 378 鸽巢原理的再研究 378 Ramsey定理 380 Ramsey数 383 关于图的Ramsey理论 386 Sperner引理和带宽 388 习题 392 8.4 其他极值问题 396 图的编码 397 分叉和流言 404 序列着色和可选择性 408 使用路径和环的划分 413 周长 416 习题 422 8.5 随机图 425 存在性和期望值 426 几乎所有图均具有的性质 430 阈值函数 432 演变和图参数 436 连通度、团和着色 439 鞅 442 习题 448 8.6 图的特征值 452 特征多项式 453 实对称矩阵的线性代数 456 特征值和图参数 458 正则图的特征值 460 特征值和扩张图 463 强正则图 464 习题 467 附录A 数学基础 471 附录B 最优化和复杂度 493 附录C 部分习题的提示 507 附录D 术语表 515 附录E 补充阅读材料 533 附录F 参考文献 567 作者索引 569 术语索引 575 Contents Prefacexi Chapter 1 Fundamental Concepts 1.1 What Is a Graph The Definition, 1 Graphs as Models, 3 Matrices and Isomorphism, 6 Decomposition and Specia] Graphs, 11 Exercises, 14 1.2 Paths, Cycles, and Trails 19 Connection in Graphs, 20 Bipartite Graphs, 24 Eulerian Circuits, 26 Exercises, 31 1.3 Vertex Degrees and Counting 34 Counting and Bijections, 35 Extremal Problems, 38 Graphic Sequences, 44 Exercises, 47 1.4 Directed Graphs 53 Definitions and Examples, 53 Vertex Degrees, 58 Eulerian Digraphs, 60 Orientations and Tournaments, 61 Exercises, 63 Chapter 2 Trees and Distance 2.1 Basic Properties Properties of Trees, 68 Distance in Trees and Graphs, 70 Disjoint Spanning Trees (optional), 73 Exercises, 75 2.2 Spanning Trees and Enumeration Enumeration of Trees, 81 Spanning Trees in Graphs, 83 Decomposition and Graceful Labelings, 87 Branchings and Eulerian Digraphs (optional), 89 Exercises, 92 2.3 Optimization and Trees Minimum Spanning Tree, 95 Shortest Paths, 97 Trees in Computer Science (optional)，100 Exercises, 103 Chapter 3 Matchings and Factors 3.1 Matchings and Covers Maximum Matchings, 108 Hall's Matching Condition Min-Max Theorems, 112 Independent Sets and Covers, 113 Dominating Sets (optional), 116 Exercises, 118 3.2 Algorithms and Applications Maximum Bipartite Matching, 123 Weighted Bipartite Matching, 125 Stable Matchings (optional), 130 Faster Bipartite Matching (optional), 132 Exercises, 134 3.3 Matchings in General Graphs Tutte's 1-factor Theorem, 136 f-factors of Graphs (optional), 140 Edmonds' Blossom Algorithm (optional) Exercises, 145 Chapter 4 Connectivity and Paths 4.1 Cuts and Connectivity Connectivity, 149 Edge-connectivity,152 Blocks, 155 Exercises, 158 4.2 k-connected Graphs 2-connected Graphs, 161 Connectivity of Digraphs, 164 k-connected and k-edge-connected Graphs,166 Applications of Menger's Theorem, 170 Exercises, 172 4.3 Network Flow Problems Maximum Network Flow, 176 Integral Flows, 181 Supplies and Demands (optional), 184 Exercises, 188 Chapter 5 Coloring of Graphs 5.1 Vertex Colorings and Upper Bounds Definitions and Examples, 191 Upper Bounds, 194 Brooks' Theorem, 197 Exercises, 199 5.2 Structure of k-chromatic Graphs Graphs with Large Chromatic Number, 205 Extremal Problems and Tur~n's Theorem 207 Color-Critical Graphs, 210 Forced Subdivisions, 212 Exercises, 214 5.3 Enumerative Aspects Counting Proper Colorings, 219 Chordal Graphs, 224 A Hint of Perfect Graphs, 226 Counting Acyclic Orientations (optional), 228 Exercises, 229 Chapter 6 Planar Graphs 6.1 Embeddings and Euler's Formula Drawings in the Plane, 233 Dual Graphs, 236 Euler's Formula, 241 255 Exercises, 243 6.2 Characterization of Planar Graphs Preparation for Kuratowski's Theorem, 247 Convex Embeddings, 248 Planarity Testing (optional), 252 Exercises, 255 6.3 Parameters of Planarity Coloring of Planar Graphs, 257 Crossing Number, 261 Surfaces of Higher Genus (optional), 266 Exercises, 269 Chapter 7 Edges and Cycles 7.1 Line Graphs and Edge-coloring Edge-colorings, 274 Characterization of Line Graphs (optional), 279 Exercises, 282 7.2 Hamiltonian Cycles Necessary Conditions, 287 Sufficient Conditions, 288 Cycles in Directed Graphs (optional),293 Exercises, 294 7.3 Planarity, Coloring, and Cycles Tait's Theorem, 300 Grinberg's Theorem, 302 Snarks (optional), 304 Flows and Cycle Covers (optional), 307 Exercises, 314 Chapter 8 Additional Topics (optional)319 8.1 Perfect Graphs 319 The Perfect Graph Theorem, 320 Chordal Graphs Revisited, 323 Other Classes of Perfect Graphs, 328 Imperfect Graphs, 334 The Strong Perfect Graph Conjecture, 340 Exercises, 344 8.2 Matroids 349 Hereditary Systems and Examples, 349 Properties of Matroids, 354 The Span Function, 358 The Dual of a Matroid, 360 Matroid Minors and Planar Graphs, 363 Matroid Intersection, 366 Matroid Union, 369 Exercises, 372 8.3 Ramsey Theory378 The Pigeonhole Principle Revisited, 378 Ramsey's Theorem, 380 Ramsey Numbers, 383 Graph Ramsey Theory, 386 Sperner's Lemma and Bandwidth, 388 Exercises, 392 8.4 More Extremal Problems 396 Encodings of Graphs, 397 Branchings and Gossip, 404 List Coloring and Choosability, 408 Partitions Using Paths and Cycles, 413 Circumference, 416 Exercises, 422 8.5 Random Graphs 425 Existence and Expectation, 426 Properties of Almost All Graphs, 430 Threshold Functions, 432 Evolution and Graph Parameters, 436 Connectivity, Cliques, and Coloring, 439 Martingales, 442 Exercises, 448 8.6 Eigenvalues of Graphs The Characteristic Polynomial, 453 Linear Algebra of Real Symmetric Matrices, 456 Eigenvalues and Graph Parameters, 458 Eigenvalues of Regular Graphs, 460 Eigenvalues and Expanders, 463 Strongly Regular Graphs, 464 Exercises, 467 Appendix A Mathematical Background Appendix B Optimization and Complexity Appendix C Hints for Selected Exercises Appendix D Glossary of Terms Appendix E Supplemental Reading Appendix F References Author Index Subject Index |
有问题微信扫码联系