算法课后答案

《算法课后答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、4-10识别下图的关节点，画出他们的双连通分图。图1：03124760深度优先树为：01324756(0,0)(1,1)(2,2)(3,3)(4,4)(5,5)(6,5)(7,5)图1中的关节点有：1,3,7①由于结点0是根且在深度优先树中只有一个孩子，所以结点0不是关节点。②由于low[3]=2,d[1]=1,low[3]>=d[1],3是1的孩子，所以结点1是关节点。③由于low[2]=2,d[3]=1,low[2]>=d[3],2是3的孩子，所以结点3是关节点。①由于low[5]=5,d[7]=5,low[5]>

2、=d[7],5是7的孩子，所以结点7是关节点。图1中有三个关节点，故图1不是双连通图。双连通分图：0311323437756图2：01672345深度优先树：01243576(0,0)(1,0)(2,0)(3,0)(4,0)(5,0)(6,0)(7,0)图2中无关节点，在该深度遍历优先树中：①由于结点0是根且在深度优先树中只有一个孩子，所以结点0不是关节点。②由于low[2]=0,d[1]=1,low[2]

3、,4是2唯一一个孩子，所以结点2不是关节点。④由于low[3]=0,d[4]=3,low[3]

4、因此图2是双连通图。它的双连通分图即为它自己。016723454-11证明一个无向连通图G的任何一条边都不可能在两个不同的双连通分图中。证明：假设一个无向连通图G中的有一条边l在两个不同的双连通分图中。但是一条边有两个顶点，若边l在G的两个不同的双连通分图中，则相当于边l的两个顶点a,b同时处在两个不同的双连通分图中，那么这两个双连通分图实际上可以合起来组成一个更大的双连通分图，这就与双连通分量是无向连通图G的极大双连通子图矛盾。所以假设不成立，命题成立。4-12设图Gi=(Vi，Ei),1<=i<=k是无向连通图G的

5、双连通分图，证明：（1）若i≠j,则Vi∩Vj至多包含一个结点；（2）结点V是G的关节点当且仅当对于某i≠j,{V}=Vi∩Vj。证明：（1）假设Vi∩Vj包含两个或以上结点，则有Gi∩Gj至少包含一条边，即有一条边既存在于双连通分图Gi又存在于双连通分图Gj，而由题4-11结论知，一个无向连通图G中的任何一条边都不可能在两个不同的双连通分图中，与假设矛盾。所以假设不成立，原命题成立。（2）如果关节点存在于一个无向连通图G中，那么这个图就不是双连通图。因而关节点存在于无向连通图的至少两个双连通分量中。若结点v是无向连通

6、图G的关节点则有某i≠j，{v}=Vi∩Vj，即该关节点是两个双连通分量的唯一公共结点；若有某i≠j，{v}=Vi∩Vj，即无向连通图G中两个不同的双连通分量有且仅有一个公共结点，则该结点v一定是G的关节点。综上知：结点V是G的关节点当且仅当对于某i≠j,{V}=Vi∩Vj。