图论与网络算法

课程编码：070105M04003H 英文名称：Graph Theory and Network Algorithm 课时：40 学分：2.00 课程属性：专业核心课 主讲教师：高随祥

本课程系统地讲授图论与网络流理论的基本概念、方法和定理，介绍该领域重要的问题以及典型的算法，展示图论与网络流模型及方法的广泛应用。
本课程适合数学、运筹学、系统科学各专业研究生作为专业基础课，同时也可供物理学、化学、生物与生命科学、计算机科学与技术、电子科学与技术、通信与信息科学、网络工程、复杂网络与系统、资源与环境、物流与交通运输、管理科学与工程、以及过程工程、自动控制等学科专业的研究生选修。
通过本课程的学习，为学生从事有关方向的理论研究打下基础，也为学生进行相关的应用研究提供有力的工具。

高等数学、线性代数

第一章 图的基本概念 5学时 高随祥
第1节 图的基本概念
第2节 最短路问题
第3节 树及其性质
第4节 生成树与最小生成树
第5节 图的矩阵表示
第二章 图的连通性 4学时 高随祥
第1节 割点和割边
第2节 连通度和边连通度
第3节 2-连通图的性质
第三章 匹配理论 5学时 高随祥
第1节 匹配与最大匹配
第2节 完美匹配
第3节 二部图的匹配
第4节 二部图中最大匹配与最大全匹配的算法
第四章 欧拉图与哈密尔顿图 4学时 高随祥
第1节 欧拉图
第2节 中国邮递员问题
第3节 哈密尔顿图
第4节 旅行商问题
第五章 支配集、独立集、覆盖集 5学时 高随祥
第1节 支配集、点独立集、点覆盖集
第2节 边独立及与边覆盖集
第3节 支配集、点独立集、点覆盖集的求法
第六章 染色理论 5学时 高随祥
第1节 边染色
第2节 点染色
第3节 色多项式
第4节 图的边染色和点染色算法
第七章 平面图 3学时 高随祥
第1节 平面图的概念
第2节 欧拉公式及其应用
第3节 可平面图的判断
第4节 平面图的对偶图
第5节 外可平面图
第八章 有向图 4学时 高随祥
第1节 有向图的基本概念
第2节 有向路与有向圈
第3节 有向图的连通性及无向图的强连通定向
第4节 欧拉有向图和哈密尔顿有向图
第5节 竞赛图
第九章 网络流理论 5学时 高随祥
第1节 网络与网络流的概念
第2节 最大流问题及其标号算法
第3节 求最大流的Dinic算法
第4节 最小费用流问题

略