【图论与代数结构】戴一奇.pdf
图论与代数结构 戴一奇胡冠章陈卫
前 言 离散数学是计算机专业的基础数学课程,它以离散量为研究对象,主要包括数理逻 清华大学计算机科学与技术系把离散数学安排为“数理逻辑与集合论”,“图论与代 本书分两大部分,其中一～六章是图论,在第一章介绍了图的基本概念及其代数表 示方法,第二至第六章分别详细讨论了道路与回路、树、平面图与图的着色、匹配与网 络流、图的连通性等图论的主要内容,并且将它们与计算机的应用紧密结合,分析介绍 了众多良好的图算法,给出其正确性证明写复杂度分析,这样,使读者在图的应用及算 法的设计与分析方面能得到较好的训练与培养。
最佳匹配及其算法 最大基数匹配Ford-Fulkerson最大流标号算法 最大流的Edmonds-Karp算法.无向图的DFS算法与图的块划分 6有向图的DFS算法与强连通块划分 变换群和置换群Caylay定理 8.