ppt18电子科大 图论上课ppt及复习总结 杨春

《ppt18电子科大 图论上课ppt及复习总结 杨春》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Email:yc517922@126.com图论及其应用任课教师：杨春数学科学学院1本次课主要内容(一)、图的一因子分解(二)、图的二因子分解(三)、图的森林因子分解图的因子分解2把一个图按照某种方式分解成若干边不重的子图之并有重要意义。理论上，通过分解，可以深刻地揭示图的结构特征；在应用上，网络通信中，当有多个信息传输时，往往限制单个信息在某一子网中传递，这就涉及网络分解问题。一个图分解方式是多种多样的。作为图分解的典型例子，我们介绍图的因子分解。所谓一个图G的因子Gi，是指至少包含G的一条边的生成子图。所谓一个图G的因子分解，是指把图G分解为若干个边不重的因子之并。

2、所谓一个图G的n因子，是指图G的n度正则因子。3如果一个图G能够分解为若干n因子之并，称G是可n因子分解的。图G1在上图中，红色边在G1中的导出子图，是G的一个一因子；红色边在G2中的导出子图，是G的一个二因子。图G2研究图的因子分解主要是两个方面：一是能否进行分解(因子分解的存在性),二是如何分解(分解算法).(一)、图的一因子分解4图的一个一因子实际上就是图的一个完美匹配的导出子图。一个图能够作一因子分解，也就是它能够分解为若干边不重的完美匹配的导出子图之并。定理1K2n可一因子分解。证明：把K2n的2n个顶点编号为1，2，…,2n。作如下排列：2n132::n2n

3、-12n-2::n+15图中，每行两点邻接，显然作成K2n的一个一因子。2n132::n2n-12n-2::n+1然后按照图中箭头方向移动一个位置，又可以得到K2n的一个一因子，不断作下去，得到K2n的2n-1个边不重的一因子，其并恰好为K2n。例1将K4作一因子分解。1234K4→4123123461234423143121234例2证明：K4有唯一的一因子分解。证明：由习题5第一题知：K4只有3个不同的完美匹配。而k4的每个1因子分解包含3个不同完美匹配，所以，其1因子分解唯一。7例3证明：K2n的不同的一因子数目为：证明：由习题5第一题知：K2n的不同完美匹配的个

4、数为(2n-1)!!。所以，K2n的一因子数目为(2n-1)!!个。即：例4证明：每个k(k>0)正则偶图G是一可因子分解的。证明：因为每个k(k>0)正则偶图G存在完美匹配，设Q是它的一个一因子，则G-Q还是正则偶图，由归纳知，G可作一因子分解。8定理2具有H圈的三正则图可一因子分解。证明：先从三正则图G中抽取H圈，显然剩下边构成G的一个一因子。而H圈显然可以分解为两个一因子。所以G可以分解为3个一因子。注：定理2的逆不一定成立。例如：上图是三正则图，且可以一因子分解，但不存在H圈。9定理3若三正则图有割边，则它不能一因子分解。证明：若不然，设G的三个一因子为G1,G

5、2,G3。不失一般性，设割边e∈G1。显然，G-G2的每个分支必然为圈。所以e在G的某个圈中，这与e是G的割边矛盾。注：没有割边的三正则图可能也没有一因子分解，如彼得森图就是如此！尽管它存在完美匹配。(二)、图的二因子分解如果一个图可以分解为若干2度正则因子之并，称G可以2因子分解。注意：G的一个H圈肯定是G的一个2因子，但是G的一个2因子不一定是G的H圈。2因子可以不连通。10例如，在下图中：两个红色圈的并构成图的一个2因子，但不是H圈。一个显然结论是：G能进行2因子分解，其顶点度数必然为偶数。(注意，不一定是欧拉图)定理4K2n+1可2因子分解。证明：设作路11其中

6、，设Pi上的第j点为vk，则：下标取为1,2,…,2n(mod2n加法)生成圈Hi为v2n+1与Pi的两个端点连线。例5对K7作2因子分解。解：v7v6v5v4v3v2v1v7v6v5v4v3v2v1v7v6v5v4v3v2v1v7v6v5v4v3v2v112定理5K2n可分解为一个1因子和n-1个2因子之和。证明：设V(K2n)=｛v1,v2,…,v2n｝作n-1条路：脚标按模2n-1计算。然后把v2n和Pi的两个端点连接。例6把K6分解为一个1因子和2个2因子分解。v6v5v4v3v2v113解：v6v5v4v3v2v1v6v5v4v3v2v1v6v5v4v3v2v

7、1定理6每个没有割边的3正则图是一个1因子和1个2因子之和。证明：因每个没有割边的3正则图存在完美匹配M，显然，G-M是2因子。14定理7一个连通图可2因子分解当且仅当它是偶数度正则图。证明：必要性显然。充分性：当G是n阶2正则图时，G本身是一个2因子。设当G是n阶2k正则图时，可以进行2因子分解。当G是n阶2k+2正则图时，由1891年彼得森证明过的一个结论：顶点度数为偶数的任意正则图存在一个2因子Q。所以，G-Q是2k阶正则图。由归纳假设，充分性得证。(三)、图的森林因子分解把一个图分解为若干边不重的森林因子的和，称为图的森林因子分解