Algorithm 版 (精华区)

发信人: sino (蚱蜢舟), 信区: Algorithm
标  题: Re: 几道题，请高手解答，给出思路亦可
发信站: 哈工大紫丁香 (2002年01月12日12:42:59 星期六), 站内信件

重（双）连通图和关节点

问题：若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，
则该连通图被称 为重（双）连通图。图的双连通性对于表示通讯或运输的图来说，有着
重要的意义。

若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上
的连通分量，则称此顶 点为关节点。

显然，没有关节点的连通图为双连通图。

关节点的特征：

假设从某个顶点V0出发对连通图进行深度优先搜索遍历，则可得到一棵深度优先生成树
，树上包含图的所有 顶点。
·若生成树的根结点，有两个或两个以上的分支，则此顶点(生成树的根)必为关节点;
·对生成树上的任意一个“顶点”，若其某棵子树的根或子树中的其它“顶点”没有和
其祖先相通的回边，则 该“顶点”必为关节点。

如何判别？

1) 设V0为深度优先遍历的出发点

p = G.vertices[0].firstarc; v = p->adjvex;
DFSArticul(G, v); // 从第v顶点出发深度优先搜索
if (count < G.vexnum) { // 生成树的根有至少两棵子树
printf (0, G.vertices[0].data); // 根是关节点

2) 对生成树上的顶点定义一个函数:

low(v) = Min{visited[v], low[w], visited[k] }
对顶点v，若(在生成树上)存在一个子树根w,
low[w] ≥ visited[v]
则顶点v为关节点

visited[v0] = min = ++count; // count计顶点访问次序
for (p=G.vertices[v0].firstarc; p; p=p->nextarc) {
w = p->adjvex; // w为v0的邻接顶点
if (visited[w] == 0) { // w未曾被访问
DFSArticul(G, w); // 返回前求得low[w]
if (low[w] < min) min = low[w];
if (low[w]>=visited[v0]) printf(v0, G.vertices[v0].data);
} // 输出关节点
else
if (visited[w] < min) min = visited[w];
// w是回边上的顶点
}

【 在 lizhenguo (夸父·追日) 的大作中提到: 】
: 什么叫双连通图啊？
: 【 在 xp ()() 的大作中提到: 】
: : 1。LC-分枝限界算法
: :    使用动态状态空间树和归约成本矩阵方法写出实现货郎担问题的LC分枝限界算法
: :    的有效程序。
: : 2。（基本检索与周游）设G是一个无向连通图，写一个算法以求出将G变成双连通图所需
: : 要增加的最小边数并要求输出这些边，分析你的算法需要的时间和空间。
: : 3。（回朔法）假定有33张牌，如下图排列，规定当一张牌跳过邻近的一张牌到空
: :     格时就把这张邻近的牌拿掉，写一个算法找出一系列跳步，使除了最后留在中
: :     心格的一张牌外，其他的牌全部拿掉。
: :               口口口


--
撷取生活中每一朵清新的浪花,智慧的浪花 ..汇成音乐的海洋.

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: mtlab4.hit.edu.cn]