应用图论：带有图优化和代数图论的引介

这本书作为图论及其应用的引介而编写。它是为高年级本科生的图论课程设计的，但也适用于科学或工程专业的初级研究生。该书严格（基于证明）地介绍了图论，同时也讨论了利用这些结果解决实际感兴趣问题的应用。本书分为四个部分。 第一部分涵盖了图论的组合方面，包括常用词汇的讨论、顶点和边割的讨论、欧拉游览、哈密顿路径以及树的表征。这导致了第二部分，该部分讨论了常见的组合优化问题。生成树、最短路径问题和拟阵都有讨论，最大流问题也是如此。第二部分以图着色和着色问题的NP完全性证明作为结尾。 第三部分向读者介绍代数图论，并重点讨论马尔可夫链、中心性计算（例如，特征向量中心性和页面排名）以及谱图聚类和图拉普拉斯算子。 第四部分包含了关于线性规划的额外材料，用于提供最大流问题的另一种分析。还提供了两个附录，其中包含了线性代数和概率论的先决条件材料。