自考_赵振坤_离散第五章答案.doc

5.1习题参考答案 1、设无向图G有16条边，有3个4度结点，4个3度结点，其余结点的度数均小于3，问：G中至少有几个结点。 解：设度数小于3的结点有x个，则有34432x216解得：x4所以度数小于3的结点至少有4个所以G至少有11个结点 2、设无向图G有9个结点，每个结点的度数不是5就是6，证明：G中至少有5个6度结点或至少有6个5度结点。 答案：证明：由题意可知：度数为5的结点数只能是0,2，4,6，8。若度数为5的结点数为0,2，4个，则度数为6的结点数为9，7,5个结论成立。若度数为5的结点数为6,8个，结论显然成立。由上可知，G中至少有5个6度点或至少有6个5度点。 3、证明：简单图的最大度小于结点数。 认为题中应指定是无向简单图.证明如下：设简单图有n个结点，某结点的度为最大度，因为简单图任一结点没有平行边，而任一结点的的边必连有另一结点，则其最多有n-1条边与其他结点相连，因此其度数最多只有n-1条，小于结点数n.4、设图G有n个结点，n+1条边，证明：G中至少有一个结点度数3 。 给出证明如下：证明：设G中所有结点的度数都小于3，即每个结点度数都小于等于2，则所有结点度数之和小于等于2n，所以G的边数必小于等于n，这和已知G有n+1条边相矛盾。所以结论成立。 5、试证明下图中两个图不同构。 证明：同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系。我们可以看出，(a)图和(b)图中都有一个三度结点，(a)图中三度结点的某条边关联着两个一度结点和一个二度结点，而(b)图中三度结点关联着两个二度结点和一个一度结点，因此可断定二图不是同构的。6、画出所有5个结点3条边，以及5个结点7条边的简单图。 解：如下图所示： (与答案一致) 7、证明：下图中的图是同构的。 证明如下：在两图中我们可以看到有ae,bh,cf,dg 两图中存在结点与边的一一对应关系，并保持关联关系。8、证明：下面两图是同构的。 给出证明如下： 证明：找出对应关系：a-q, b-r, c-s, d-t, e-u, f-v, g-w, h-x 9、证明：三次正则图必有偶数个结点。 证明如下：由题意可知每个结点度数都是3度，即每个结点均为奇结点，根据有偶数个奇结点可知，三次正则图必有偶数个奇结点。 5.2习题参考答案 1、 给定图G，如下图所示，求出G中从A到F的所有初级路。 解：从A到F的初级路有：ABCF、ABEF、ADEF、ABECF、ABCEF、ADECF、ADEBCF 2、给定图G，如下图所示，找到G中从v2出发的所有初级回路。 认为图中少了一个箭头：从V1到V2有一箭头。从V2出发的初级回路有：V2V4V1V2、V2V3V4V1V2. 3、设G为无向连通图，有n个结点，那么G中至少有几条边？为什么？对有向图如何？ 解：若G为无向连通图，有n个结点，则G中至少有n-1条边。因为在n个结点的图中，任取一个结点为起始点，若要连通其他每个结点，则其他每个结点至少应有1度,此结点则有n-1度。因此总的度数至少为2n-2度，而度数为边的2倍，可算得边数为n-1. 对于有向图，若是弱连通，则与无向图一样至少为n-1,若是单侧连通也是如此，而强连通边数至少为n。(此题根据的答案更正)4、设V和E分别为无向连通图G的点割集和边割集，G-E的连通分支数一定是多少？G-V的连通分支数也是定数吗? 解： G-E的连通分支数一定是2，而G-V的连通分支数就不是定数了。有可能大于2.5、设有七人a,b,c,d,e,f,g,已知：a会讲英语，b会讲汉语和英语，c会讲英语、意大利语和俄语，d会讲日语和汉语,e会讲德语和意大利语，f会讲法语、日语和俄语，g会讲法语和德语，试问这七人间可以任意交谈吗？ 答：可以。设七个人为图中的7个结点，以他们之间有共同语言为条件画边，可以看出，七个人的结点在图中是连通的，因此这七个人间可以通过相互翻译任意交谈。6、一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个结点一次。 证明如下：必要性：如果图中的任何一个回路都不能包含所有结点,则可知未被包含在回路内的结点不能与其他结点中的某一结点连通。这与本图是强连通的相矛盾。因此必有这样一个路它至少包含每个结点一次。充分性：当G中有一个回路，它至少包含每个结点一次时，可以知道，任一结点可达其他所有结点，因此它是强连通的。7、若有简单图至多有2n个结点，每个结点度数至少为n，G是连通图。 又若简单图G至多有2n个结点，每个结点度数至少为n-1，那么G是连通图吗？为什么？ 答：G不再是连通图，假若n=1时，G中至多可有2个结点，而每个结点度数至少可以为0，显然这两个结点不能连通。以下是的答案：方法一：设v1、v2是这个简单图的任意两个结点，由已知可得，v1、v2的度数至少为n， （1）若v1、v2之间有边，则显然v1、v2是连通的。 （2）若v1、v2无边，则v1和剩下的结点中的n个结点有边相连，v2也和剩下的结点中的n个结点有边相连。因为剩下的结点最多只有2n-2个，由抽屉原理可得，至少存在一个结点，它和v1、v2都有边相连，此时v1和v2也是连通的。 由（1）（2）可知，结论成立 方法二：显然这个图中任意的一对结点的度数之和大于等于2n，所以这个图是汉密尔顿图，所以这个图是连通的。8、简单图G有n个结点，e条边，设e0.5(n-1)(n-2),证明：G是连通的。 证明如下：n个结点的简单无向图，连通的最低条件是有n-1条边。而e0.5(n-1)(n-2) 可得en-1，因此G是连通的。上面的答案是错误的，纠正如下：因为一个连通图至少要有n-1条边，但并不是说至少有n-1条边的图一定是连通图。并且容易验证这个结论不成立。 证明如下： 在图G中，它的结点数为n，设v是G中任一结点，若把v去掉后，其它n-1结点，每个结点度数最多有n-1度，因此n-1个结点之间最多只有0.5（n-1)(n-2)条边，而e0.5(n-1)(n-2),所以至少有一条边连接v和其它结点。 下面我用数学归纳法进一步证明： （1）容易证明当n=1,2时，结论成立 （2）假设当n=k时，结论成立，即若e0.5（k-1)(k-2)时结论成立 （3）当n=k+1时，若此时每个结点度数为k，则结论显然成立，否则必存在一个结点v度数至多只有k-1度，即这个结点最多只有k-1条边和它相连。因为此时总的边数e0.5k(k-1),则其它k个结点之间的边数e0.5k(k-1)-(k-1)=0.5(k-1)(k-2)。根据归纳假设，显然这k个结点之间是连通的，而根据上面我们知道，至少有一条边使v和其它结点相连，所以此时这个图是连通的。 根据（1）（2）（3）可知结论成立。 5.3习题参考答案1、设图 G=,V=v1,v2,v3,v4的邻接矩阵 A(G)= 0 1 0 1 1 0 1 1 1 1 0 0 1 0 0 0 则 v1的入度deg(v1)是多少？ v4的出度deg(v4)是多少？ 从v1到v4长度为2的路有几条？ 解：1、v1的入度是3. v4的出度是1，因为 A2(G)= 2 0 1 1 2 2 0 1 1 1 1 20 1 0 1所以从v1到v4长度为2的路有1条。 2、有向图G如图所示，求G中长度为4的路径总数，并指出其中有多少条是回路。v3到v4的迹有几条。 答：长度为4的路径总数为15条，其中3条是回路。从v3到v4的迹有3条。 3、给定图G如下图 求： a)给出G的邻接矩阵 b) 求各结点的出、入度 c) 求从结点c出发长度为3的所有回路 解:邻接矩阵如图：(按字母顺序)M（G）0 0 1 0 0 1 0 1 0 0 0 0 0 1 10 0 1 1 0 0 1 0 0 0 a的出度是1，入度为1b的出度是1，入度为1c的出度是2，入度为3d的出度是2，入度为2e的出度是1，入度为1补充一下：出度就可以数该行的非零个数，入度则可数该列的非零个数从结点c出发长度为3的回路有：c-e-b-c , c-d-d-c4、给定G如图所示， a)写出邻接矩阵 b)G中长度为4的路有几条？ c)G中有几条回路？ 解：(有疑问，v2、v3间没有箭头，则此图有错，暂且理解为双向连通吧)a)M（G）0 0 0 0 1 1 0 1 0 00 1 0 0 11 0 1 0 00 1 0 1 0b) 有52条c)无数条(看到这里，以为v2、v3间的箭头应向右更符合其本意，因为图中有某种对应的关系。)5、试用矩阵法判断有向图。 G=a,b,c,d,|,连通性。 答：不连通补充一下：原矩阵为：M(G)=1 0 0 1 0 0 0 00 1 0 10 0 0 0由此矩阵得到的路径矩阵为： M4(G)=1 0 0 1 0 0 0 00 1 0 10 0 0 0可以发现图中些结点间没有路径存在。6、求出下图所示图G的邻接矩阵、可达矩阵，找出从v2到v3长度为3的初级路，并计算出A2,A3进行验证。 解：邻接矩阵为：M(G)=0 1 0 10 0 1 1 0 1 0 10 1 0 0其余答案略，用的话说就是：太麻烦了，自己算一算吧:)7、设图G中的边满足W(G-e)W(G),称为e为G的割边（桥）。 证明：e是割边，当且仅当e不包含在G的任一回路中。 证明：必要性：设e是G某一连通分支的一条边。假设e包含在G的某一回路中，若把e去掉后，显然该连通分支仍是连通的，所以W（Ge）W（G）。这和e是G的割边矛盾。充分性：设e是连接vi,vj的一条边，假设e不是割边。则把e去掉后，该连通分支仍是连通的vi到vj必有路，不妨设此路为vi.vj,则必有vi.vjevi,这和e不包含在G的任一回路中相矛盾，所以e是割边。5.4习题参考答案1、构造一个欧拉图，其结点数v和边数e满足下述条件： a) v、e的奇偶性一样； b) v,e的奇偶性相反。 如果不可能，请说明原因。 都可以实现：如图： 2、确定n取怎样的值，完全图Kn有一条欧拉回路。 答：n是奇数。因为完全图中，每个结点度数均为n-1，显然要有欧拉回路，n1必须是偶数，所以n是奇数。3、a)画一个有一条欧拉回路和一条汉密尔顿回路的图。 b)画一个有一条欧拉回路但没有一条汉密尔顿回路的图。 c)画一个没有一条欧拉回路，但有一条汉密尔顿回路的图。 解：如下： 4、如果图G中中度数为奇数的结点个数为0或2，则G可一笔画出吗？说明理由。 答：不一定。若该图是连通的，则可以一笔画出，否则不可以。如下图5、若无向图G是欧拉图，G中是否存在割边？为什么？ 答：不存在，因为欧拉图中，存在一条回路，包含各边一次且仅一次，所以任意去掉一条边，该图仍是连通的。 6、若一个有向图G是欧拉图，它是否一定是强连通？若有一个有向图G是强连通的，它是否一定是欧拉图？说明理由。 答：（1）是，因为存在一条欧拉回路，所以任意两个结点都是可达的（2）不是，如： 7、下图所示的G1和G2是否是汉密尔顿图，若是，请给出一条从a出发的汊密尔顿回路。 答：(1)是。a-i-h-g-d-e-f-b-c-j-a(2)不是。因为我找不出这样的回路，若学友们找出的话请告诉我，谢谢。 8、有割点的连通图是否能是汉密尔顿图？为什么？ 答：不能。根据定理5.4.3 9、某次会议有20人参加，其中每人都至少有10个朋友，这20人围一圆桌入席，要想使每人相邻的两位都是朋友是否可能？根据什么？ 答：可能。我们把每个人看成一个结点，若是朋友的用一条边连接。因此每个结点的度数都大于等于10，所以任意两个结点的度数之和都大于等于20，因此这个图中一定存在一条汉密尔顿回路，按这个回路排座位就可以了。 5.5习题参考答案1、证明：小于30条边的简单平面图有一个结点度数小于等于4. 证明：设结点数为v，边数为e（1）若v3，则结论显然成立。（2）若v3,则3v6e，解得v(e+6)/3假设图中每个结点的度数都大于4，即大于等于5。则所有结点的度数之和就大于等于5(e+6)/3，因此边数e5(e+6)/6 ，解得e30，这和已知边数小于30相矛盾。所以结论成立。 2、证明：每个面至少有4条边任何连通简单平面图中， m2n-4,其中n为结点数，m为边数。 证明：设这个图的面数为r，由欧拉公式nm+r=2得r=m-n+2因为deg(R)4，所以2m=deg(R)4(m-n+2)，解得m2n4 3、证明：下图（彼得森图）不是欧拉图，也不是平面图。 证明：（1）彼得森图每个结点的度数都等于3，所以不是欧拉图。（2）证明思路：只要能找出和K5或K3,3同胚的子图就行了。不过我找不出来，请各位学友找一找。4、证明：在有6个结点12条边的连通简单平面图中，每个面由3条边组成。 证明：由欧拉公式可得，r8，假设至少有一个面不是3条边围成，则必定大于3条边，所以2e3r24，所以e12，这与已知有12条边相矛盾。5.6习题参考答案1、说明具有6个结点的非同构的无向树的数目是多少。 答：应是6个。因为它是连通且无回路的无向树，因此在此树中只能有5条边。将这5条边按不同方式连接6个结点可得到6种形态的无向树，大家不妨画一画。2、下面哪一种图不是树？ a)无回路的连通图 b)有n个结点，n-1条边的连通图； c)每对结点间都有路的图； d)连通但删去一条边则不连通的图。 答：c)不是树。每个结点都有路，则也包括回路，而树是无回路的，因此c)不是树。3、连通图G是一棵树 ，当且仅当满足下述条件中哪一个？ a)有些边不是割边； b)每条边都是割边； c)无边割边； d)每条边都不是割边； 答：b)是树，因为在树中，删去任一条边均使图变得不连通，则此边就是割边。4、一个树有2个4度结点，3个3度结点，其余结点都是叶子，则叶子数是多少？ 解：设叶子数为n,则根据树的定义和图中总度数是边数的2倍，可列出方程如下：24+33+n1=2(n+2+3-1)解之得：n=95、画出结点数n5的所有不同构的树。 解：如下图： 6、设图G是一棵树，它有n2个2度分枝点，n3个3度分枝点，.nk个k度分枝点，求G中叶结点数。 解：同第4题的解法，设叶结点数为n1，则有：n1+2n2+3n3+.knk=2(n1+n2+n3+.+nk-1)解之得：n1=n3+2n4+3n5+.+knk+2+2 7、某城市拟在六个区之间架设有线电话网，其网点间距离如下面有权图矩阵给出，试给架设线路的最优方案，请画出图，并计算出线路的长度。 A= |0 1 0 2 9 0 | |1 0 4 0 8 5 | |0 4 0 3 0 10|2 0 3 0 7 6 | |9 8 0 7 0 0 | |0 5 10 6 0 0|解：要解本题，实际上是求该网点组成的图的最小生成树，呵呵，这对学过数据结构的同学来说是比较容易的：请看下图：线路的长度为1+2+3+5+7=18 8、求算式(a+(b*c)*d)-e)(f+g)+(h*i)*j的树形表示。 解：如图所示： 9、画出下图中的一棵最小生成树，并写出该生成树的关系矩阵。 答：注意，由于题图中所给权值位置不对，将其作了挪动。大家能明白吧。该生成树的关系矩阵如下： M(A)= |0 1 1 1 0 0 | |1 0 0 0 0 0 | |1 0 0 0 1 0 |1 0 0 0 0 0 | |0 0 1 0 0 1 | |0 0 0 0 1 0 | 10、设T1和T2是连通图G的两棵生成树，a是T1中但不在T2中的一条边。证明存在边b，它在T2中但不在T1中，使得（T1-a)b和(T2-b)a都是G的生成树。 以下是峰飞同学给出的证明：(感谢峰飞)首先证明存在边b，它在T2中但不在T1中。设不存在边b，它在T2中但不在T1中。也就是说T2中的所有边都T1中。因为存在边a,它在T1中但不在T2中，所以有T2是T1的真子集。T1是树，且有T1和T2有同样的结点，T1的所有真子集不可能是树，有T2不是树，这与T2是树相矛盾。所以必存在边b，它在T2中但不在T1中。设边b在T2中但不在T1中，边a在T1中但不在T2中(T1-a)Ub(T1Ub)-a,T1Ub后必存在唯一的环。设边a不在此环中，那么有此环中的所有边都在T2中，也就是说T2中存在环，这与T2是树相矛盾，也就是说，T1Ub的环中有边a，那么T1Ub-a，也是连通的并且没有