· 学校主页    · 学院主页

《图论》

发布时间:2011-03-17  浏览次数:1395

 

 

图 论

 

一、课程基本信息
课程编号:0906044
课程中文名称:图论导引

课程英文名称:Introduction to Graph Theory
课程性质:通识教育选修
考核方式:考查
开课专业:全校
开课学期:2
总学时:32
总学分:1.5

授课教师潘海为、张可佳



二、课程目的和任务
本课程是计算机科学与技术专业的专业任选课,本课程的目的是从图论的理论与实践出发培养学生运用图论的相关理论与算法解决实际问题的能力,从而能够与ACM大学生程序设计竞赛这个平台相结合提高学生的创新能力。通过本课程的学习,使学生了解图论的基本定义与理论进而理解能够在竞赛中运用的图论的经典算法。

三、教学基本要求(含素质教育与创新能力培养的要求)
通过本课程学习,学生应在知识和技能两方面达到要求:
知识方面----理解图论的基本定理、定义及经典算法,并能够理解算法的思想及证明。
技能方面----根据提出问题的特点,能够选择恰当的图论算法对问题求解并对求解过程进行优化,进而能够不断的在竞赛的过程中提高自身能力。

四、教学内容与学时分配

 
   第1章 基本概念6学时)
1.1 相关概念及图论概述 (4学时)
1.2 图邻接矩阵2学时)
2章 树和距离(6学时)
2.1 树的基本性质,生成树的概念和枚举3学时)
2.2 在最小生成树和最短路径算法3学时)
3章 匹配和因子6学时)
  3.1 匹配和覆盖2学时)
  3.2 最大匹配技术最大加权匹配算法2学时)
3.3 一般图中的匹配及本章练习(2学时)      
4章 连通度、路径及网络流4学时)
4.1 割、连通度以及k-连通图1学时)
4.2 最大网络流1学时)
4.3 最小费用最大流2学时)
5章 图的着色及可平面图6学时)
  5.1 图的着色3学时)
  5.2 可平面图3学时)
6章 边和环4学时)
6.1线图和边着色2学时)
6.2 哈密顿环及旅行商问题2学时)

五、教学方法及手段(含现代化教学手段)
以课堂教学为主,讨论为辅,采用多媒体教学。

六、实验(或)上机内容
 

七、教材及主要参考资料
 
    教    材:图论导引(机械工业出版社Douglas B. West著 李建中 骆吉洲译)
 
参考资料:
(1)图论(科学出版社,王树禾编著)
(2)矩阵乘法在信息学中的应用(浙江省杭州二中 俞华程 论文)


八,课程资料下载
 
第1讲    第2讲    第3讲    第4讲    第5讲    第6讲   
第7讲    第8讲    第9讲    第10讲   第11讲
 

 

© 2017哈尔滨工程大学计算机科学与技术学院
地址:哈尔滨市南岗区南通大街145号哈尔滨工程大学21号楼 邮编:150001 电话:0451-82519406
管理维护:智能信息处理研究中心 技术支持:信息化处