- 1、本文档共26页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
图论课件–图的因子分解
* 图论及其应用 应用数学学院 * 本次课主要内容 (一)、图的一因子分解 (二)、图的二因子分解 (三)、图的森林因子分解 图的因子分解 * 把一个图按照某种方式分解成若干边不重的子图之并有重要意义。理论上,通过分解,可以深刻地揭示图的结构特征;在应用上,网络通信中,当有多个信息传输时,往往限制单个信息在某一子网中传递,这就涉及网络分解问题。 一个图分解方式是多种多样的。作为图分解的典型例子,我们介绍图的因子分解。 所谓一个图G的因子Gi,是指至少包含G的一条边的生成子图。 所谓一个图G的因子分解,是指把图G分解为若干个边不重的因子之并。 所谓一个图G的n因子,是指图G的n度正则因子。 * 如果一个图G能够分解为若干n因子之并,称G是可n因子分解的。 图G1 在上图中,红色边在G1中的导出子图,是G的一个一因子;红色边在G2中的导出子图,是G的一个二因子。 图G2 研究图的因子分解主要是两个方面:一是能否进行分解(因子分解的存在性),二是如何分解(分解算法). (一)、图的一因子分解 * 图的一个一因子实际上就是图的一个完美匹配。一个图能够作一因子分解,也就是它能够分解为若干边不重的完美匹配之并。 定理1 K2n可一因子分解。 证明:把K2n的2n个顶点编号为1,2,…, 2n。作如下排列: 2n 1 3 2 : : n 2n-1 2n-2 : : n+1 * 图中,每行两点邻接,显然作成K2n的一个一因子。 2n 1 3 2 : : n 2n-1 2n-2 : : n+1 然后按照图中箭头方向移动一个位置,又可以得到K2n的一个一因子,不断作下去,得到K2n的2n-1个边不重的一因子,其并恰好为K2n。 例1 将K4作一因子分解。 1 2 3 4 K4 → 4 1 2 3 1 2 3 4 * 1 2 3 4 4 2 3 1 4 3 1 2 1 2 3 4 例2 证明:K4有唯一的一因子分解。 证明:由习题5第一题知:K4只有3个不同的完美匹配。而k4的每个1因子分解包含3个不同完美匹配,所以,其1因子分解唯一。 * 例3 证明:K2n的一因子分解数目为: 证明:由习题5第一题知:K2n的不同完美匹配的个数为(2n-1)!!。所以,K2n的以因子分解数目为(2n-1)!!个。即: 例4 证明:每个k (k0)正则偶图G是一可因子分解的。 证明:因为每个k (k0)正则偶图G存在完美匹配,设Q是它的一个一因子,则G-Q还是正则偶图,由归纳知,G可作一因子分解。 * 定理2 具有H圈的三正则图可一因子分解。 证明:先从三正则图G中抽取H圈,显然剩下边构成G的一个一因子。而H圈显然可以分解为两个一因子。所以G可以分解为3个一因子。 注:定理2的逆不一定成立。例如: 上图是三正则图,且可以一因子分解,但不存在圈。 * 定理3 若三正则图有割边,则它不能一因子分解。 证明:若不然,设G的三个一因子为G1,G2,G3。不失一般性,设割边e∈ G1。 显然,G-G2的每个分支必然为圈。所以e在G的某个圈中,这与e是G的割边矛盾。 注:没有割边的三正则图可能也没有一因子分解,如彼得森图就是如此!尽管它存在完美匹配。 (二)、图的二因子分解 如果一个图可以分解为若干2度正则因子之并,称G可以2因子分解。注意:G的一个H圈肯定是G的一个2因子,但是G的一个2因子不一定是G的H圈。2因子可以不连通。 * 例如,在下图中: 两个红色圈的并构成图的一个2因子,但不是H圈。 一个显然结论是:G能进行2因子分解,其顶点度数必然为偶数。(注意,不一定是欧拉图) 定理4 K2n+1可2因子分解。 证明:设 作路 * 其中,设Pi上的第j点为vk,则: 下标取为1, 2,…, 2n (mod2n) 生成圈Hi为v2n+1与Pi的两个端点连线。 例4 对K7作2因子分解。 解: v7 v6 v5 v4 v3 v2 v1 v7 v6 v5 v4 v3 v2 v1 v7 v6 v5 v4 v3 v2 v1 v7 v6 v5 v4 v3 v2 v1 * 定理5 K2n可分解为一个1因子和n-1个2因子之和。 证明:设V(K2n)={v1,v2,…,v2n} 作n-1条路: 脚标按模2n-1计算。然后把v2n和Pi的两个端点连接。 例5 把K6分解为
文档评论(0)