研究生课程教学大纲 把线性代数和矩阵理论的知识与图论联系起来，这是代数图论的一个主要研究方向， 如应用关联矩阵证明握手定理就是一个很好的例子 (2)通过应用图同构方法识别NaNiO2晶体的不同构型的例子说明图同构方法在其它学科也 有重要应用. (3)许多化学物质的结晶体呈正多面体的形状，如食盐的结晶体是正六面体，明矾的结晶 体是正八面体.正多面体的研究可以追溯到柏拉图时代.柏拉图视“四古典元素”为元 素，其形状如正多面体中的其中四个.正多面体的研究还与著名的欧拉多面体公式有关 (正多面体只有5种). (4)超立方是一种重要的图类（可由三种等价的方式定义，即集合方法，序列方法， Cartesian乘积方法).由于对称性好，连通度高等特点得到了广泛研究，特别是，超立 方还是一种互连网络拓扑结构. 第二章：树(6学时) 1本章教学内容： (1)树的概念与性质(2学时)，(2)生成树(2学时)，(2)最小生成树(2学时)。 2本章教学要求： 通过本章课程的学习，要求学生理解树的理论与实际意义，掌握树的概念与性质，生成树， 最小生成树算法。 3本章教学重点：(1)树的概念与性质，(2)最小生成树算法及应用。 4本章教学难点：克鲁斯克尔算法证明。 课程思政： (1)树不仅是一种结构相对简单的图类（很多时候作为一些结论是试验田），而且在其它领 域有应用.英国数学家Arthur Cayley 1875年用树的模型研究了化学同分异构体的计数 问题：早在l9世纪，物理学家Kirchhoff就己经注意到电路中的独立回路与该电路中 所谓生成树的关系，进而发现了Kirchhoff电流定律；树还是一种特殊的网络拓扑模型 与数据存储模型（特别是二叉树） (2)Jordan定理事实上给出一个算法可以求树的半径和中心（只有一个中心点时是剪叶的次 数，两个中心点时是剪叶的次数+1)，该定理对应该布局在区域中心的资源配置有指导 作用，如确定社区医院的修建位置，就可以建模求图的中心. (3)Radia Joy Perlman于1981年设计了生成树协议.该协议是工作在OSI网络模型中的第 二层（数据链路层）的通信协议，防止交换机冗余链路产生的环路.用于确保以太网中 2研究生课程教学大纲 2 把线性代数和矩阵理论的知识与图论联系起来, 这是代数图论的一个主要研究方向, 如应用关联矩阵证明握手定理就是一个很好的例子. (2) 通过应用图同构方法识别 NaNiO2晶体的不同构型的例子说明图同构方法在其它学科也 有重要应用. (3) 许多化学物质的结晶体呈正多面体的形状, 如食盐的结晶体是正六面体, 明矾的结晶 体是正八面体. 正多面体的研究可以追溯到柏拉图时代. 柏拉图视“四古典元素”为元 素，其形状如正多面体中的其中四个. 正多面体的研究还与著名的欧拉多面体公式有关 (正多面体只有 5 种). (4) 超立方是一种重要的图类(可由三种等价的方式定义, 即集合方法, 序列方法, Cartesian 乘积方法). 由于对称性好, 连通度高等特点得到了广泛研究, 特别是, 超立 方还是一种互连网络拓扑结构. 第二章：树(6 学时) 1 本章教学内容： (1)树的概念与性质（2 学时），(2) 生成树（2 学时），(2) 最小生成树（2 学时）。 2 本章教学要求： 通过本章课程的学习，要求学生理解树的理论与实际意义，掌握树的概念与性质，生成树， 最小生成树算法。 3 本章教学重点：（1）树的概念与性质，（2）最小生成树算法及应用。 4 本章教学难点：克鲁斯克尔算法证明。 课程思政: (1) 树不仅是一种结构相对简单的图类(很多时候作为一些结论是试验田), 而且在其它领 域有应用. 英国数学家 Arthur Cayley 1875 年用树的模型研究了化学同分异构体的计数 问题; 早在 19 世纪，物理学家 Kirchhoff 就已经注意到电路中的独立回路与该电路中 所谓生成树的关系, 进而发现了 Kirchhoff 电流定律; 树还是一种特殊的网络拓扑模型 与数据存储模型(特别是二叉树). (2) Jordan 定理事实上给出一个算法可以求树的半径和中心(只有一个中心点时是剪叶的次 数, 两个中心点时是剪叶的次数+1), 该定理对应该布局在区域中心的资源配置有指导 作用, 如确定社区医院的修建位置，就可以建模求图的中心. (3) Radia Joy Perlman 于 1981 年设计了生成树协议. 该协议是工作在 OSI 网络模型中的第 二层(数据链路层)的通信协议, 防止交换机冗余链路产生的环路. 用于确保以太网中