第7章
7-1：1，6
（1）证明：在任何有向完全图中，所有结点入度的平方之和等于所有结点的出度平方之和。 （6）证明：简单图的最大度小于结点数。 7-2：1,2,3,4,7,9,10
（1）在无向图G中，从结点u到结点v有一条长度为偶数的通路，从结点u到结点v又有一条长度为奇数的通路，则在G中必有一条长度为奇数的回路。
（2）若无向图G中恰有两个奇数度的结点，则这两个结点间必有一条路。 （3）若图G是不连通的，则G的补图G是连通的。
（4）当且仅当G的一条边e不包含在G的闭迹中时，e才是G的割边。
（7）在图7-2.9中给出了一个有向图，试求d?v1，v4?，d?v2，v5?及d?v3，v6?。此有向图对应的关系是否可传递的？如果不是可传递的，试求此图的传递闭包。
图7-2.9
（9）一个有向图D是单侧连通的，当且仅当它有一条经过每一结点的路。 （10）试证明徒弟每一个结点和每一条边，都只包含于一个弱分图中。 7-3：1,2,3,4
（1）求出图7-3.9中有向图的邻接矩阵A，找出从v1到v4长度为2和4的路，用计算A2，
34A和A来验证这个结论。
图7-3.9
（2）对于邻接矩阵A的简单有向图G，它的距离矩阵定义如下：
dij??，如果d?vi，vj???
dij?0，对所有的i?1,2,...,n dij?k，这里k是使aij(k)?0的最小正整数
确定由图7-3.9所示的有向图的距离矩阵，并指出dij?1是什么意义？
（3）在图7-3.10中给出了一个有向图，试求该图的邻接矩阵，并求出可达性矩阵和距离矩阵。
图7-3.10
（4）写出如图3.11所示的图G的完全关联的矩阵，并验证其秩是否如定理7-3.2所述。
图7-3.11 7-4：5,6,9
（5）找一种9个a，9个b，9个c的圆形排列，使由字母{a,b,c}组成的长度为3的27个字的每个字出现一次。
（6）a）画一个有一条欧拉回路和一条汉密尔顿回路的图。
b）画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。 c）画一个没有一条欧拉回路，但有一条汉密尔顿回路的图。
（9）证明如G具有汉密尔顿路，则对于V的每一个真子集S有
W(G?S)?S?1
7-5：1,5
（1）证明：若G是每一个面至少由k(k?3)条边围成的连通平面图，则e?里e，v分别是图G的边数和结点数。
（5）如果可能的话，画出图7-5.8各图的平面图象，否则说明它包含一个与K5或K3,3在2
k(v?2)k?2，这
度结点内同构的子图。
图7-5.8
7-6：3,4,7
（3）用韦尔奇?鲍威尔法对图7-6.6各图着色，求图的着色数n。
（a）
图 7-6.6
（b）
（4）证明：若图G是自对偶的，则e?2v?2。
（7）a）一个完全图K6的边涂上红色或蓝色。证明：对任何一种随意涂边的方法，总有一个完全图K3的所有边被涂上红色，或者一个K3的所有边被涂上蓝色。 b）证明：六个人的人群中，或者有三个人互相认识或者有三个人彼此陌生。
c）对于n各结点的完全图Kn的边，随意涂上红色或蓝色，证明：如果有6条或更多条红色的边关联于一个结点，则存在着一个各边都是红色的K4或者一个蓝色的K3。如果有4条或更多条蓝色的边关联于一个结点，则存在一个红色的K4或者存在一个蓝色的K3。 7-7：2,3,4
（2）一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，问它有几个度数为1的结点。
（3）一棵树有n2个结点度数为2，n3个结点度数为3…，n4个结点度数为k，问它有几个度数为1的结点。
（4）设T1和T2是连通图G的两棵生成树，a是在T1不在T2中的一条边，证明存在边b，
它在T2中但不在T1中，使得(T1?{a})?{b}和(T2?{b})?{a}都是G的生成树。 7-8：5,6
（5）给定权1,4,9,16,25,36,49,64,81,100。求 a）构造一颗最优二叉树。
b）构造一颗最优三叉树。
c）说明如何构造一颗最优t叉树。
（6）构造一个与英文字母b,d,g,o,y,e对应的前缀码，并画出该前缀码对应的二叉树，再用此六个字母构成一个英文短语，写出此短语的编码信息。
