图论第二次作业

图论第二次作业

一、 第四章

4.3（1）画一个有Euler闭迹和Hamilton圈的图； （2）画一个有Euler闭迹但没有Hamilton圈的图； （3）画一个有Hamilton圈但没有Euler闭迹的图； （4）画一个既没有Euler闭迹也没有Hamilton圈的图；

解：（1）一个有Euler闭迹和Hamilton圈的图形如下：

（2）一个有Euler闭迹但没有Hamilton圈的图形如下：

（3）一个有Hamilton圈但没有Euler闭迹的图形如下：

（4）一个既没有Euler闭迹也没有Hamilton圈的图形如下：

4.7 证明：若G没有奇点，则存在边不重的圈C1,C1,···,Cm,使得

E(G)?E(C1)?E(C2)?????E(Cm)。

证明：将G中孤立点除去后的图记为G1，则G1也没有奇点，且?(G1)?2，则G1含圈C1，在去掉G1?E(C1)的孤立点后，得图G2，显然G2仍无奇度点，且

?(G2)?2，从而G2含圈C2，如此重复下去，直到圈Cm，且Gm?E(Cm)全为孤

立点为止，于是得到E(G)?E(C1)?E(C2)?????E(Cm)。

4.10 证明：若

（1）G不是二连通图，或者

（2）G是具有二分类(X,Y)的偶图，这里X?Y， 则G是非Hamilton图。

证明：（1）因为G不是二连通图，则G不连通或者存在割点v，有w(G?v)?2，由相关定理得：若G是Hamilton图，则对于v(G)的任意非空顶点集S，有：

w(G?S)?S，则该定理得逆否命题也成立，所以可得：若G不是二连通图，则

G是非Hamilton图。

（2）因为G是具有二分类(X,Y)的偶图，又因为X?Y，在这里假设X?Y，则有w(G?X)?Y?X，也就是说：对于v(G)的非空顶点集S，有：w(G?S)?S成立，则可以得出G是非Hamilton图。

4.12 设G是有度序列(d1,d2,???,dn)的非平凡简单图，这里

d1?d2?????dn，证明：若不存在小于dn?m?1?n?m，则G有Hamliton路。

证明：在G之外加上一个新点v，把它和G的其余各点连接，得图G1：

(n?1)的正整数m，使得dm?m且2

G1的度序列为：(d1?1,d2?1,???,dn?1,n)，由已知：不存在小于

(n?1)的正整数2m，使得dm?1?m且dn?m?1?1?n?m?1?(n?1)?m。于是由度序列判定定理知：G1是Hamilton路，则G有Hamliton路。

二、 第五章作业

5.1 （1）证明：每个k方体都有完美匹配（k?2）; （2）求K2n和Kn,n中不同的完美匹配的个数。

证明：（1）证明每个k方体都是k正则偶图即可。

事实上，由k方体的构造：k方体有2k个顶点，每个顶点可以用长度为k的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。如果我们划分k方体的2k个顶点，把坐标之和为偶数的顶点归入X，其余归入Y。显然，X中顶点互不邻接，Y中顶点也如此。所以k方体是偶图。又不难知道k方体的每个顶点度数为k，所以k方体是k正则偶图。 由推论得：k方体存在完美匹配。

解：（2）利用归纳法求K2n和Kn,n中不同的完美匹配的个数。

K2n的任意一个顶点有2n-1中不同的方法被匹配。所以K2n的不同完美匹配个数等于(2n-1)K2n-2，如此递推下去，可以归纳出K2n的不同完美匹配个数为：(2n-1)!!；利用同样的方法可归纳出Kn,n的不同完美匹配个数为：n!。

5.2 证明：一棵树最多只有一个完美匹配。

证明：若不然，设M1和M2是树T的两个不同的完美匹配，那么M1?M2??，容易知道：T[M1?M2]每个非空部分顶点度数为2，即它存在圈，于是推出T中有圈，矛盾。所以一棵树最多只有一个完美匹配。

5.6 证明：K2n的1-因子分解的数目为

数目为(2n-1)!!个。即：

(2n?1)!!?(2n)!。 2n?n!证明：由结论知：K2n不同完美匹配的个数为(2n-1)!!。所以，K2n的1-因子分解

(2n)! n2?n!

5.7 将K9表示为四个生成圈之和。

解：K4n+1=K2(2n)+1，所以，可以分解成2n个边不重的2因子之和。而K9=K2*4+1。所以K9可以表示为四个边不重的2因子之和，对于每个分解出的因子的路径为：

Pi?vivi?1vi?1vi?2vi?2vi?3???vi?nvi?n

则K9的四条路径为：

P1?v1v8v2v7v3v6v4v5,P2?v2v1v3v8v4v7v5v6,P3?v3v2v4v1v5v8v6v7,P4?v4v3v5v2v6v1v7v8,则生成圈Hi是V2n+1与Pi的两个端点连线生成的。所以可将K9表示为四个生成圈之和。

5.13 所谓n?n矩阵的一条对角线是指两两不同行不同列的n个矩阵

元素组成的集。对角线的权是指它的n个元素的和。找出下列矩阵具有最小权的对角线：

?4?7??8??6??4581011?6574??51296?

?613107?5798??解：首先从第一行第一列开始，找出矩阵中的最小元素，发现为坐标是(1,1)的4，将其所在的行和列删除，得到的矩阵为

?6574??51296??? ?613107???5798??再从此矩阵的第一行第一列开始，找出矩阵中的最小元素，发现为原坐标是(2,5)的4。依次类推，继续得到坐标是(3,2)的5，(5,3)的7，(4,4)的10。 所以最小权为：4+4+5+7+10=30。

本文来源：https://www.bwwdw.com/article/756a.html