您好、欢迎来到现金彩票网!
当前位置:刘伯温四肖中特料 > 推理结点 >

交大版《离散的数学结构》标准答案doc

发布时间:2019-06-07 11:20 来源:未知 编辑:admin

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  离散数学辅助教材 概念分析结构思想与推理证明 离散数学习题解答 习题六 (第六章 图论) 1.从日常生活中列举出三个例子,并由这些例子自然地导出两个无向图及一个向图。 [解] ①用V代表全国城市的集合,E代表各城市间的铁路线的集合,则所成之图G=(V,E)是全国铁路交通图。是一个无向图。 ②V用代表中国象棋盘中的格子点集,E代表任两个相邻小方格的对角线的集合,则所成之图G=(V,E)是中国象棋中“马”所能走的路线图。是一个无向图。 ③用V代表FORTRAN程序的块集合,E代表任两个程序块之间的调用关系,则所成之图G+(V,E)是FORTRAN程序的调用关系图。是一个有向图。 2.画出下左图的补图。 [解] 左图的补图如右图所示。 3.证明下面两图同构。 [证] 存在双射函数(:V→V′及双射函数( : E→E′ ( (v1)=v1′ ( (v1,v2)=(v1′,v2′) ( (v2)=v2′ ( (v2,v3)=(v2′,v3′) ( (v3)=v3′ ( (v3,v4)=(v3′,v4′) ( (v4)=v4′ ( (v4,v5)=(v4′,v5) ( (v5)=v5′ ( (v5,v6)=(v5′,v6′) ( (v6)=v6′ ( (v6,v1)=(v6′,v1′) ( (v1,v4)=(v1′,v4′) ( (v2,v5)=(v2′,v5′) ( (v3,v6)=(v3′,v6′) 显然使下式成立: ( (vi,vj)=(vi,vj′)( ( (vi)=v i′∧( (vj)=vj′ (1≤i·j≤6) 于是图G与图G′同构。 4.证明(a),(b)中的两个图都是不同构的。 图G中有一个长度为4的圈v1v2v6v5v1,其各顶点的度均为3点,而在图G′中却没有这样的圈,因为它中的四个度为3的顶点v1(,v5(,v7(,v3(不成长度的4的圈。 图G中′有四个二度结点,v6(,v8(,v4(,它们每个都和两个三度结点相邻,而G中一个区样的结点都没有。 在(b)中,图G(中有一2度结点v3(,它相邻的两个项点v2(,v4(的度均为4,而在图G中却没有这样的点。 5.一个图若同构于它的外图,则称此图为自补图。在满足下列条件的无向简单图中: 1) 给出一个五个结点的自补图; 2)有三个或一结点的自补图吗?为什么? 3)证明:若一个图为自补图,则它对应的完全图的边数不清必然为偶数。 [解] 1) 五个结点的自补图如左图G所示 同构函数( : V→V及( : E→如下: ( (a)=a ((a,b)=(a,c) ( (b)=c ((b,c)=(c,e) ( (c)=e ((c,d)=(e,d) ( (d)=b ((d,e)=(b,d) ( (e)=d (e,a)=(d,a) 2)(a=3为奇数,所以由下面3)的结论,不可能有自补图。 (b)有五个结点的自补图。1)中的例子即是一个五个结点的自补图。 3)证:一个图是一个自补图,则它对应的完全图的边数必为偶数。 因为若一个图G是自补图,则G∪=对应的完全图,而且E∩=φ,G现同构,因此它们的边数相等,即E=,因此对应的完全图的边数E*=E+=2E,是偶数。 实际上,n个项点(n>3)的自补图G,由于其对应的完全图的边数E*=,因此有=2E,为偶数。这里n≥4。对于所有大于或等于4的正整数,都可表达成n=4k,4k+1,4k+2,4k+3的形式,这里k=1,2,…。其中只有n=4k,4k+1,才能使为偶数,所以自补图的项点数只能是4k或4k+1形式,(k∈N) 6.证明在任何两个或两个以上人的组内,总存在两个人在组内有相同个数的朋友。 [证] 令上述组内的人的集合为图G的项点集V,若两人互相是朋友,则其间联以一边。所得之图G是组内人员的朋友关系图。显然图G是简单图,图中项点的度恰表示该人在组内朋友的个数,利用图G,上述问题就抽象成如下的图认论问题:在简单图G中,若V≥2,则在G中恒存在着两个项点,v1,v2∈V,使得它们的度相等,即deg(v1)=deg(v2)。其证明如下: 若存在着一个项点v∈V,使得deg(v)=0,则图G中各项点的度最大不超过n-2。因此n个项点的度在集合{0,1,2,…,n-2}里取值,而这个集合只有n-1个元素,因此,根据鸽笼原理,必有两个项点的度相同。 若不存在一个度为零的项点,则图G中各项点的度最大不超过n-1。因此n个项点的度在集合{1,2,…,n-1}中取值,这个集合只有n-1个元素,因此,根据鸽笼原理,必有两具项点的度相同。 7.设图G的图示如右所示: 1) 找出从A到F的所有初级路; 2)找出从A到F的所有简单路; 3)求由A到F的距离。 [解] 1)从A到F的初级路有7条 P1 : (A,BC,F),P2 (A,B,C,E,F),P3 : (A,B,E,F) P4 : (A,BE,C,F),P5 : (A,D,C,E,F),P6 : (A,D,E,C,F) P7 : (A,D,E,B,C,F)。 2)从A到F的简单路有9条 除了上述1)中7条外,不有P8 : (A,D,E,C,B,E,F) P9 : (A,D,E,B,C,E,F)。 3)从A到F的距离为3。 由图可看出,显然从A到F,一步不可能到达,二步也不可到达;但有长度为3的路,比如P1,P3,P5等能从A到F,故从A到F的距离为3。 8.在下面的图中,哪此是边通图?哪些是简单图? (a) (b) (c) [解] (1)图(2)与图(b)不连通,它们能分成两个边通支。所以只有图(c)是连能图。 (2)图(c)是简单图,图为它显然无平等边,无自环。图(a)、(b)是多重图(a)有平行边(b)有自环。 9.求出所有具有四个结点的简单无向连通图。 [解] 在不同构的意义下,具有四个结点的简单无向连通图共有6个。 如下面所示: (实际上,具有四个结点的简单图共有11个,这可由P定理得证。参见卢开澄的《组合数学一算法与分析》上册P241-P244)。 10.设G是一个简单无向图,且为(n,m)图,若 证明G是连通图。 [证] 用反证法。假若简单无向图G不是连通图,那么G必可成K(≥2)个连通分支G1,G2,…,Gk,每个连通分支Gi(1≤i≤k)都是一个简单无向图,因此它们分别为(n1,m1),(n2,m2),…(nk,mk)图显然有n=n1+n2+…nk,m=m1+m2+…mk,且ni≤n-1(1≤i≤k)于是有 m=m1+m2+…mk =(n-1)··((n1-1)+(n2-1)+…+(nk-1)) =(n-1)((n1+n2+…+nk)-k) = (n-1)(n-k) ≤(n-1)(n-2) (k≥2) 这与已知M>(n-1)(n-2)矛盾。 因此假设错误,G是连通图。 11.设G=(V,E)是无向完全图(无自环),V=n 求G中有多少初级圈? 设e∈E,求含有e的初级圈有几个? 设u,v∈V,u≠v,求由u到v有几条初级路? [解] 1)在一个有n个结点的无向完全图(无自环)中,构成一个初级圈,至少需3个结点,至多有n个结点,故G中初级圈的个数为 即将从n个结点中选出的k个结点进行排列,然后除去重复:每个排列的倒排列(除2);长为k的圈排列可形成k个线)含有边e的初级圈为 即,从u到v的直接边(完全图,该边存在)是一条;再将该直接边加到其它初级路里,就构成了含边(u,v)的初级圈,从而由2)可得如上数值。 12.试证在简单有向图中 每个结点及每条边都属于且只属于一个弱分图; 每个结点及每条边都至少属于一个单向分图。 [证] 1)有向图中的弱连通性建立了G中结点集合V上的等价关系,因此构成了V上的一个划分;同时,还建立了边集上的一个划分。因此,每一个弱连通支就是一个“划分块”。设G1,G2,…,Gk为G的所有弱连通分图,则有: V(G)=V(G1)∪V(G2)…∪V(Gk) E(G)=E(G1)∪E(G2)…∪E(Gk) 并且,当i≠j时,V(Gi)∩V(Gj)=φ,E(Gi)∩E(Gj)=φ。因此,每个结点及每条边都属于且只属于一个弱图。 2)有向图中的单向连通性建立了G中结点集合V上的一个相容关系,因此构成了V上的一个覆盖;同时,还建立了边集上的一个覆盖;每一个单向分图就是一个“覆盖快”。设G1,G2…,Gk为G的所有单向分图,则有 V(G)=V(G1)∪V(G2)∪…∪V(Gk) E(G)=E(G1)∪E(G2)∪…∪E(Gk) 因此,每个结点及每条边都至少属于一个单向分图。 13.试用有向图描述出下述问题的解法路径:某人m带一条狗d,一只猫c和一只兔子r过河,没有船,他每次游过河时只能带一只动物,当没有人管理时狗和兔子不能相处,猫和兔子也不能相处。在这些条件的约束下,他怎样才能将这三只动物从北岸带往南岸? [解] 将人,狗,兔中任意几种在一起的情况看作是一种状态;一个布局是一个二元组,由两个互补的状态构成,二元组的前者表示河北岸的状态,后者表示河南岸的状态。初始布局为(pdcr,φ),终止布局为(φ,pdcr)安全布局有十种,不安全布局有六种,它们是: (dr,pc),(cr,pd),(dcr,p), (pc,dr),(pd,cr),(p,dcr)。 按题意构造有向图,其解法路径如下: 14.求下列图中的所有强连通支,单向连通支,弱连通支。 [解] 1)有六个强连通支,它们是: G1=({v1,v2,v3,v9,v10},{(v1,v2),(v2,v9),(v9,v10),(v10,v1),(v2,v3),(v3,v9)}) G2=({v4},φ),G3=({v8},φ),G4=({v7},φ), G5=({v5},{(v5,v5)}),G6=({v6},φ)。 2)有四个单向连通支,它们是: G1=({v1,v2,v3,v4,v9,v10},{(v1,v2),(v2,v9),(v9,v10),(v10,v1),(v2,v3),(v3,v9),(v3,v4)}), G2=({v4,v7,v8},{(v7,v8),(v8,v4)}), G3=({v5},{v5,v5}),G4=({v6},φ) 3)有三个弱连通支,它们是 G1=({v1,v2,v3,v4,v7,v8,v9,v10},{(v1,v2),(v2,v9),(v9,v10),(v10,v1),(v2,v3),(v3,v9),(v3,v4),(v7,v8),(v8,v4)}) G2=({v5},{(v5,v5)}),G3=({v6,φ}) 15.给出有向图如下所示: 1) 求它的邻接矩阵A; 2) 求A2,A3,A4,指出从v1到v4长度为1,2,3,4的路径各有几条? 3) 求AT,ATA,AAT,说明ATA和AAT中元素(2,3)和(2,2)的意义; 4) 求A(2),A(3),A(4)及可过矩陈R; 5) 求出强度通支。 [解] 1)它的邻接矩阵 从v1到v4长度为1的路有1条,是(v1,v4); 从v1到v4长度为2的路有1条,是(v1,v2),(v2,v4); 从v1到v4长度为3的路有2条,是: (v1,v2),(v2,v8),(v3,v4); (v1,v4),(v4,v2),(v2,v4)。 从v1到v4长度为4的路有3条,是: (v1,v2),(v2,v3),(v3,v2),(v2,v4); (v1,v2),(v2,v4),(v4,v2),(v2,v4); (v1,v4),(v4,v2),(v2,v3),(v3,v4); 3) AT= 在ATA中,元素(2,3)=0的意义是: 不存在着这样的结点,从它发出的边同时终止于结点v2及v3; 在ATA中,元素(2,3)=3的意义是:(v2)=3,即结点v2的入度为3。 在AAT中,元素(2,3)=1的意义是:存在着一个结点,v4从v2及v3发出的边同时终之于它; 在AAT中,元素(2,2)=2的意义是:(v2)=2,即结点v2的出度为2。 4) 5)·强连通支为 G1=({v1},φ) G2=({v2,v3,v4},{(v2,v3),(v2,v4),(v3,v2),(v3,v4),(v4,v2)}) 16.利用Dijkstra算法,求出下面图中从u到v的所有最短路径及路径长度。 (1) (2) 17.在Dijjkstra算法中,增加一个记忆系统,使得此算法不仅能给出从u到v的最短路的路长,而且可以给出一条最短路径。 [解] 观察Dijkstra算法的N02,容易看出每当确定出一个新的标记点t0 时,由初始结点u到结点t0的最短路就可以确定下来了(但可能不唯一)。因而,该路中心至少有一点P。直接与结点t0相邻。故此,修正的算法如下: 算法一:在确定从结点u到结点v的最短路的路长的同时, No1. P:={u};T:=V\P;S(u):=[u];d(u):=0; ((t∈T)(d(t):=∞) No2. ((t∈T)(d(t):={d(t),d(P)+W(P,t)}; ((t0∈T)((t∈T)(d (t0)≤d(t)); ((P0∈P)(d(t0)=d(p0)+W(p0,t0)); S(t0):=[S(p0) t0]; (表结构) No3. P:=PU{t0};T:=T\{t0};mark(t0):=d(t0) No4. if t0=v then exit else goto No2; 我们也可以采用回溯方法。 算法二:在Dijkstra算法之后增加一个回溯系统,求出一条从u到v的最短路径。 No1. P:={u};T:=V\P;d(u):=0;((t∈T)(d(t):=∞); No2. ((t∈T)(d(t):={d(t),d(p)+w(p,t)}); ((t0∈T)((t∈T)(d(t0)≤d(t)); No3. P:=PU{t0};T:=T\{t0};mar(t0):=d(t0) No4. S:=[v];g:=v No5. ((p∈P)(d(p)=d(g)=W(p,q)); s:=[p s]; q:=p; No6. ifg=u then exit else goto No3 以上两种算法都直接给出了从结点u到结点v的最短路径。但是,算法一的记忆比较庞大,而算法二又重复了Dijkstra算法中的一些判断过程。我们综合以上两种算法,又有如下 算法三:在求出从结点u到结点v的最短路径之间各结点的最短长度d值以及前驱结点(紧前结点) No1. P:= {u};T:=V\P;d(u):=0;((t∈T)(d(t):=∞); No2. ((t∈T)(d(t):={d(t),d(p)+w(p,t)}); ((t0∈T)((t∈T)(d(t0)≤d(t)); ((p∈P)(d(p)=d(p0)+w(p0,t0)); No3. P:=PU{t0};T:=T\{t0};mark(t0):=(p0,d(t0)); No4. if t0=v then exit else goto No2; 算法三并未直接给出从结点u到结点v的最短路径,但它的记忆系统比较简单,计算方便。要给出从结点u到v的最短路经时,只要从终步v开始,根据标记的第一个分量,向前回溯即可得到。 18.判断下列图示能否一笔画。 [解] 根据本章§2定理2:图中奇结点的个数是偶数。所以奇结点的个数为2k,当k=0,1时,此图是一笔画的,而当k>1时,则此图是k笔画的。于是 图(a),不是一笔画,因为它的奇结点为四个(用表示); 图(b),(c)都是一笔画,因为它的奇结点是二个; 19.设G是有向图,证明G是Euler图的充要条件是:G是强连通的,且G中每一结点的进度等于出度。 [证] 必要性 若G是Euler图,则G中含有有向Euler圈,并且G中无狐立点,从而G中每个结点都与一条有向边相连。由于每条向边都必须在有向Euler圈上,因此每个结点也都在有向Euler圈上,所以从任一结点出发都可到达另一任意结点,故此G是强连通的。 而且,又由于每条有向边只能在有向Euler圈中出现一次,于是每一个结点,有一边进来,就应有一边出去,再有一边进来,就应再有一边出来;这样,每一结点的进度必然等于度。 充分性 因为G是强连通的,故G中任何两个结点都可互相到达,因此G中存在着有向简单圈。不妨设C是G中长度最长的有向简单圈套 ,则C必是G中的有向Euler圈,从而G是Euler图。 否则,必有边e不在圈C中,但e的一个端点在C上,不然的话,则图G一定不强连通,这和已知条件矛盾。由于对于图G中每个点v,(u)= (u),并且C是一个有向圈,从而对图G1=(V(G),E(G)\C)仍有=(u)= (u),故此在G1中一定存在含有e的有向圈C1中一定存在含e的有向圈C1,C∪C1显然仍是G中的有向圈,且此有向圈的长度大于C的长度,这和C是G中最长的有向圈的假定相矛盾,故C一定是G中的有向Euler圈。 这个有向Euler圈C可利用一个算法给出: No1. 以G中任一结点出发,沿着有向边走 成一个圈,而且是简单圈套; No2. 若此圈已是有向Euler圈,出口; No3. 否则,除此圈外,必仍有若于边不在其中,这些边中至少有一条边以引中至少有一条边以此圈中的某一结点为起点,以这个结点为起点走出一个圈(这个别圈不应含原圈中的任一边,并且是一简单圈); No4. 将此圈插入原圈中,得到一个新的长度更长的简单圈,然后goto No2. 20.设G是连通的无向图,且有2k>0奇结点。证明:在G中存在k条边不重的简单路G1,C2,C3…Ck,使 E(G)=E(C1)∪E(C2)∪E(E3)∪…∪E(Ck) [证] 设v1,v2,…,vk,vk+1…,v2k为G中的2k个奇结点,在vi和vi+k两个结点间连以新边ei*(i=1,2,…,k),所得之图记为G*,则G*的每个结点的度均为偶数,又由于G连通,则G*也是连通的,根据Euler定理,知在G*中存在Euler圈C*。若我们从C*中除去这k条新边ei*(i=1,2,…,k),则C*就分解成k条边不重的简单路C1,C2,C3…Ck,并且显然有E(G)=E(C1)∪E(C2)∪E(C3)…∪E(Ck)。 21.构造一个长度为16的De Bruijn序列。 [解] 我们定义一个有向图D4如下:D4的项点是3位二进制数p1p2p3,其中pi=0或1。存在一条以项点p1p2p3为起点,以项点q1q2q3为终点的向边(p1p2p3,q1q2q3)当且仅当p2=q,p3=q2。另外,D4的每条有向边(p1p2p3,p2p3p4)上都标以四位二进制数p1p2p3p4。D4如下图1所示: 显然,D4是连通的,并且D4的每个项点都具有入度2和出度过2,故由有向图的Euler定理,知D4中存在着一条有向Euler圈,这条有向Euler圈从图1可容易得到为 a1,a2,,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15,a16。 它可看作是D4的弧的序列,它产生一个长为24=16位二进制数1(它恰好是由ai(i=)的第一位数字组成),和鼓轮表面的设计要求符合。用这个16位二进制数设计的鼓轮如图2所示: 这个16位二进制数就是要求的长度为16的De B ruijn序列。 图2 22.1)画一个图示,使它既有一条E-圈,又有一条H—圈; 2)画一个别图示,使它有一条E—圈,但没有一条H—圈; 3)画一个图示,使它没有一条E—圈,但有一条H—圈; 4)画一个图示,使它既没有一条E—圈,又没有一条H—圈; [解] (a)图1既有E-圈,又有H圈。 (b)图2有E-圈,但没有H-圈。 (c)圈3有H-圈,但没有E-圈。 (d)图4既没有E-圈,又没有H-圈。 图2不存在H-圈,是因为存在着S={中间点},使W(G\S)=2个连通支数,而 S =1,从而W(G\S)? S 故由定理1判定H-图的必要条件可知不存在H-圈。 图3不存在E—圈,是因为G中存在8个结点的度均为3,是奇数。图4中不存在H—圈,因为G是一个偶图(二分图),而偶图要有圈,必须结点数为偶数(即X=Y,V=X+Y=2X),而G的结点数为11个,是奇数,不是偶数。 23.若G=(V,E)有Hamilton路,证明对V中任一非空子集S,均有W(G\S) S +1。 [证] 设G=(V,E)中的Hamilton路为C,路的两个端点为v1,及v2。我们给G增加一个新结点,v*及两个新边(v*,v1)和(v*,v2)而得到图G*,于是G*中就有Hamilton圈G*(它由Hamilton路C及关联新点v*的两个新边构成)。令S*=S∪{v*},则显然有G\S=C*\S*。从而根据定理1有Hamiltou圈的必要条件,有 W(G\S)=W(G*\S*)≤S*=S+1 。 24.雄辩地证明下面的图示中没有Hamilton路。 [证] (1)将图1标记为图3。 图3中存在着Hamilton路,此如H=(b,c,h,g,k,i,d,e,a,f,j) 但是,图3中不存在Hamilton圈。因为,结点e,j均为2度结点,故若Hamilto圈,则引H-必通过e,j及其关联的四条边,因此在边(a,e)及(f,j)上各增加一个结点l,m,得到图4,显然,图1,即图3有H-圈当且仅当图4有H-圈。 取S={a,e,l,g,i,c},则G\S={m,f,j,k,b,h,d}这7个孤立点,因此W(G\S)=7,而S=6,故此有 W(G\S)?S 根据定理1,有H-圈的必要条件,知图4中没有H-圈,因此图中没有H-圈。 (2)图2中不存在H路。 证法一:将图中偶结点全标为A,奇结点全标为B,取S={偶结点}则G\S为8个孤立奇结点,于是W=8,而 S =6。从而有W(G\S)?S+1,于是根据第23题的结论,有H-路的必要条件,知无H-路存在。 证法二:注意到图中的标号,奇、偶结点交错,因此是一个偶图(二分图)于是若有H-路,则奇偶结点之差不得超过1。但是这里奇结点(标为B)有8个,偶结点(标为A)有6个,其差为2。所以不可能有一条H-路。 25.有七位客人入席,A只会讲英语;B会讲汉语;C会讲英语,意大利语及俄语;D会讲汉语及日语;E会讲意大利语及德语;F会讲法语,日语及俄语;G会讲德语和法语。问主人能否把诸位安排在一张圆桌上,使每一位客人与左右邻不用翻译便可交谈。若能安排,请给出一个方案。 [解] 能安排,其方案为: H=(A,B,D,F,G,E,C,A) 将每个人作为一个项点,如果两个人会讲同一种语言,就在代表他们的二个项点间连一条边,边上标明二人公用的语言,这样就可得一简单无向图G。所求问题转化为图G中有无Hamilton圈问题。 而上边指出的圈H正好是图G的一条Hamilton圈,因此问题得到解决。 26.假设在一次集合上,任意两人合起来能够认识其余n-2 个人。证明这n个人可以排成一行,使得除排头与排尾外,棋逢对手余的每个人都认识自己的左右邻。 [证] 我们来构造一个n阶图G,图G的项点代表n个人,两个认识的人对应的顶点间连一条边,从而图G满足: 对任意二顶点u和v,都有deg(u)+deg(v)≥h-2(不包括u,v在内)。 所求问题转化为,证明图G中存在一条Hamilton路。为此,我们证明: 对任意二顶点u和v,都有deg(u)+deg(v)≥h-1。分情况证明如下: 1)若u和v相邻(即u和v表示之二人认识),则有 deg(u)+deg(v) ≥(n-2)+2=n>n-1 2)若u和v不相邻(即u和v表示之二人不认识)则仍有 deg(u)+deg(v) ≥n-1>n-2 否则,由已知deg(u)+deg(v)≥n-2知deg(u)+deg(v)=n-2。那么,G中除u和v外的余n-2个点,每个顶点都恰与u或v之一相邻。今考察其中一点w,设它与v相邻,则它必不与u相邻。于是对于v,w这一对顶点,它们都不与除去它们之后的n-2个顶点中之一顶点u相邻,这就与题设条件:任二顶点合起来都与其余n-2个项点相邻,相矛盾。 综合1),2)并且根据定理2,有Hamiltou路的充分条件,可知图G中存在着一条H路。 27.如何由无向图G的邻接矩阵判断G是否为二分图? [解] 二分图G=(V,E)实际上是项点集V的一个划分{X,Y},有两上划分块,而划分和等价关系对应,因此我们将判定G是二分图转化为判定某一相应的关系是等价关系。 No1. 令A:=(aij)nxn,其中aij= (于是A显然是对称短矩阵,即AT=A。) No2. 求A(2):=AοA=()nxn,其中=(aik∧akj)。 (由于(A(2))T=ATοAT=AοA= A(2) 故A(2)是对称矩阵。)vi,vj∈XVY,=1( vi,vj∈Y(同时) No3. 令B:=E∨A(2)=(bij),(其中E是n阶单位)其中 bij= No4. 求B(2)=BB=(),(其中E是n阶单位)其中=(bik∧bkj)。 No5. 求B(2)=B,(即B是传递的,因而是等价的。)输出“图G是二分图”,出口;否则(即B不是传递的,因而不是等价的。)输出“G不是二分图”,出口。 28.证明:如果G是二分图G为(n,m)图,那么 。 [证] 设二分图G=(V,E)的项点集V是划分为二部分X,Y。因为 V =n,所以不妨设,(这里k≥0)从而。 因于二分图的边数小于其对应的完全二分图的边数 故此: 29.设G=(V,E)是二分圈,V=V1∪V2,证明: 1)若G中有H—圈,则 V1 = V2 ; 2)若G中有H—路,则 V2-1≤ V1≤V2+1 。 [证] 1)证法一:若G中有H—图,由于G是二分图,则在G 中去掉V2后,就只剩下V1中的 V1 个孤立点;同样,在G中去掉V1后,就只剩下V2中的 V2 个孤立点。因此由定理1,有Hamilton圈的必要条件,可知: V1 =W(G\V2)≤ V2 , V2 =W(G\V1)≤ V1 因此,可得 V1 = V2 。 证法二:设C=(v1,v2,v3,…,vl-1,vl,v1)是二分图中的一条Hamilton圈,从而有V={v1,v2,…vl},于是 V =l。 不妨设v1∈V1,观察圈C中的各结点,有: v1∈V1(v2∈V2(v3∈V1( v4∈V2(…(vτ∈V2 从而有v1,v3…,vτ-1∈V1∪V2,故此 V1={v1,v3,…vτ-1},V2={v2,v4,…vτ} 所以 V1 == V2 。 2)证法一:若G中有H—路,由于G是二分图,则在G中去掉2后,就只剩下V1中的 V1 个孤立点;同样,在G中去掉V1后,就只剩下V2中的 V2 个孤立点。因此由习题23有Hamilton路的必要条件,可知 V1 =W(G\V2)≤V2 +1 V2 =W(G\V1) V1 +1,于是 V2-1≤V1 故此 V1 -1≤ V1 ≤V2 +1 。 证法二:设C=(v1,v2,…vτ)是二分图中的一条Hamilton路,从而V={v1,v2,…,v },于是 V =τ。根据1)的证法二: (a)若v1∈V1,vτ∈V1,则vτ-1∈V2 故此τ-1为偶数,τ为奇数,于是 V1 = 因此 V1 =V2 +1 (b)若v1∈V1 vτ∈V1,则τ为偶数,于是 V1 == V2 (c)若v1∈V2,vτ∈V1,同(b)可证 V1 =V2 (d)若v1∈V2,vτ∈V2,则同(a)可证 V2 =V1+1,即V2-1= V1 综合以上四点,有 V2-1≤V1≤V2+1 。 30.在下面的图示中,是否存在{v1,v2,v3,v4}到{u1,u2,u3,u4,u5}的完美匹配?若存在,请指出它的一个完美匹配。 [解] 不存在{v1,v2,v3,v4}到{u1,u2,u3,u4,u5}的完美匹配。 因为这两个互补结点子集的结点个数不相同。 31.某展览会共有25个展室,布置如下图所示,有阴影的展室陈列实物,无阴影的展室陈列图片,邻室之间均有门可通。有人希望每个展室都恰去一次,您能否为他设计一条路线? [解] 不能。 因为,若我们将每个展室看作一个项点,并且V1是无阴影展室的项点集,V2是有阴影展室的项点集,将邻室之间的门通道看作相应两顶点的边,于是我们得到一个二分图G。从而问题转化为问图G中是否有从起点(入口)uv1到终点(出口)v∈V2的一条Hamilton路?而这样的H路存在的必须条件是 V1= V2(参见29的2)证法=b))。但是V1=121≠3=V2,故不满足必要条件,所以没有从u到v的Hamilton路。 32.证明:小于30条边的平面简单图有一个结点的度数小于等于4。 [证] 用反法:假设简单平面图的所有结点的度数都大于4,因而都大于等于5,则由§2定理1,有 故此 n≤ 由于简单平面图无平等边,自环,所以任一区域都至少由三条或以的边围成,故利用欧拉公式的推论公式:m≤3n-6,有 m≤3· 因此,m≥30,这与已知条件m<30矛盾。所以,假设错误,小于30条边的简单平面图必有一个结点的度数小于等于4。 33.在由(r+1)2个结点构成的r2个正方形网格所组成的平面图上,验证Euler公式的正确性。 [证] 如此的平面图,结点数n=(r+1)2 边数m=(r+1)r+(r+1)r=2(r+1)r =2r2+2r 面数f=r2+1 (外部为-4r条边围成的面) 于是 n-m+f=(r+1)2-(2r2+2r)+(r2+1) =(r2+2r+1)-(2r2+2r)+(r2+1) =2 故此Euler公式对此类图正确。 34.运用kuratowski定理证明下图是非平面图。 [证](1)给图G中结点打上标号,并用黑点标记要删去的边。 (2)去掉图G中打黑点的边,得图G的子图。 (3)对图G的子图进行变形。 (4)用kuratowski技术对图G的子图(变形后的)进行处理: 从而,在kwratowski技术下,(3)与K3·3同构,因而根据Kwratowski定理,此图G是非平面图。 离散数学习题解答 习题七 1.证明树是只有一个区域的平面图。 [证] 证法一 由于树无圈套在,因此根据kuratowski定理,可知树是平面图(否则,必须有圈,矛盾),因此可用Euler定理。对于树,m=n-1,故此由n-m+r=2,得树的区域数 r=2+m-n=2+(n-1)-n=1 证法二 用归纳法,施归纳于树的结点个数n。 当n=1时,只显然为平面图只有一个区域,题意为真 当n=k时,假设题意为线时,我们来证题意为真。 事实上,由于T是树,故T中至少有一个悬挂点,在T中删去此结点,得到一个k个结点的边通图T′,显然T′中无圈。于T′是一个具有k个结点的树,于是根据归纳假设,T′是只有一个区域的平面图。这时将删去的结点重新扦入T′中以得到T,由于悬挂点不改变图的平面性和区域数,因此T仍是中仍一个区域的平面图。 2.请画出具有六个结点的各种不同构的自由树。 [解] 共有六种,图示如下: (1) (2) (3) (4) (5) (6) 3.证明任意一棵树中至少有两片叶子。 [证] 当结点数n≥2时,任意一棵树必至少有两片叶子。否则,假设某树中最多只有一片叶了,那么其中n-1结点都不是叶子,故此这n-1个点的度都大于等于2,于是根据各结点的度的总和是边数的二倍可知 2n-2=2(n-1)=2m=≥2(n-1)+1=2n-1 ,矛盾。 4.在一棵树中,度数为2的结点有n2个;度数为了的结点有n3个;…;度数为k的结点有nk个;问它有几个度数为1的结点? [解] 设这棵树的项点数为n,边数为m,度为1的结点数为x。从而 n=x+n2+n3+…+nk =2m=2(n-1)=2n-2 但是 =1·x+2·n2+3·n3+…k·nk =2(x+n2+n3+…+nk)-2 于是解得 x=n3+2n4…+(k-2)nk+2 因此,度为1的结点共有n3+2n4+…+(k-2)nk+2个。 5.设G=(V,E)是连通的(n,m)无向图,证明m≥n-1。 [证] 既然G是一个连通的无向图,那么G 一定包含一个生成树。 又因 V =n,于是生成树的边数为n-1,从而 m= E ≥n-1 6.若G=(V,E)是(n,m)无向图,且n≤m,则G中必有圈。 [证] 用反证法。假设G中无圈,则 (a)当G连通时,有G是一棵树,从而m=n-1<n,与已知n≤m矛盾。 (b)当G不连通时,有G是森林,不妨设G有k个树,每个树的结点数分别为n1,n2,…nk,边数分别是n1-1,n2-1,…,nk-1。显然ni=n 因此,G的总数 m=(ni-1)= ni-1=n-k<n (k>1) 与已知n≤m矛盾。 7.求出左上图中的全部生成树。 [解] 此图共有16个生成树,(详见王朝瑞《图论》P259 Cayley(1889)定理:n阶完全图的生成树有nn-2个,故4阶完全图的生成树有42=16个) 8.求出左下图的最小生成树。 [解] 利用kruskal 算法,先将各边按大小排队如图(a)(树相等的边顺序任意)。然 后逐边检查,若ei和T不构成圈,就将ei插入T中。最后得到最小生成树T如图(b)所示。 T:={e1,e2,e3,e4,e5,e6,e9} W(T)=W(e1)+W(e2)+W(e3)+W(e4)+W(e5)+W(e6)+W(e9) =1+1+1+2+2+2+5 =14 9.由简单有向图的邻接矩阵如何判断它是否为有根树?若是有根树,又如何确定树根及树叶? [答](a)邻接矩阵,只有当一列其元素全为零且其余n-1列均只有一个元素为1,其它元素都为零时,该简单有向图是有根树。 (b)若是有根树,其邻接矩阵中元素全为零的一列所对庆的项点是树根;而元素全为零的行所对应的顶点都是树叶。 10.没G为有根树,证明:当把有向边视为无向边时,G为自由树叶。 [证](1)注意到有根树中只有一个结点进数为零(即根结点),其它n-1个结点的进数均为1。根据第六章§2定理1(2),有向图中诸结点的进数之和等于边数,可知有根树的边数为n-1;(2)又因为有根树从根结点可达任一结点(第七章§2定义1(3)),于是当把有向边视为无向边时,有根树应为弱连通图。综合(1)、(2)根据第七章§1定理1的3),可知,当我们把有向边视为无向边时,有根树G是自由树。 11.设G=(V,E)为有向图,若G在弱连通意义下无圈,证明G中必有入度为0的结点,且G中必有出度为0的结点。 [证] 用反证法。假设有向图G中无进度为0的结点,于是G中任一结点,之进度都大于等于1,从而G中诸结点的进度之和大于等于n。根据第六章§2定义1(2),有向图中诸结点的进数之和等于边数,可知有向图G的边数m大于等于n。又当忽视有向边的方向时,已知G是一个连通图,从而G中有圈(否则,G连通且无圈,根据树的定义,G为树,根据第七章§1的定理1.3)或4)知m=n-1,这与m≥n矛盾),这与G在弱连通意义下无圈矛盾。 因此可见G中必有进度为0的结点。 同理可证G中必有出度为0的结点。 12.设T为二叉树,证明: 1)T的第l层上的结点总数不超过2l(其中l≥0); 2)若T的高度为h,则T至多只有2h+1-1个结点。 [证] 1)用归纳法。[基始步],当l=0时,由二叉树只有一个结点,即根结点,故结论为真。[归纳假设],当l=k时,结论为真。即第k层上的结点总数不超过2k。[归纳步],当l= k+1时,由于二叉树中,每个结点至多有2个儿子,于是第k+1层结点总数不超过 第k层结占总数·2 ≤2k·2(归纳假设) =2k+1 即当l=k+1时,结论也真。故对于任何自然数l≥0,1)是线)由于每一层(第l层)结点总数不超过2l,于是二叉树T的结点部数不超过 2°+2′+…+2h= 因此2)得证。 13.将下图表示成以R为根的自顶向下的有根树,然后再将有根树化为二叉树。 [解] 转化后的自顶向下的有根树如图(a)所示: 相关的二叉树如图(b)所示: 14.对于表达式 (35xyz2+6w/x)—x3/(yw) 用中序画成二叉树。 [解] 要把所给表达式表示成二对树,首先要变换成: (35*x*y* (z* z)+(6w)/x)—(x*x*x)/(y*w) 再由此式画出二叉树如图(a) 因此,其前序波兰表达式(前序历遍): —+***35xy*zz/*6wx/*xxx*yw 其后序波兰表达式(后序历遍): 35x*y*zz**6w*x/+xx*x*yw*/— (a) 1 图 v1′ v2′ v3′ v4′ v5′ v6′ v6 v1 图G′ 图G v5 v4 v3 v2 v1 v2 v3 v4 v88 v78 v58 v68 v4( v1( v2( v7( v6( v8( v5( v3( v1 v2 v3 v4 v58 v1( v2( v3( v4( v58 G G′ G G′ G G b e d c a a e b c d A D E F C B G1 G2 G3 G4 G5 G6 G6 G5 G4 G2 pdc,r pdcr,φ dc,pr c,pdr pcr,d dpc,r pdr,c pr,dc φ,pdcr v5 v1 v10 v9 v8 v7 v4 v3 v2 v6 v1 v4 v3 v2 u v 3 4 5 1 2 6 8 5 3 4 2 2 9 7 3 1 10 5 2 10 10 4 2 2 1 5 8 3 6 6 6 3 8 2 5 v u 10 5 2 ⑩ 10 4 2 ∞ 1 ∞ 3 ⑥ 6 6 3 8 ∞ 0 ① ∞ 2 8 5 2 6 10 ③ 1 u ∞ v 5 2 (a) 10 5 2 ⑩ 10 4 2 ∞ 1 ∞ 3 ⑥ 6 6 3 8 ∞ 0 11 2 8 5 2 6 10 ③ 1 u ∞ v 5 2 (b) 10 5 2 ⑩ 10 4 2 ∞ 1 3 6 6 3 8 2 8 5 2 6 10 1 u ∞ v 5 2 (c) 10 5 2 ⑩ 10 4 2 ∞ 1 ⑧ 3 ⑤ 6 6 3 8 ∞ 2 8 5 2 6 10 ③ 1 u ∞ v 5 2 (d) 10 5 2 ⑩ 10 4 2 1 ⑧ 3 ⑤ 6 6 3 8 2 8 5 2 6 10 ③ 1 u v 5 2 (e) 10 5 2 10 4 2 1 3 6 6 3 8 2 8 5 2 6 10 1 u v 5 2 (f) 10 5 2 10 4 2 1 3 6 6 3 8 2 8 5 2 6 10 1 u v 5 2 (g) 10 5 2 10 4 2 1 3 6 6 3 8 2 8 5 2 6 10 1 u v 5 2 (h) 从u到v的最短路径共有三条: P1=(u,u1,u3,u4,v) P2=(u,u1,u2,u3,u5,u6,v) P3=(u,u12,u2,u3,u6,v) P4=(u,u1,u2,u3,u5,u8,u6,v) P5=(u,u7,u8,u6,v) 从u到v的最短路长为: W(P1)=W(P2)=W(P3)=15。 10 5 2 10 4 2 1 3 6 6 3 8 2 8 5 2 6 10 1 u v 5 2 (j) u7 u8 u5 u6 u2 u3 u4 u1 v 3 4 5 2 6 8 5 3 4 u (a) 7 3 1 8 9 2 2 2 1 v 3 4 5 2 6 8 5 3 4 u (b) 7 3 1 8 9 2 2 2 1 v 3 4 5 2 6 8 5 3 4 u (d) 7 3 1 8 9 2 2 v 3 4 5 2 6 8 5 3 4 u (c) 7 3 1 8 9 2 2 2 v 3 4 5 2 6 8 5 3 4 u (e) 7 3 1 8 9 2 2 2 1 v 3 4 5 2 6 8 5 3 4 u (f) 7 3 1 8 9 2 2 2 1 v 3 4 5 2 6 8 5 3 4 u (g) 7 3 1 8 9 2 2 2 1 b c a 图1 000 001 100 110 011 111 101 010 a4 a3 a1 a2 a5 a6 a7 a8 a16 a15 a11 a9 a10 a12 a13 a14 弧 标号 a1 0000 a2 0001 a3 0011 a4 0111 a5 1111 a6 1110 a7 1100 a8 1001 a9 0010 a10 0101 a11 1011 a12 0110 a13 1101 a14 1010 a15 0100 a16 1000 图4 图3 图2 图1 图2 图1 B A A A A A A B B B B B B B B B 图5 G E C A B D F 德语 英语 俄语 英语 英语 图G 其余n-2个 顶点 u v w v1 v2 v3 v4 u5 u3 u4 u2 u1 入口 u 入口 u u 1 2 5 4 7 3 图G 图G 6 图G的子图 1 2 5 4 7 3 6 6 5 2 1 3 7 4 图G的子图 1 2 5 3 7 4 1 (1) (2) (3) (4) (5) (6) (7) (8) (8) (9) (11) (10) (12) (13) (14) (15) (16) 1 2 3 7 3 5 6 5 9 11 1 6 2 1 e2 e6 e8 e13 e7 e10 e12 e9 e14 e15 e11 e5 e3 e4 e1 (a) (b) e2(1) e9(5) e3(1) e4(2) e1(1) e6(2) e5(2) A E B F C D J h G I R A B R F E H G I J C D (a) R B A I D C F J G H v v v v v

  ·《魔兽世界》德拉诺之王6.0要塞:旅店追随者副加属性的选择思路及属性攻略教程.doc

  ·酵母甘油醛―3―磷酸脱氢酶(GPD)基因及其启动子的分离和鉴定.pdf

  ·聚铜络合物[Cu(L)μ-1,3-N3]n(ClO4)n的密度泛函计算及磁性研究.pdf

  ·抗菌肽ABP3基因的克隆及其在Pichiapastoris中的表达.pdf

http://mojdzwonek.com/tuilijiedian/149.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有