9 图 习题答案.doc

练习9.11.（l）证明：n个顶点的简单图中不会有多于条边。（2）n个顶点的有向完全图中恰有条边。证:（l）由于简单图是没有重边和环的无向图，所以任意两个顶点之间最多有1条边，n个顶点最多有C(n,2)=n(n-1)/2条边。（2）由于有向完全图是任何两个顶点都有有向边的图，所以n个顶点的边数总和为2. 分别画出下面两个图的补图及它的一个生成子图。 （1）（2） 解:（1） 补图 生成子图(不唯一)（2） 补图 生成子图(不唯一)3. 一个简单图，如果同构于它的补，则该图称为自补图。（1）给出一个4个顶点的自补图。（2）给出一个5个顶点的自补图。（3）是否有3个顶点或6个顶点的自补图？（4）证明一个自补图一定有4k或4k1个顶点（k为正整数）。解 （1）4个顶点的自补图： （2）5个顶点的自补图：（3）没有。（4）证 设G为自补图，有n 个顶点。我们已知n 个顶点的完全图有 条边，因此G应恰有条边。故或者n是4的整数倍，或者n1是4的整数倍，即图G 一定有4k或4k1个顶点（k为正整数）。4. （l）证明图中（a）与（b）同构。 A a bD C B c E F d e k f g G H h I J i j (a) (b) （2）给出所有不同构的4个结点的简单图的图示。证（l）在图（a）图（b）间建立双射h vABDIJCEGHFh(v)abdihcfjkg可逐一验证 (不赘) (u,v)E(a)当且仅当 (h(u),h(v)E(b)（2）所有不同构的4个结点的简单图的图示有如下11个： 练习9.21. 证明：在简单无向图G中，从结点u到结点v,如果既有奇数长度的通路又有偶数长度的通路，那么G中必有一奇数长度的回路。证 设G中，从结点u到结点v的奇数长度的通路为O ，偶数长度的通路为E。对O和E的除结点u和v的相交结点的数目归纳k。k=0,那么O和E恰好构成G的奇数长度的回路。 设奇数长度的通路与偶数长度的通路的相交结点的数目少于k时，命题成立。 u 1 2 k v设图G中，从结点u到结点v的奇数长度的通路与偶数长度的通路有k个相交结点，如图所示：考虑结点u到结点k,如果从结点u到结点k,既有奇数长度的通路又有偶数长度的通路，那么据归纳假设，其中有一奇数长度的回路，因而G中必有一奇数长度的回路。如果从结点u到结点k的两条通路均为偶数长度，或均为奇数长度，那么结点k到结点v必然既有奇数长度的通路又有偶数长度的通路，因而构成一奇数长度的回路。2. 证明：若简单无向图G是不连通的，那么G必定是连通的。证 设简单无向图G是不连通的，那么G由两个不相关的子图（没有任何边关联分别在两个子图中的顶点）G1，G2组成，分别有顶点，u1,u2,uk和v1,v2,vl。由于边（ui ,vj）均不在G中（i=1,2,k, j=1,2,l）因此（ui ,vj）全部在G中，从而G是连通的。3. 给出下图中有向图的强分图，单向分图和弱分图。4.v1 v2 v7 v10 v4 v3 v8 v9 v5 v6解 图中有向图的强分图有：v1,v2, , v3,v4,v5,v6, ,v7,v8,v9,图中有向图的单向分图有：v1,v2,v3,v4,v5,v6, ,v7,v8,v9,v10,图中有向图的弱分图有：v1,v2,v3,v4,v5,v6, ,v7,v8,v9,v10,4. 有7个人a，b，c，d，e，f，g分别精通下列语言，问他们7人是否可以自由交谈（必要时借助他人作翻译）。 a 精通英语。 b 精通汉语和英语。 c 精通英语、俄语和意大利语。 d 精通日语和英语。 e 精通德语和意大利语。 f 精通法语、日语和俄语。g 精通法语和德语。 ab d c e g f解 下图中7个顶点表示7个人，关联两个顶点的边表示两个人同时精通某一种语言：由于该图是连通的，因此他们7人是可以自由交谈（必要时借助他人作翻译）。5. v是简单连通图G的割点，当且仅当G中存在两个顶点v1，v2，使v1到v2的通路都经过顶点v 。试证明之。证充分性是显然的。必要性：设顶点v是简单连通图G的割点，如果不存在两个顶点v1，v2，使v1到v2的通路都经过顶点v，那么对任意两个顶点v1，v2，都有一条通路不经过顶点v，因而删除顶点v不能使G不连通，与v是简单连通图G的割点矛盾。故G中必存在两个顶点v1，v2，使v1到v2的通路都经过顶点v 。6. 简单连通图G的割边，当且仅当e不在G的任一回路上。试证明之。证 设e是简单连通图G的割边，其端点为u,v 。删除边e后，u,v应在两个不同的连通分支中。若e在G的一条回路上，那么删除边e后，u,v应仍在一条通路上，矛盾。故e不在G的任一回路上。反之，设e不在G的任一回路上，而e不是简单连通图G的割边。那么G-e仍是连通的，故还有u到v的一条通路，从而这条通路连同边e构成G中的一条回路，矛盾。因此边e是简单连通图G的割边练习9.31. 试作出四个图的图示，使第一个既为欧拉图又为哈密顿图；第二个是欧拉图而非哈密顿图；第三个是哈密顿图却非欧拉图；第四个既非欧拉图也非哈密顿图。解（a）既为欧拉图又为哈密顿图；（b）是欧拉图而非哈密顿图；（c）是哈密顿图却非欧拉图；（d）既非欧拉图也非哈密顿图。 （a） (b) (c) (d)2问n为何种数值时，Kn既是欧拉图又是哈密顿图。问k为何值时，k-正则图既是欧拉图又是哈密顿图。解 n为奇数时，Kn既是欧拉图又是哈密顿图。k为大于或等于n/2的偶数时，k-正则图既是欧拉图又是哈密顿图。3判别图中各图是否为欧拉图。 （a） （b）解（a）所有顶点的度都是偶数，它是为欧拉图。（b）并非所有顶点的度都是偶数，它是不是欧拉图（根据定理7.11。）411个学生在一张圆桌旁共进晚餐，要求在每次晚餐上每个学生的邻座都与其它各次晚餐的邻座不同。问这样共进晚餐能安排多少次。解 每个学生作为一个顶点，做成一个Kn图。就餐时邻座学生之间作一条边，每次就餐座位安排就是一个哈密顿回路。要求每次就餐邻座不同，就是求无任何公共边的哈密顿回路的个数。根据定理7.14，可以安排（11-1）/2=5次。5判别图中各图是否为哈密顿图，若不是，请说明理由，并回答它是否有哈密顿通路。 （a） (b) (c)解（a），(b) 是为哈密顿图。(c) 不是哈密顿图，也没有哈密顿通路。在图(c)中增加顶点k ，并对其顶点做二着色，构成图(d)（如下）。图(d) 不是哈密顿图，也没有哈密顿通路。因为图中白色顶点比黑色顶点多两个。故(c) 不是哈密顿图，也没有哈密顿通路。否则它的哈密顿回路或哈密顿通路必定经过顶点k（k在两个二度顶点之间的边上），从而图(d) 也是哈密顿图，也有哈密顿通路，矛盾。 k （d）练习9.41. 对给出的有向图G:（1）计算它的邻接矩阵A及A2，A3，A4，A5。（2）计算它的路径矩阵B。（3）计算它的可达性矩阵P。（4）请通过上述矩阵判断有几条长度为2的回路？从c到b有几条长度为3的拟路径？解(1) 它的邻接矩阵A=A2=A3=A4=A5=(2)它的路径矩阵B=(3)它的可达性矩阵P=（4）从A2中可以知道，有2条长度为2的回路。(bcb, cbc)从A3中可以知道，从c到b有3条长度为3的拟路径。(cbcb, ceab, cdab)从c到b有2条长度为3的路径。(ceab, cdab)2. 对给出的有向图G: v1 v2 v3v4 v5（1）计算它的邻接矩阵A及A2，A3，A4，说出从v1到v4的长度为l，2，3，4的拟路径各有多少条。 （2）计算AA，A A，说出它们中第2，3分量及第4，4分量的意义。 （3）计算它的路径矩阵B及可达性矩阵P，并从P说出G的各强分图。解(1) 它的邻接矩阵A= v1到v4的长度为1的拟路径各有1条。A2= v1到v4的长度为2的拟路径各有1条。A3= v1到v4的长度为3的拟路径各有1条。A4= v1到v4的长度为4的拟路径各有2条。A5=(2) AA=A A