2二图与遍历算法习题参考答案

第二章部分习题参考答案1.证明下列结论：1）在一个无向图中，如果每个顶点的度大于等于2，则该该图一定含有圈；2）在一个有向图D中，如果每个顶点的出度都大于等于1，则该图一定含有一个有向圈。1）证明：设无向图最长的迹,10kVVVP每个顶点度大于等于2，故存在与1V相异的点'V与0V相邻，若,'PV则得到比P更长的迹，与P的取法矛盾。因此，PV'，是闭迹，从而存在圈.0'10VVVV证明*：设在无向图G中，有n个顶点，m条边。由题意知，m=(2n)/2=n，而一个含有n个顶点的树有n-1条边。因m=nn-1，故该图一定含有圈。（定义：迹是指边不重复的途径，而顶点不重复的途径称为路。起点和终点重合的途径称为闭途径，起点和终点重合的迹称为闭迹，顶点不重复的闭迹称为圈。）2）证明：设有向图最长的有向迹,10kVVVP每个顶点出度大于等于1，故存在'V为kV的出度连接点，使得'VVk成为一条有向边，若,'PV则得到比P更长的有向迹，与P矛盾，因此必有PV'，从而该图一定含有有向圈。2.设D是至少有三个顶点的连通有向图。如果D中包含有向的Euler环游（即是通过D中每条有向边恰好一次的闭迹），则D中每一顶点的出度和入度相等。反之，如果D中每一顶点的出度与入度都相等，则D一定包含有向的Euler环游。这两个结论是正确的吗？请说明理由。如果G是至少有三个顶点的无向图，则G包含Euler环游的条件是什么？证明：1）若图D中包含有向Euler环游，下证明每个顶点的入度和出度相等。如果该有向图含有Euler环游，那么该环游必经过每个顶点至少一次，每经过一次，必为“进”一次接着“出”一次，从而入度等于出度。从而，对于任意顶点，不管该环游经过该顶点多少次，必有入度等于出度。2）若图D中每个顶点的入度和出度相等，则该图D包含Euler环游。证明如下。对顶点个数进行归纳。当顶点数|v(D)|=2时，因为每个点的入度和出度相等，易得构成有向Euler环游。假设顶点数|v(D)|=k时结论成立，则当顶点数|v(D)|=k+1时，任取v∈v(D).设S={以v为终点的边}，K={以v为始点的边}，因为v的入度和出度相等，故S和K中边数相等。记G=D-v.对G做如下操作:任取S和K中各一条边21ee、，设在D中vve11，22vve，则对G和S做如下操作21vvGG,}{2eSS，重复此步骤直到S为空。这个过程最终得到的G有k个顶点，且每个顶点的度与在G中完全一样。由归纳假设，G中存在有向Euler环游，设为C。在G中从任一点出发沿C的对应边前行，每当遇到上述添加边v1v2时，都用对应的两条边e1，e2代替，这样可以获得有向Euler环游。3）G是至少有三个顶点的无向图，则G包含Euler环游等价于G中无奇度顶点。（即任意顶点的度为偶数）。3．设G是具有n个顶点和m条边的无向图，如果G是连通的，而且满足m=n-1,证明G是树。证明：思路一：只需证明G中无圈。若G中有圈，则删去圈上任一条边G仍连通。而每个连通图边数e=n(顶点数)–1，但删去一条边后G中只有n-2条边，此时不连通，从而矛盾，故G中无圈，所以G为树。思路二：当2n时，112m，两个顶点一条边且连通无环路，显然是树。设当)2,(1kNkkn时，命题成立，则当kn时，因为G连通且无环路，所以至少存在一个顶点1V，他的度数为1，设该顶点所关联的边为).,(211VVe那么去掉顶点1V和1e，便得到了一个有k-1个顶点的连通无向无环路的子图'G，且'G的边数1'mm，顶点数1'nn。由于m=n-1,所以11)1(1''nnmm，由归纳假设知，'G是树。由于G相当于在'G中为2V添加了一个子节点，所以G也是树。由（1），（2）原命题得证。4.假设用一个nn的数组来描述一个有向图的nn邻接矩阵，完成下面工作：1）编写一个函数以确定顶点的出度，函数的复杂性应为);(n：2）编写一个函数以确定图中边的数目，函数的复杂性应为);(2n3）编写一个函数删除边),(ji，并确定代码的复杂性。解答：（1）邻接矩阵表示为nna，待确定的顶点为第m个顶点mvintCountVout(int*a,intn,intm){intout=0;for(inti=0;in;i++)if(a[m-1][i]==1)out++;returnout;}（2）确定图中边的数目的函数如下：intEdgeNumber(int*a,intn){intnum=0;for(inti=0;in;i++)for(intj=0;jn;j++)if(a[i][j]==1)num++;returnnum;}（3）删除边（i,j）的函数如下：voiddeleteEdge(int*a，inti,intj){if(a[i-1][j-1]==0)return;a[i-1][j-1]=0;return;}代码的时间复杂性为Θ(1)5.实现图的D-搜索算法，要求用SPARKS语言写出算法的伪代码，或者用一种计算机高级语言写出程序。解:D搜索算法的基本思想是，用栈代替BFS中的队列，先将起始顶点存入栈中，搜索时，取出栈顶的元素，遍历搜索其相邻接点，若其邻接点还未搜索，则存入栈中并标记，遍历所有邻接点后，取出此时栈顶的元素转入下一轮遍历搜索，直至栈变为空栈。ProcDBFS(v)//从顶点v开始，数组visited标示顶点被访问的顺序；PushS(v,S);//首先访问v,将S初始化为只含有一个元素v的栈count:=count+1;visited[v]:=count;WhileS非空dou:=PullHead(S);count:=count+1;visited[w]:=count;//区别队列先进先出，此先进后出for邻接于u的所有顶点wdoifs[w]=0thenPushS(w,S);//将w存入栈Ss[w]:=1;end{if}end{for}end{while}end{DBFS}注：PushS(w,S)将w存入栈S;PullHead(S)为取出栈最上面的元素，并从栈中删除ProcDBFT(G，m)//m为不连通分支数count:=0;计数器，标示已经被访问的顶点个数foritondos[i]:=0;//数组s用来标示各顶点是否曾被搜索，是则标记为1，否则标记为0；end{for}foritomdo//遍历不连通分支的情况ifs[i]=0thenDBFS(i);end{if}end{for}end{DBFT}6.下面的无向图以邻接链表存储，而且在关于每个顶点的链表中与该顶点相邻的顶点是按照字母顺序排列的。试以此图为例描述讲义中算法DFNL的执行过程。邻接链表A-B-E|0B-A-C|0C-B-D-E|0D-C|0E-A-C-F-G|0F-E-G|0G-E-F|0解：初始化数组DFN:=0，num=1；A为树的根节点,对A计算DFNL(A,null)，DFN(A)：=num=1;L(A)：=num=1;num:=1+1=2。从邻接链表查到A的邻接点B，因为DFN(B)=0,对B计算DFNL(B,A)DFN(B)：=num=2;L(B)：=num=2;num：=2+1=3。查邻接链表得到B的邻接点A，因为DFN(A)=10,但A=A,即是B的父节点，无操作。接着查找邻接链表得到B的邻接点C，因为DFN(C)=0,对C计算DFNL(C,B)DFN(C)：=num=3;L(C)：=num=3;num:=3+1=4。查找C的邻接点B，因为DFN(B)=10,但B=B,即是C的父节点，无操作。接着查找邻接链表得到C的邻接点D，因为DFN(D)=0,对D计算DFNL(D,C)，DFN(D)：=num=4;L(D)：=num=4;num:=4+1=5。查找得D邻接点C，而DFN(C)=3≠0,但C=C，为D的父节点，L(D)保持不变。一个无向图GABEDGCF11234756111554D的邻接链表结束，DFNL(D,C)的计算结束。返回到D的父节点C，查找邻接链表得到C的邻接点E，因为DFN(E)=0,对E计算DFNL(E,C),DFN(E)：=num=5;L(E)：=num=5;num:5+1=6;查找得E邻接点A，因DFN(A)=1≠0，又A≠C，变换L(E)=min(L(E),DFN(A))=1。查找得E邻接点C，因DFN(C)=3≠0，但C=C，无操作。查找得E邻接点F，因DFN(F)=0，对F计算DFNL(F,E)，DFN(F)：=num=6;L(F)：=num=6;num:=6+1=7;查找得F邻接点E，因DFN(E)=5≠0，但E=E，无操作。查找得F邻接点G，因DFN(G)=0，对G计算DFNL(G,F)，DFN(G)：=num=7;L(G)：=num=7;num=7+1=8；查找G邻接点E，因DFN(E)=5≠0，又E≠F，L(G)=min(L(G),DFN(E))=5查找得G邻接点F,因DFN(F)=6≠0，但F=F，无操作。G的邻接链表结束，DFNL(G,F)的计算结束。L(F)：=min(L(F)，L(G))=min(6,5)=5F的邻接链表结束，DFNL(F,E)的计算结束。L(E):=min(L(E),L(F))=min(1,5)=1E邻接链表结束，DFNL(E,C)计算结束。L(C):=min(L(C),L(E))=min(3,1)=1C的邻接链表结束，DFNL(C,B)计算结束。L(B):=min(L(B),L(C))=min(2,1)=1查找B的邻接链表结束，DFNL(B,A)计算结束。L(A):=min(L(A),L(B))=1查找得A的邻接点E，因DFN(E)=0，又E≠null,则L(A)=min(L(A),DFN(E))=1查找A的邻接链表结束，DFNL(A,null)计算结束。最终结果为：深索数DFN，与最低深索数L如下DFN(A)=1，DFN(B)=2，DFN(C)=3，DFN(D)=4，DFN(E)=5，DFN(F)=6，DFN(G)=7L(A)=1;L(B)=1;L(C)=1;L(D)=4;L(E)=1;L(F)=5;L(G)=5.序节点DFNL栈顶—栈底2-连通割点1A1(1,0,0,0,0,0,0)(A,B)2B2(1,2,0,0,0,0,0)(B,C),(A,B)3C3(1,2,3,0,0,0,0)(C,D),(B,C),(A,B)4D4(1,2,3,4,0,0,0)(B,C),(A,B){(C,D)};C5E5(1,1,1,4,1,0,0)(E,F),(E,A),(B,C),(A,B)6F6(1,1,1,4,1,6,0)(F,G),(E,F),(E,A),(B,C),(A,B)7G7(1,1,1,4,1,5,5)(E,A),(B,C),(A,B){(G,E),(F,G),(E,F)}E8(1,1,1,4,1,5,5){(E,A),(B,C),(A,B)}附课本讲义程序2-3-1对图2-3-5的执行过程开始DFNL(A,*)DFN(A):=1;L(A):=1;num:=2;∵DFN(B)=0,∴DFNL(B,A)DFN(B):=2;L(B):=2;num:=3;∵DFN(A)=10,但A=A,∴不做任何事情∵DFN(C)=0,∴DFNL(C,B)DFN(C):=3;L(C):=3;num:=4;∵DFN(B)=20,但B=B,∴不做任何事情∵DFN(D)=0,∴DFNL(D,C)DFN(D):=4;L(D):=4DFN(C);num:=5;弹出（C,D）边∵DFN(C)=30,但C=C,∴不做任何事情∵DFN(E)=0,∴DFNL(E,C)DFN(E):=5;L(E):=5DFN(C);num:=6;弹出（C,E）边∵DFN(C)=30,但C=C,ABBBACBBCBADCBBCBAECBBCBAFCBBFCBAAFCBB∵DFN(F)=0,∴DFNL(F,C)DFN(F):=