电子科技大学：《图论及其应用 Graph Theory and its Applications》研究生课程教学资源（课件讲稿）17 托特定理与图的因子分解

本次课主要内容 托特定理与图的因子分解 (一)、托特定理 (二)、图的一因子分解 (三)、图的二因子分解 (四)、图的森林因子分解

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2 本次课主要内容 (二)、图的一因子分解 (三)、图的二因子分解 (四)、图的森林因子分解 托特定理与图的因子分解 (一)、托特定理

(三)、托特定理 定理（托特定理，1947） 图G有完美匹配当且仅当对V 的任意非空真子集S,有： o(G-S)≤lS 注：0(G-S)表示奇分支数目

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3 (三)、托特定理 定理 (托特定理，1947) 图G有完美匹配当且仅当对V 的任意非空真子集S, 有： oG S S ( )   注：o (G-S)表示奇分支数目

例1证明：一棵树G有完美匹配当且仅当对所有顶点y ∈G,有：0(G-v)=1。 证明：“必要性” 一方面：若G有完美匹配，由托特定理：0(G-v)≤1 另一方面：若树G有完美匹配，则显然G为偶阶树，于是 o(G-v)≥1； 所以：o(G-v)=1。 “充分性” 由于对任意点v∈V(G),有o(G-v)户1

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4 例1 证明：一棵树G有完美匹配当且仅当对所有顶点v ∈V(G),有：o (G - v)=1。 证明：“必要性” 一方面：若G有完美匹配，由托特定理：o(G-v)≦1; 另一方面：若树G有完美匹配，则显然G为偶阶树，于是 o(G-v)≥1; 所以：o(G-v)=1。 “充分性” 由于对任意点v ∈V(G), 有o(G-v)=1

设C是G-v的奇分支，又设G中由v连到G-v的奇分支的 边为vu,显然，由u连到G-u的奇分支的边也是uy。 令M={e(w):它是由v连到G-v的奇分支的边，v∈V(G) 则：M是G的完美匹配

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5 设Cv是G-v的奇分支，又设G中由v连到G-v的奇分支的 边为vu，显然，由u连到G-u的奇分支的边也是uv。 令M=｛e(v):它是由v连到G-v的奇分支的边，v ∈V(G) ｝ 则：M是G的完美匹配。 v u

推论（彼得森定理）没有割边的3正则图存在完美匹配。 证明：设S是V的任意一个非空真子集，G1,G2,G是 G-S的所有奇分支。m,(1≤i≤k)表示端点分属于S和G:的 边数。 m G 6

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6 推论 (彼得森定理) 没有割边的3正则图存在完美匹配。 证明：设S是V的任意一个非空真子集，G1,G2,…,Gk是 G-S的所有奇分支。mi (1≦i≦k)表示端点分属于S和Gi的 边数。 S G1 G2 Gk m1 m2 mk

下面分析m mk 在G,中，其总度数 为2E(G1。 在G中，其点在G G 中的总度数为3V(Gl。 所以： G2 m,=3Ψ(G,)川-2lE(G;) 所以m必然为奇数，但G无割边，所以m≥3.这样： o(G-S)=k≤3∑m,≤3∑d)≤33小s到=小s 由托特定理，G有完美匹配

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 下面分析mi S G1 G2 Gk m1 m2 mk 在Gi中，其总度数 为2|E(Gi)|。 在Gi中，其点在G 中的总度数为3|V(Gi)|。 所以： 3()2() m VG EG ii i   所以mi必然为奇数，但G无割边，所以mi≥3.这样： 1 11 1 ( ) () 3 33 3 k i i vS oG S k m d v S S          由托特定理，G有完美匹配

注：推论中的条件是G存在完美匹配的充分条件 而不是必要条件。例如： (a)没有完美匹配 (D)有完美匹配 8

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 8 注：推论中的条件是G存在完美匹配的充分条件 而不是必要条件。例如： （a）没有完美匹配 （b）有完美匹配

(二)、图的一因子分解 所谓一个图G的因子G,是指至少包含G的一条边的生成 子图。 所谓一个图G的因子分解，是指把图G分解为若干个边 不重的因子之并。 所谓一个图G的n因子，是指图G的n度正则因子

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 所谓一个图G的因子Gi，是指至少包含G的一条边的生成 子图。 所谓一个图G的因子分解，是指把图G分解为若干个边 不重的因子之并。 所谓一个图G的n因子，是指图G的n度正则因子。 (二)、图的一因子分解

如果一个图G能够分解为若干n因子之并，称G是可n因 子分解的。 图G1 图G2 在上图中，红色边在G,中的导出子图，是G的一个一因 子；红色边在G,中的导出子图，是G的一个二因子。 研究图的因子分解主要是两个方面：一是能否进行分解 (因子分解的存在性)，二是如何分解（分解算法）。 10

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10 如果一个图G能够分解为若干n因子之并，称G是可n因 子分解的。 图G1 在上图中，红色边在G1中的导出子图，是G的一个一因 子；红色边在G2中的导出子图，是G的一个二因子。 图G2 研究图的因子分解主要是两个方面：一是能否进行分解 (因子分解的存在性),二是如何分解(分解算法)

图的一个一因子实际上就是图的一个完美匹配的导出子 图。一个图能够作一因子分解，也就是它能够分解为若干 边不重的完美匹配的导出子图之并。 定理1Kn可一因子分解。 证明：把K2n的2n个J顶点编号为1,2，，2n。作如下排 列： 2n 2 2n-1 ↑3 ↓ n- t n+1

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 11 图的一个一因子实际上就是图的一个完美匹配的导出子 图。一个图能够作一因子分解，也就是它能够分解为若干 边不重的完美匹配的导出子图之并。 定理1 K2n可一因子分解。 证明：把K2n的2n个顶点编号为1，2，…, 2n。作如下排 列： 2n 1 3 2 : : n 2n-1 2n-2 : : n+1