《图论》课程大纲

学    院：软件学院

学    期：2021 秋季

课程号：311172020

总课时：32

学    分：2

任课教师：林  兰

课程助教：待定

上课时间/地点：周五3-4节(am10:15-11:55)  江安一教A207

Email address:  linlan@scu.edu.cn

CourseWebsite:  http://cc.scu.edu.cn（课件及资料的发布）

教材：

《图论引导》(原书第二版) [美]道格拉斯 B. 韦斯特 著 李建中 骆吉洲 译 机械工业出版社

参考书目：

《图论---一个迷人的世界》 [美]Arthur Benjamin, Gary Chartrand, PingZhang 著,程晓亮 等译,机械工业出版社, 2016.10

《现代图论》 殷剑宏 主编  北京航空航天大学出版社 (2015.6)

《离散数学及其应用》（原书第8版）（Discrete Mathematical and Its Applications），Kenneth.Rosen著，机械工业出版社（2020.1）

其它参考资料：

课程网站发布的相关学习资源、资料。

学习内容：

第1章 基本概念（8个学时）

n  1.1 什么是图

n  1.2 路径、环和迹

n  1.3 顶点度和计数

n  1.4 有向图

第3章 匹配和因子（8个学时）

n  3.1 匹配和覆盖

n  3.2 算法和应用

n  3.3 一般图中的匹配

第5章  图的着色（6个学时）

n  5.1 图的边着色

n  5.2 顶点着色

n  5.3 着色的计数

专题讨论 （4个学时）

n  独立集求法

n  Ramsey理论

小测验  3次（4个学时）

期末考试（2个学时）

说明：以上课程内容按教材实际章节编写，方便同学们对应教材。

学习目的：（你将学习哪些内容、会获得哪些能力？）

课程着力于图的基本概念、基本定理和一些经典算法，内容包括四个部分。第一部分，学习基本概念、经典模型及其应用。在这一部分可以扩展到先前课程《离散数学》中未学到但又常用的一些基本概念和有趣的应用，比如排名投票制问题。第二部分，图的匹配问题。从概念、定理出发，讨论图的基本匹配算法、二部图的不同匹配模型，及具体问题的应用建模，还会学习到匹配与因子的巧妙关系。第三个部分，图的着色问题。这个部分将更加深入细致的（与先前课比较）学习到图的边着色、点着色和它们的典型应用，以及讨论着色的计数问题。第四个部分，课程将选择两个专题内容，扩展学习的广度。

课程结束后，学生将理解并掌握典型的图结构，具有解决图论基本问题的方法和技巧。能够运行图这个强大的数学工具解决计算机工程问题建模、求解相关的计算机科学问题和优化问题。

评分标准：

期末总成绩 = 平时成绩×20% + 平时测验×30% + 期末考试成绩×50%

平时成绩：包括需提交的作业成绩（大致15%），考勤（大致5%）。

平时测验：3次，分别在9月、10月和11月底，每次占10%。

期末考试：1次，时间待定，占50%成绩。

课程要求：

l每周按时参加课堂学习，积极参与讨论和发言。

l课后复习，阅读相关资料，完成布置的练习题。

l按时完成作业，并须参加过程测验。