ppt18 图因子分解.ppt

Email: yc517922@126.com;本次课主要内容; 把一个图按照某种方式分解成若干边不重的子图之并有重要意义。理论上，通过分解，可以深刻地揭示图的结构特征；在应用上，网络通信中，当有多个信息传输时，往往限制单个信息在某一子网中传递，这就涉及网络分解问题。; 如果一个图G能够分解为若干n因子之并，称G是可n因子分解的。; 图的一个一因子实际上就是图的一个完美匹配的导出子图。一个图能够作一因子分解，也就是它能够分解为若干边不重的完美匹配的导出子图之并。; 图中，每行两点邻接，显然作成K2n的一个一因子。;1; 例3 证明：每个k (k0)正则偶图G是一可因子分解的。; 定理2 具有H圈的三正则图可一因子分解。; 定理3 若三正则图有割边，则它不能一因子分解。; 例如，在下图中：; 下标取为1, 2,…, 2n (mod2n); 定理5 K2n可分解为一个1因子和n-1个2因子之和。; 解：; 定理7 一个连通图可2因子分解当且仅当它是偶数度正则图。; 例如：K5的一种森林因子分解为：; 定理8 图G的荫度为：;震姬桂歧缮季才滨狂昭滦儡测芬掖垢芦瞧妨翼菇祁狱府面议玲紊拎坝胜忧ppt18 图因子分解ppt18 图因子分解; 定理9; 例7 对K7作最小森林因子分解。;v7; 例9 证明：一棵树G有完美匹配当且仅当对所有顶点v ∈V(G),有：o (G - v)=1。; 设Cv是G-v的奇分支，又设G中由v连到G-v的奇分支的边为vu，显然，由u连到G-u的奇分支的边也是uv。; 证明：设G是2k正则连通图，V(G)=｛v1,v2,…,vn｝。则G存在欧拉环游C。; 例如：;x1; 作业;Thank You !