离散作业第7章

第77-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中给出了一个有向图，试求dv，v，dv，v及dv，v。此有向1 4 2 5 3 6图对应的关系是否可传递的？如果不是可传递的，试求此图的传递闭包。图7-2.9（9）一个有向图D是单侧连通的，当且仅当它有一条经过每一结点的路。（10）试证明徒弟每一个结点和每一条边，都只包含于一个弱分图中。7-3：1,2,3,4（1）求出图7-3.9中有向图的邻接矩阵A从v到v长度为2和4的路，用计算A2，1 4A3和A4来验证这个结论。图7-3.9（2）对于邻接矩阵A的简单有向图G，它的距离矩阵定义如下：d，如果dv，vj i jd0，对所有的i,2,...,njdk，这里k是使a(k)0的最小正整数j j确定由图7-3.所示的有向图的距离矩阵，并指出d1是什么意义？j（3图.10中给出了一个有向图，试求该图的邻接矩阵，并求出可达性矩阵和距离矩阵。图7-0（4图所示的图G的完全关联的矩阵，并验证其秩是否如定理72所述。图7-4：5,6,9（）找一种9个a，9个b，9个c的圆形排列，使由字母{a,b,c}组成的长度为3的27个字的每个字出现一次。（6b）画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。c）画一个没有一条欧拉回路，但有一条汉密尔顿回路的图。（9如G具有汉密尔顿路，则对于V的每一个真子集S有W(GS)S17-5：5（1）证明：若G是每一个面至少由k(k3)条边围成的连通平面图，则e里e，v分别是图G的边数和结点数。

，这k(v2)，这k2（5图58各图的平面图象，否则说明它包含一个与K或K在25 3,3度结点内同构的子图。图7-57-6：3,4,7（3奇鲍威尔法对图7-6.各图着色，求图的着色数n。（） （）6（4）证明：若图G是自对偶的，则e2v2。（7）一个完全图K的边涂上红色或蓝色。证明：对任何一种随意涂边的方法，总有一6个完全图K的所有边被涂上红色，或者一个K的所有边被涂上蓝色。3 3b）证明：六个人的人群中，或者有三个人互相认识或者有三个人彼此陌生。c对于n各结点的完全图K的边随意涂上红色或蓝色有6条或更多条红色n的边关联于一个结点，则存在着一个各边都是红色的K或者一个蓝色的K。如果有条4 3或更多条蓝色的边关联于一个结点，则存在一个红色的K或者存在一个蓝色的K。4 37-7：2,3,4（为2为3为4为1的结点。（有n个结点度数为2，n个结点度数为3…，n个结点度数为k个2 3 4度数为1的结点。（4设T和T是连通图G的两棵生成树，a是在T不在T中的一条边，证明存在边b，1 2 1 2它在T中但不在T中，使得(T{a}){b}和(T{b}){a}都是G的生成树。2 1 1 27-8：6（5）给定权1,4,9,16,