§9.1 网络与网络流的基本概念 §9.2 最大流最小割定理及求最大流的标号算法 §9.3 求最大流的 Dinic 算法 §9.4 最小费用流问题

§6.1 边染色 §6.2 点染色 §6.3 色多项式 §6.4 完美图

§2.1 割点和割边 §2.2 连通度和边连通度 §2.3 2-连通图的性质 §2.4 Menger定理 §2.5 可靠通信网络的设计

§4.1 Euler 图 §4.2中国邮递员问题（Chinese Postman Problem） §4.3Hamilton 图 §4.4 旅行商问题(Travelling Salesman Problem,TSP)

中科院研究生院专业基础课：《图论与网络流理论》第一章 习题（高随祥）

§3.1 匹配与最大匹配 §3.2 完美匹配 §3.3 二部图的匹配 §3.4 二部图中最大匹配与最大权匹配的算法

本章的知识点： 构建集装箱运输网络模型 重点掌握构建集装箱运输网络模型并计算 学生自行查阅的资料： 网络配流模型文献8篇 本章为重点章节 学时（10） 理论6学时，仿真实验4学时 7.1 多式联运虚拟运输网络图的构建 单节点 7.2 集装箱低碳运输路线选择模型构建 7.3 时间窗约束下的多式联运路径成本模型

§8.1 有向图的基本概念 §8.2 有向路与有向圈 §8.3 有向图的连通性 §8.4 Euler 有向图和 Hamilton 有向图 §8.5 竞赛图 §8.6 根树及其应用

§5.1 支配集、点独立集、点覆盖集 §5.2 边独立集与边覆盖集 §5.3 支配集、点独立集、点覆盖集的求法 §5.4 Ramsey 数

一、排课表问题—求二部图的正常 χ′(G)边染色 1. 问题： 有 m 位教师 m x , x , , x 1 2 \ ，n 个班级 n y , y , , y 1 2 \ 。教师 xi 每周需要给班级 yj上 pij 次（节）课。要求制订一张周课时尽可能少的课程表