山东科技大学 离散数学第7章习题

《山东科技大学 离散数学第7章习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章习题课2009年12月练习7-1（6）简单图的最大度小于结点数。证明：设简单图G中有n个结点。任取一个结点v，由已知G是简单图没有环和重边，v至多和n-1个结点相邻，也即deg(v)≤n-1,而△(G)＝maxdeg(v)≤n-1,因此最大度小于结点数。练习7-2（2）：若无向图G中恰有两个奇数度的结点，则这两个结点之间必有一条路。证明：设无向图G中两个奇数度的结点为u和v。从u开始构造一条迹，即从u出发经关联于结点u的边e1到达结点u1，若deg(u1)为偶数,则必可由u1再经关联于结点u1的边e2到达结点u2,如此继续下去,每边只取一次,直到另一个奇数度

2、结点停止,由于图G中只有两个奇数度结点,故该结点或是u或是v。如果是v,那么从u到v的一条路就构造好了。如果仍是结点u,此路是闭迹。闭迹上每个结点都是关联偶数条边,而deg(u)为奇数,所以至少还有一条关联于结点u的边不在此闭迹上。继续从u出发,沿着该边到达另一个结点u1’,依次下去直到另一个奇数度结点停下。这样经过有限次后必可到达结点v,这就是一条从u到v的路。练习7-2（3）：若图G是不连通的，则G的补图G是连通的。证明：若G=是不连通的，可设图G的连通分支为G[V1],G[V2],……,G[Vm](m≥2)。由于任意两个连通分支G[Vi],G[V

3、j]不连通，因此Vi与Vj之间的连线在补图中，在G中任取两个结点u和v，则u和v的位置有两种情况：1)若u和v均在同一个连通分支G[Vi]中,根据上面的分析，可在另一个连通分支G[Vj]（i≠j)中取一个结点w，使得u与w，v与w在G中连通，故有u－w－v，即u与v在G中连通2)若u与v分别属于两个不同的连通分支G[Vi]与G[Vj]，由上面的分析可知，u与v在G中连通。故当图G不连通时，则补图G是连通的7-2（4）:当且仅当G的一条边e不包含在G的回路中时，e才是G的割边。证明：必要性。（e是G的割边）设e是连通图G的割边，e关联的两个结点是u和v。如果e包含在

4、G的一个回路中，那么除边e=(u,v)外还有另一条分别以u和v为端点的路，所以删去边e后，G仍为连通图，这与e是割边相矛盾。充分性。如果边e不包含在G的任一条回路中，那么连接结点u和v的边只有e，而不会有其它连接u和v的任何路。因为如果连接u和v还有不同于边e的路，此路与边e就组成一条包含边e的回路，从而导致矛盾。所以删去边e后，u和v就不连通，故边e是割边。300页（2）如果u可达v，它们之间可能不止一条路，在所有这些路中，最短路的长度称为u和v之间的距离（或短程线），记作d，如果从u到v是不可达的，则通常写成d=∞距离矩阵为0121∞011

5、∞101∞120dij=1表示存在边。300页（3）用Warshall算法求可达性矩阵。邻接矩阵为0000010110100000010000000A=i=1时，因为A的第一行全为0，所以A不变。i=2时，因为A的第2列全为0，所以A不变。i=3时，因为A[2，3]=A[4，3]=1，将第3行加到第2行和第4行。0000010110100001010000000A=i=4时，因为A[4,2]=1，将第四行加到第2行，A不变。i=5时，因为A的第5列全为0，所以A不变。0000010110100001010000000P=故A的可达性矩阵为：距离矩阵为

6、0∞∞∞∞1011∞1∞0∞∞2∞10∞∞∞∞∞0300页（4）：写出如图7-3.11所示的图G的完全关联矩阵，并验证其秩如定理7-3.2所述。e1e2e3e4e5e6e7e8e9A100001010B011000100C000110010D110000001E000011100F001100001完全关联矩阵为:此图为连通图，由定理7-3.2，其秩为5。311页（2）构造一个欧拉图，其结点数v和边数e满足下述条件a)v，e的奇偶性一样。b)v，e的奇偶性相反。如果不可能，说明原因。v=3,e=3v=5,e=5v=4,e=4v=4,e=6v=7,e=8v=6,e=

7、7无向图G具有一条欧拉回路，当且仅当G是连通的，并且所有结点度数全为偶数。下面的图中所有结点度数全为偶数，所以都是欧拉图。311页（6）a)画一个有一条欧拉回路和一条汉密尔顿回路的图。在无孤立结点图G中，经过图中每条边一次且仅有一次的一条回路，称为欧拉回路。给定图G，经过图中每个结点恰好一次的回路称作汉密尔顿回路。b)画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。c)画一个没有一条欧拉回路，但有一条汉密尔顿回路的图。设G是一个具有k个奇数度结点（k>0）的连通图，证明在G中的边能剖分为k/2条路（边不相重）。证明：因为一个图中度数为奇数的结点个数必为偶数，故k

8、必为偶数。