没有幻灯片标题复旦大学精品课程

1、 8-15：证明一棵树最多只有一个完美匹：证明一棵树最多只有一个完美匹配。配。 8-16：对于：对于n=2,3,4,5，分别找出一个没有分别找出一个没有完美匹配的完美匹配的n-正则简单图的例子。正则简单图的例子。 8-17：证明二分图：证明二分图G具有完美匹配当且仅具有完美匹配当且仅当对任意当对任意V的子集的子集A， |（A）|A成立。成立。 8.18,8.19,8.20,8.21,8.22 一、基本概念一、基本概念 顶点度数，顶点度数， (G),定理定理5.1,5.2 正则图，生成子图，导出子图，边导出正则图，生成子图，导出子图，边导出子图，补图子图，补图 连通，连通图，连通分支连通，连通图

2、，连通分支(孤立点也是一孤立点也是一个分支）个分支） 出度，入度，竞赛图，强连通，单向连出度，入度，竞赛图，强连通，单向连通，弱连通通，弱连通 定理定理5.4(所有度数大于所有度数大于1有回路）有回路）,定理定理5.7（二分图，奇回路）（二分图，奇回路） (半半)Euler图图,充要条件充要条件 (半半)Hamilton图图,必要条件，充分条件必要条件，充分条件 (半半)Euler有有向图向图,充要条件充要条件 (半半)Hamilton有有向图，有关结论向图，有关结论 平面图，面，内部面，外部面平面图，面，内部面，外部面 Euler公式公式,推论推论6.1，6.2 库拉托斯基定理库拉托斯基定理

3、 对偶图，定义，特点对偶图，定义，特点 点着色，面着色，地图点着色，面着色，地图 树，树叶，分支点，树的等价定义树，树叶，分支点，树的等价定义 生成树，最小生成树，余树，枝，弦，生成树，最小生成树，余树，枝，弦， 定理定理7.3,G连通当且仅当连通当且仅当G有生成树有生成树 定理定理7.1和和7.3就可获知就可获知,一个简单连通图如一个简单连通图如果不是树果不是树,就一定存在就一定存在3棵不同的生成树棵不同的生成树. m分树，正则分树，正则m分树分树,最优树最优树. 点割，割点，点连通度点割，割点，点连通度(平凡或不连通平凡或不连通) 断集，割集，桥，边连通度断集，割集，桥，边连通度(平凡或不

4、连平凡或不连通通) 点连通度，边连通度，最小度数的关系点连通度，边连通度，最小度数的关系定理定理8.1 网络，容量，流量，可行流，最大流，网络，容量，流量，可行流，最大流，割容量，最小割割容量，最小割 匹配，匹配，v关于关于M饱和，完美匹配，最大匹饱和，完美匹配，最大匹配，完全匹配配，完全匹配 交错路，增广路，定理交错路，增广路，定理8.8(最大匹配的充最大匹配的充要条件。要条件。 邻集，霍尔定理邻集，霍尔定理 点覆盖和独立集点覆盖和独立集,边覆盖和边独立集边覆盖和边独立集 定理定理 8.11,推论推论 8.1,定理定理 8.12,科尼格科尼格(Knig)定理定理 二、基本算法和计算二、基本算

5、法和计算 最小权通路最小权通路, 路及权路及权 点着色数和面着色数点着色数和面着色数 最小生成树最小生成树,最优树（最优树（w(T). 最大流，最小割，最大流的值，割容量最大流，最小割，最大流的值，割容量 点连通度，边连通度点连通度，边连通度 0(G) , 0(G), 1(G), 1(G)。 三、证明及判别三、证明及判别 1.判别判别 强连通，强连通， (半半)Euler图图,(半半)Hamilton图，找出图，找出(回回)路路 有关结论是否成立有关结论是否成立 2.证明证明 (1)证明连通：任两点连通。证明连通：任两点连通。 反证，不连通：反证，不连通：1）若干连通分支）若干连通分支 2）存

6、在）存在2个顶点，它们之间没有路个顶点，它们之间没有路 (2)证明证明G为树：树的等价定义证明方法，为树：树的等价定义证明方法，利用树的等价定义；证明利用树的等价定义；证明G有生成树，有生成树，可证明可证明G连通，再用定理连通，再用定理7.3 (3)利用利用Euler公式，推论公式，推论6.1和和6.2，及定，及定理理6.2的证明方法，结合定理的证明方法，结合定理5.1;做过的做过的习题习题 (4)连通度证明，定理连通度证明，定理8.1，8.2，8.3及做及做过习题证明方法过习题证明方法 (5)最小生成树，最优树算法的正确性证明方法最小生成树，最优树算法的正确性证明方法 (6)最大流标号法方法

7、的正确性证明（算法停止最大流标号法方法的正确性证明（算法停止时，为何就是最大流）时，为何就是最大流） (7)匹配的证明：定理匹配的证明：定理8.8的证明方法；利用霍的证明方法；利用霍尔定理证明，如例子和习题尔定理证明，如例子和习题 (8)独立集与覆盖：定理独立集与覆盖：定理8.12的证明方法，利用的证明方法，利用有关定理证明，如作业有关定理证明，如作业8.22 在图论证明中，注意基本概念和结论的运用，在图论证明中，注意基本概念和结论的运用， 通过加点，加边，删点，删边，使之满足定理通过加点，加边，删点，删边，使之满足定理条件。条件。 题题型：型： 判别说明理由判别说明理由 计算计算 其他其他 证明证明答