ppt17 - 副本.ppt
《ppt17 - 副本.ppt》由会员分享,可在线阅读,更多相关《ppt17 - 副本.ppt(26页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、1Email: 图论及其应用图论及其应用任课教师:杨春任课教师:杨春应用数学学院应用数学学院2本次课主要内容本次课主要内容(一一)、图的一因子分解、图的一因子分解(二二)、图的二因子分解、图的二因子分解(三三)、图的森林因子分解、图的森林因子分解图的因子分解图的因子分解3 把一个图按照某种方式分解成若干边不重的子图之并有把一个图按照某种方式分解成若干边不重的子图之并有重要意义。理论上,通过分解,可以深刻地揭示图的结构重要意义。理论上,通过分解,可以深刻地揭示图的结构特征;在应用上,网络通信中,当有多个信息传输时,往特征;在应用上,网络通信中,当有多个信息传输时,往往限制单个信息在某一子网中传递
2、,这就涉及网络分解问往限制单个信息在某一子网中传递,这就涉及网络分解问题。题。一个图分解方式是多种多样的。作为图分解的典型例子,一个图分解方式是多种多样的。作为图分解的典型例子,我们介绍图的因子分解。我们介绍图的因子分解。所谓一个图所谓一个图G的因子的因子Gi,是指至少包含,是指至少包含G的一条边的生成的一条边的生成子图。子图。所谓一个图所谓一个图G的因子分解,是指把图的因子分解,是指把图G分解为若干个边不分解为若干个边不重的因子之并。重的因子之并。所谓一个图所谓一个图G的的n因子,是指图因子,是指图G的的n度正则因子。度正则因子。4 如果一个图如果一个图G能够分解为若干能够分解为若干n因子之
3、并,称因子之并,称G是可是可n因因子分解的。子分解的。图图G1 在上图中,红色边在在上图中,红色边在G1中的导出子图,是中的导出子图,是G的一个一因的一个一因子;红色边在子;红色边在G2中的导出子图,是中的导出子图,是G的一个二因子。的一个二因子。图图G2 研究图的因子分解主要是两个方面:一是能否进行分解研究图的因子分解主要是两个方面:一是能否进行分解(因子分解的存在性因子分解的存在性),二是如何分解二是如何分解(分解算法分解算法).(一一)、图的一因子分解、图的一因子分解5 图的一个一因子实际上就是图的一个完美匹配。一个图图的一个一因子实际上就是图的一个完美匹配。一个图能够作一因子分解,也就
4、是它能够分解为若干边不重的完能够作一因子分解,也就是它能够分解为若干边不重的完美匹配之并。美匹配之并。定理定理1 K2n可一因子分解。可一因子分解。证明:把证明:把K2n的的2n个顶点编号为个顶点编号为1,2,,2n。作如下排。作如下排列:列:2n132:n2n-12n-2:n+16 图中,每行两点邻接,显然作图中,每行两点邻接,显然作成成K2n的一个一因子。的一个一因子。2n132:n2n-12n-2:n+1 然后按照图中箭头方向移动一然后按照图中箭头方向移动一个位置,又可以得到个位置,又可以得到K2n的一个一的一个一因子,不断作下去,得到因子,不断作下去,得到K2n的的2n-1个边不重的一
5、因子,其并恰个边不重的一因子,其并恰好为好为K2n。例例1 将将K4作一因子分解。作一因子分解。1234K44123123471234423143121234 例例2 证明:证明:K4有唯一的一因子分解。有唯一的一因子分解。证明:由习题证明:由习题5第一题知:第一题知:K4只有只有3个不同的完美匹配。个不同的完美匹配。而而k4的每个的每个1因子分解包含因子分解包含3个不同完美匹配,所以,其个不同完美匹配,所以,其1因子分解唯一。因子分解唯一。8 例例3 证明:证明:K2n的一因子分解数目为:的一因子分解数目为:证明:由习题证明:由习题5第一题知:第一题知:K2n的不同完美匹配的个数为的不同完美
6、匹配的个数为(2n-1)!。所以,。所以,K2n的以因子分解数目为的以因子分解数目为(2n-1)!个。即:个。即:例例4 证明:每个证明:每个k(k0)正则偶图正则偶图G是一可因子分解的。是一可因子分解的。证明:因为每个证明:因为每个k(k0)正则偶图正则偶图G存在完美匹配,设存在完美匹配,设Q是它的一个一因子,则是它的一个一因子,则G-Q还是正则偶图,由归纳知,还是正则偶图,由归纳知,G可作一因子分解。可作一因子分解。9 定理定理2 具有具有H圈的三正则图可一因子分解。圈的三正则图可一因子分解。证明:先从三正则图证明:先从三正则图G中抽取中抽取H圈,显然剩下边构成圈,显然剩下边构成G的一个一
7、因子。而的一个一因子。而H圈显然可以分解为两个一因子。圈显然可以分解为两个一因子。所以所以G可以分解为可以分解为3个一因子。个一因子。注:定理注:定理2的逆不一定成立。例如:的逆不一定成立。例如:上图是三正则图,且可以一因子分解,但不存在圈。上图是三正则图,且可以一因子分解,但不存在圈。10 定理定理3 若三正则图有割边,则它不能一因子分解。若三正则图有割边,则它不能一因子分解。证明:若不然,设证明:若不然,设G的三个一因子为的三个一因子为G1,G2,G3。不失。不失一般性,设割边一般性,设割边e G1。显然,显然,G-G2的每个分支必然为圈。所以的每个分支必然为圈。所以e在在G的某个的某个圈
8、中,这与圈中,这与e是是G的割边矛盾。的割边矛盾。注:没有割边的三正则图可能也没有一因子分解,如注:没有割边的三正则图可能也没有一因子分解,如彼得森图就是如此!尽管它存在完美匹配。彼得森图就是如此!尽管它存在完美匹配。(二二)、图的二因子分解、图的二因子分解 如果一个图可以分解为若干如果一个图可以分解为若干2度正则因子之并,称度正则因子之并,称G可以可以2因子分解。注意:因子分解。注意:G的一个的一个H圈肯定是圈肯定是G的一个的一个2因因子,但是子,但是G的一个的一个2因子不一定是因子不一定是G的的H圈。圈。2因子可以不因子可以不连通。连通。11 例如,在下图中:例如,在下图中:两个红色圈的并
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- ppt17 副本
限制150内