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

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

1.k-(点,面,边)着色,k-(点,面,边)色图,点色数x(G),面色数x*(G),边色数x(G) 2.x(G)上界, Brooks定理 3.五色定理 4. Vizing定理 5.色多项式f(G,k)

通过本课程的学习，学生初步学会用Matlab软件做数值计算、解优化模型、解图论问题；初步理解并上机操练下列数值计算方法：方程求解、迭代法、微分方程求解、插值法、曲线拟合、回归分析、计算机模拟、线性规划与非线性规划、图论中的最小生成树和最短路径；初步学会用数学建模的方法解决一些实际问题

图论的应用范围: 1、中国邮路问题: 邮递员如何选择适当的投递路线,使每条街道至 少走过一次且所走的总路程最短? 2、最短路问题: 一个乡有9个自然村,其间道路如下图所示, 要以村为中心建有线广播网,如要求沿道路 架设广播线,应如何架设使所用电线最短？

1.关联矩阵M(D),M(G) 2.用基本联矩阵M(G)求所有生成树 3.邻接矩阵A(D),相邻矩阵A(G) 4.用A的幂求不同长度通路(回路)总数 米 5.可达矩阵P(D),连通矩阵P(G) 6.单源最短路径问题, Dijkstra算法

一、等价关系,等价类,商集 二、划分,第二类 Stirling数 三、偏序,线序,拟序,良序 四、哈斯图 五、特殊元素:最?元,极?元,?界,?确界 六、(反)链

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

P167 之题：写出 Matlab 环境下，由加权图的边权矩阵表示，转化为带权邻接矩阵表示，的函数 M—文件

根据“邻接矩阵”计算图（有向无向混合负权均可） 中“从任意一个顶点到任意一个顶点的最短路长” 算法： 邻接矩阵 C