教学基本要求Р了解:自同构与自同构群的概念,顶点可迁图及其性质,Frucht定理。Р理解:同构的概念,同构关系是一种等价关系。Р掌握:判断两个图是否同构的方法。Р四、重点、难点提示和教学手段Р(一)重点、难点Р1. 判断两个度是否同构的方法。Р2. 从群的角研究图。Р(二)教学手段Р课堂讲授,课堂讨论与习题课相结合Р五、思考与练习Р思考: 1. Cayley图有那些好的性质?Р 2. 图的重构。Р练习由授课老师自行确定Р第四章树Р一、学习目的Р通过本章的学习,掌握树的基本性质和五种等价定义,了解最优生成树提出的实际应用背景,学会简单的图生成树计数方法,能够熟练利用求最优生成树几种算法求解给定图的最优生成树,并解决实际问题。本章计划8学时。Р二、课程内容Р§3.1 树Р树及相关概念,树的的基本性质,树的等价定义及其相互推导。Р§3.2 最小生成树问题Р生成树及相关概念。最优生成树的实际应用背景,避圈法求最优生成树, Kruskal算法及其合理性分析, Prim算法及其合理性分析,破圈法, 利用最优生成树求解实际问题。Р§3.3 最优生成树Р生成树的计数方法,Caylay树公式,矩阵树定理。Р三、教学基本要求Р了解:几种特殊的树,引入最优生成树的实际应用背景,破圈法求最优生成树,Kruskal算法与Prim算法的合理性分析,Caylay树公式,矩阵树定理, Р理解:树等价定义的本质和内在联系, 生成树的相关概念。Р掌握:树的基本性质,树等价定义的相互推导,生成树的计数方法。Р熟练掌握: 利用Kruskal算法和Prim算法求解图的最优生成树。Р四、重点、难点提示和教学手段Р(一)重点、难点Р1. 树的等价定义及其相互推导。Р2. 判断连通图的最小生成树个数。Р3. Kruskal算法和破圈法的合理性分析。Р4.利用最小生成树求解实际问题。Р(二)教学手段Р课堂讲授与习题课相结合
全文预览
