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)定理