图论(15)图分解问题
目录
(一)图的一因子分解
因子
因子的本质是生成子图,因子的点集跟原图一样,只是边集不一样。
因子分解
n因子
可n因子分解
偶数阶完全图可一因子分解
如果一个图存在完美匹配,则其顶点数一定是偶数个。因为完美匹配是独立的边覆盖了所有的顶点,顶点的个数一定是边的两倍
例题
定理2 具有H圈三正则图可一因子分解
可一因子分解的三正则图并不一定是哈密尔顿图,去掉上下两个点,得到3个分支,3>2,由性质定理,不是哈密尔顿图
定理3 若三正则图有割边,则它不能一因子分解
两个一因子相加是二因子,二因子中每个点的度数都为2,则二因子一定是由若干个圈构成的,
(二)、图的二因子分解
定理4 奇数阶完全图可2因子分解
定理5 2n阶完全图可分解为1个一因子和n-1个二因子之并
逻辑证明:2n阶完全图可以分成2n-1个一因子,把其中的2n-2个一因子,通过合并,得到n-1个二因子,得证
定理6 每个没有割边的3正则图是1个一因子和1个二因子之和
定理7 一个连通图可2因子分解当且仅当它是偶数度正则图
前边定理4的奇数阶完全图就是偶数度正则图呀
(三)、图的森林因子分解
分解成的每一个因子都是森林
定理8 荫度计算公式
包含s个顶点的子图有很多,其中包含边数最多的那个子图所包含的边数即为ms
这个方法也太不好用了,得把s得每种情况都穷举一遍。
定理9 完全图和完全偶图的最小森林因子分解
重点题型
注意,图的差运算是删边运算,不删点