图论与网络流

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

本课程系统地讲授图论与网络流理论的基本概念、方法和定理，介绍该领域重要的问题以及典型的算法，展示图论与网络流模型及方法的广泛应用。通过本课程的学习，为学生从事有关方向的理论研究打下基础，也为学生进行相关的应用研究提供有力的工具。

无

第一章 图的基本概念 6.0学时 高随祥
第1节 图的基本概念
第2节 最短路问题
第3节 树及其基本性质
第4节 生成树与最小生成树
第5节 图的中心与中位点
第6节 图的矩阵表示
第二章 图的连通性 4.0学时 高随祥
第1节 割点和割边
第2节 连通度和边连通度
第3节 2-连通图的性质
第4节 Menger定理
第5节 可靠通信网络的设计
第三章 匹配理论 4.0学时 高随祥
第1节 匹配与最大匹配
第2节 完美匹配
第3节 二部图的匹配
第4节 二部图中最大匹配和最大权匹配的算法
第四章 Euler图与Hamilton图 4.0学时 高随祥
第1节 Euler图
第2节 中国邮递员问题
第3节 Hamilton图
第4节 旅行商问题
第五章 支配集、独立集、覆盖集与团 4.0学时 高随祥
第1节 支配集、点独立集、点覆盖集
第2节 边独立集与边覆盖集
第3节 支配集、点独立集、点覆盖集的求法
第4节 Ramsey数
第六章 染色理论 5.0学时 高随祥
第1节 边染色
第2节 点染色
第3节 色多项式
第4节 完美图
第5节 图的边染色算法和点染色算法
第七章 平面图 4.0学时 高随祥
第1节 平面图的概念
第2节 欧拉公式及其应用
第3节 可平面图的判断
第4节 平面图的对偶图
第5节 外可平面图
第6节 不可平面图的几个研究方向简介
第7节 平面图的面染色和四色猜想
第八章 有向图 4.0学时 高随祥
第1节 有向图的基本概念
第2节 有向路与有向圈
第3节 有向图的连通性及无向图的强连通定向
第4节 Euler有向图和Hamilton有向图
第5节 竞赛图
第6节 根树及其应用
第九章 网络流理论 5.0学时 高随祥
第1节 网络与网络流的基本概念
第2节 最大流问题及其标号算法
第3节 求最大流的Dinic算法
第4节 求最大流的推拉流算法
第5节 最大流问题的一些扩展
第6节 最小费用流问题

略