8-15：证明一棵树最多只有一个完美匹配。 8-16：对于n=2,3,4,5，分别找出一个没有完美匹配的n-正则简单图的例子。

Presentation on theme: "8-15：证明一棵树最多只有一个完美匹配。 8-16：对于n=2,3,4,5，分别找出一个没有完美匹配的n-正则简单图的例子。"— Presentation transcript:

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

2 一、基本概念 顶点度数，(G),定理5.1,5.2 正则图，生成子图，导出子图，边导出子图，补图 连通，连通图，连通分支(孤立点也是一个分支） 出度，入度，竞赛图，强连通，单向连通，弱连通 定理5.4(所有度数大于1有回路）,定理5.7（二分图，奇回路）

3 (半)Euler图,充要条件 (半)Hamilton图,必要条件，充分条件 (半)Euler有向图,充要条件 (半)Hamilton有向图，有关结论 平面图，面，内部面，外部面 Euler公式,推论6.1，6.2 库拉托斯基定理 对偶图，定义，特点 点着色，面着色，地图

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

5 点连通度，边连通度，最小度数的关系定理8.1 网络，容量，流量，可行流，最大流，割容量，最小割 匹配，v关于M饱和，完美匹配，最大匹配，完全匹配 交错路，增广路，定理8.8(最大匹配的充要条件。 邻集，霍尔定理 点覆盖和独立集,边覆盖和边独立集 定理 8.11,推论 8.1,定理 8.12,科尼格(König)定理

6 二、基本算法和计算 最小权通路, 路及权 点着色数和面着色数 最小生成树,最优树（w(T)). 最大流，最小割，最大流的值，割容量 点连通度，边连通度 0(G) ,0(G),1(G),1(G)。

7 三、证明及判别 1.判别 强连通， (半)Euler图,(半)Hamilton图，找出(回)路 有关结论是否成立

8 2.证明 (1)证明连通：任两点连通。 反证，不连通：1）若干连通分支 2）存在2个顶点，它们之间没有路 (2)证明G为树：树的等价定义证明方法，利用树的等价定义；证明G有生成树，可证明G连通，再用定理7.3 (3)利用Euler公式，推论6.1和6.2，及定理6.2的证明方法，结合定理5.1;做过的习题 (4)连通度证明，定理8.1，8.2，8.3及做过习题证明方法

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

10 题型： 判别说明理由 计算 其他 证明

11 答疑时间: 6月19日上午9:00-11:30 下午1:30-4:30 地点：逸夫楼402室 6月20日上午9:00-11:30
地点：系223房间