9图习题答案

练习9.11.（l）证明：n个顶点的简单图中不会有多于2)1(nn条边。（2）n个顶点的有向完全图中恰有2n条边。证:（l）由于简单图是没有重边和环的无向图，所以任意两个顶点之间最多有1条边，n个顶点最多有C(n,2)=n(n-1)/2条边。（2）由于有向完全图是任何两个顶点都有有向边的图，所以n个顶点的边数总和为2nnnnnnn2.分别画出下面两个图的补图及它的一个生成子图。（1）（2）解:（1）补图生成子图(不唯一)（2）补图生成子图(不唯一)3.一个简单图，如果同构于它的补，则该图称为自补图。（1）给出一个4个顶点的自补图。（2）给出一个5个顶点的自补图。（3）是否有3个顶点或6个顶点的自补图？（4）证明一个自补图一定有4k或4k＋1个顶点（k为正整数）。解（1）4个顶点的自补图：（2）5个顶点的自补图：（3）没有。（4）证设G为自补图，有n个顶点。我们已知n个顶点的完全图有2)1(nn条边，因此G应恰有4)1(nn条边。故或者n是4的整数倍，或者n–1是4的整数倍，即图G一定有4k或4k＋1个顶点（k为正整数）。4.（l）证明图中（a）与（b）同构。(a)(b)（2）给出所有不同构的4个结点的简单图的图示。证（l）在图（a）图（b）间建立双射hvABDIJCEGHFh(v)可逐一验证(不赘)ADCBEFGHIJ(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时，命题成立。设图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.u12…kvv1v2v7v10v4v3v8v9解图中有向图的强分图有：{v1,v2},{v1,v2,v2,v1},{v3,v4,v5},{v3,v5,v4,v3,v4,v5,v5,v4},{v6},{v6,v6},{v7,v8,v9},{v7,v8,v8,v9,v9,v7},{v10},{}图中有向图的单向分图有：{v1,v2,v3,v4,v5,v6},{v1,v2,v2,v1,v1,v4,v2,v3,v4,v3,v3,v5,v4,v5,v5,v4,v3,v6},{v7,v8,v9,v10},{v7,v8,v8,v9,v9,v7,v7,v10}图中有向图的弱分图有：{v1,v2,v3,v4,v5,v6},{v1,v2,v2,v1,v1,v4,v2,v3,v4,v3,v3,v5,v4,v5,v5,v4,v3,v6},{v7,v8,v9,v10},{v7,v8,v8,v9,v9,v7,v7,v10}4.有7个人a，b，c，d，e，f，g分别精通下列语言，问他们7人是否可以自由交谈（必要时借助他人作翻译）。a精通英语。b精通汉语和英语。c精通英语、俄语和意大利语。d精通日语和英语。e精通德语和意大利语。f精通法语、日语和俄语。g精通法语和德语。解下图中7个顶点表示7个人，关联两个顶点的边表示两个人同时精通某一种语言：由于该图是连通的，因此他们7人是可以自由交谈（必要时借助他人作翻译）。5.v是简单连通图G的割点，当且仅当G中存在两个顶点v1，v2，使v1到v2的通路都经过顶点v。试证明之。abdcegf证充分性是显然的。必要性：设顶点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）既非欧拉图也非哈密顿图。2．问n为何种数值时，Kn既是欧拉图又是哈密顿图。问k为何值时，k-正则图既是欧拉图又是哈密顿图。解n为奇数时，Kn既是欧拉图又是哈密顿图。k为大于或等于n/2的偶数时，k-正则图既是欧拉图又是哈密顿图。3．判别图中各图是否为欧拉图。（a）（b）（a）(b)(c)(d)解（a）所有顶点的度都是偶数，它是为欧拉图。（b）并非所有顶点的度都是偶数，它是不是欧拉图（根据定理7.11。）4．11个学生在一张圆桌旁共进晚餐，要求在每次晚餐上每个学生的邻座都与其它各次晚餐的邻座不同。问这样共进晚餐能安排多少次。解每个学生作为一个顶点，做成一个Kn图。就餐时邻座学生之间作一条边，每次就餐座位安排就是一个哈密顿回路。要求每次就餐邻座不同，就是求无任何公共边的哈密顿回路的个数。根据定理7.14，可以安排（11-1）/2=5次。5．判别图中各图是否为哈密顿图，若不是，请说明理由，并回答它是否有哈密顿通路。解（a），(b)是为哈密顿图。(c)不是哈密顿图，也没有哈密顿通路。在图(c)中增加顶点k，并对其顶点做二着色，构成图(d)（如下）。图(d)不是哈密顿图，也没有哈密顿通路。因为图中白色顶点比黑色顶点多两个。故(c)不是哈密顿图，也没有哈密顿通路。否则它的哈密顿回路或哈密顿通路必定经过顶点k（k在两个二度顶点之间的边上），从而图(d)也是哈密顿图，也有哈密顿通路，矛盾。练习9.41.对给出的有向图G:（a）(b)(c)k（d）（1）计算它的邻接矩阵A及A2，A3，A4，A5。（2）计算它的路径矩阵B。（3）计算它的可达性矩阵P。（4）请通过上述矩阵判断有几条长度为2的回路？从c到b有几条长度为3的拟路径？解(1)它的邻接矩阵A=0101100001110100010000010A2=0011100010011121101000100A3=1112000100111310111211010A4=1222211010123321113101112A5=2325301112343631233211131(2)它的路径矩阵B=1111111111111111111111111(3)它的可达性矩阵P=1111111111111111111111111（4）从A2中可以知道，有2条长度为2的回路。(bcb,cbc)从A3中可以知道，从c到b有3条长度为3的拟路径。(cbcb,ceab,cdab)从c到b有2条长度为3的路径。(ceab,cdab)2.对给出的有向图G:（1）计算它的邻接矩阵A及A2，A3，A4，说出从v1到v4的长度为l，2，3，4的拟路径各有多少条。（2）计算A○Aι，Aι○A，说出它们中第2，3分量及第4，4分量的意义。（3）计算它的路径矩阵B及可达性矩阵P，并从P说出G的各强分图。解(1)它的邻接矩阵A=0101010000000000110001010v1到v4的长度为1的拟路径各有1条。A2=1110001010000001000011100v1到v4的长度为2的拟路径各有1条。A3=1101011100000000101011010v1到v4的长度为3的拟路径各有1条。A4=1211011010000001110012110v1到v4的长度为4的拟路径各有2条。v1v2v3v4v5A5=2211012110000001101022110(2)A○Aι=01010100000000001100010100100010011000101000100000=2101201000000001002120012Aι○A=01000100110001010001000000101010000000000110001010=1000003120011000202000000A○Aι中第2，3分量为0，表明没有两条边以v2，v3为起点而终止于同一终点；第4，4分量为1,是v4的出度。Aι○A中第2，3分量为0，表明没有两条边起始于同一顶点而以v2，v3为终点；第4，4分量为3,是v4的入度。（3）它的路径矩阵B=1111011110000001111011110可达性矩阵P=1111011110001001111011111由P看出各强分图的顶点集合分别是{v1}，{v3}，{v2，v4，v5}.由P看出此图为单向连通图。