8-15:证明一棵树最多只有一个完美匹 配。 8-16:对于n=2,3,4,5,分别找出一个没 有完美匹配的n正则简单图的例子。 8-17:证明二分图G具有完美匹配当且仅 当对任意V的子集A I(A)≥A成立。 8.18,8.19,8.20,8.21,8.22
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
基本概念 顶点度数,8(G),定理5.1,52 正则图,生成子图,导出子图,边导出 子图,补图 连通,连通图,连通分支孤立点也是一 个分支) 出度,入度,竞赛图,强连通,单向连 通,弱连通 定理5.4(所有度数大于1有回路),定理57 (二分图,奇回路)
一、基本概念 顶点度数，(G),定理5.1,5.2 正则图，生成子图，导出子图，边导出 子图，补图 连通，连通图，连通分支(孤立点也是一 个分支） 出度，入度，竞赛图，强连通，单向连 通，弱连通 定理5.4(所有度数大于1有回路）,定理5.7 （二分图，奇回路）
(半) Euler图,充要条件 (半 Hamilton图,必要条件,充分条件 (半) Euler有向图充要条件 (半) Hamilton有向图,有关结论 平面图,面,内部面,外部面 Euer公式推论6.,1,6,2 库拉托斯基定理 对偶图,定义,特点 点着色,面着色,地图
(半)Euler图,充要条件 (半)Hamilton图,必要条件，充分条件 (半)Euler有向图,充要条件 (半)Hamilton有向图，有关结论 平面图，面，内部面，外部面 Euler公式,推论6.1，6.2 库拉托斯基定理 对偶图，定义，特点 点着色，面着色，地图
树,树叶,分支点,树的等价定义 生成树,最小生成树,余树,枝,弦, 定理73,G连通当且仅当G有生成树 定理71和73就可获知,个简单连通图 如果不是树就一定存在3棵不同的生成树 m分树,正则m分树最优树. 点割,割点,点连通度平凡或不连通) 断集,割集,桥,边连通度(平凡或不连 通)
树，树叶，分支点，树的等价定义 生成树，最小生成树，余树，枝，弦， 定理7.3,G连通当且仅当G有生成树 定理7.1和7.3就可获知,一个简单连通图 如果不是树,就一定存在3棵不同的生成树. m分树，正则m分树,最优树. 点割，割点，点连通度(平凡或不连通) 断集，割集，桥，边连通度(平凡或不连 通)
点连通度,边连通度,最小度数的关系 定理81 网络,容量,流量,可行流,最大流, 割容量,最小割 匹配,v关于M饱和,完美匹配,最大匹 配,完全匹配 交错路,增广路,定理88(最大匹配的充 要条件。 邻集,霍尔定理 点覆盖和独立集边覆盖和边独立集 定理8.11推论8.1,定理82,科尼格 (K6nig)定理
点连通度，边连通度，最小度数的关系 定理8.1 网络，容量，流量，可行流，最大流， 割容量，最小割 匹配，v关于M饱和，完美匹配，最大匹 配，完全匹配 交错路，增广路，定理8.8(最大匹配的充 要条件。 邻集，霍尔定理 点覆盖和独立集,边覆盖和边独立集 定理 8.11,推论 8.1,定理 8.12,科尼格 (König)定理
二、基本算法和计算 最小权通路,路及权 点着色数和面着色数 最小生成树最优树(w(T) 最大流,最小割,最大流的值,割容量 点连通度,边连通度 β0G),00(G),B1(G),a1(G)
二、基本算法和计算 最小权通路, 路及权 点着色数和面着色数 最小生成树,最优树（w(T)). 最大流，最小割，最大流的值，割容量 点连通度，边连通度 0(G) ,0(G),1(G),1(G)
三、证明及判别 1判别 强连通, 半) Euler图半) Hamilton图,找出(回) 路 有关结论是否成立
三、证明及判别 1.判别 强连通， (半)Euler图,(半)Hamilton图，找出(回) 路 有关结论是否成立
2证明 (1)证明连通:任两点连通。 反证,不连通:1)若干连通分支 2)存在2个顶点,它们之间没有路 (2)证明G为树:树的等价定义证明方法, 利用树的等价定义;证明G有生成树, 可证明G连通,再用定理73 (3)利用 Euler公式,推论6.1和62,及定 理62的证明方法,结合定理5.;做过的 习题 4)连通度证明,定理8.1,8.2,8.3及做 过习题证明方法
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及做 过习题证明方法
(5)最小生成树,最优树算法的正确性证明方法 (6)最大流标号法方法的正确性证明(算法停止 时,为何就是最大流) (7)匹配的证明:定理88的证明方法;利用霍 尔定理证明,如例子和习题 (8)独立集与覆盖:定理81的证明方法,利用 有关定理证明,如作业822 在图论证明中,注意基本概念和结论的运用, 通过加点,加边,删点,删边,使之满足定理 条件
(5)最小生成树，最优树算法的正确性证明方法 (6)最大流标号法方法的正确性证明（算法停止 时，为何就是最大流） (7)匹配的证明：定理8.8的证明方法；利用霍 尔定理证明，如例子和习题 (8)独立集与覆盖：定理8.12的证明方法，利用 有关定理证明，如作业8.22 在图论证明中，注意基本概念和结论的运用， 通过加点，加边，删点，删边，使之满足定理 条件
题型: 判别说明理由 计算 其他 证明
题型： 判别说明理由 计算 其他 证明