给出一个没有偶圈的简单无向图，求两个顶点间路径的数目。

老实说，这个题目其实不容易，在正式竞赛中肯定不属于送分题。题目的难点在于发现“没有偶圈”这个条件反映的图的特殊性质。

如提示中所说，考虑图的双连通分量。首先解释一下什么是双连通分量。无向图中某个顶点如果被删除之后，连通分量的数目增加，那么这个顶点就叫做割点。无向图中不包含割点的极大子图就是双连通分量。

双连通分量中任意两顶点共圈。从这个性质出发，可以证明：没有偶圈的简单无向图的所有双连通分量只能是2阶完全图或奇圈，收缩所有双连通分量之后得到的图是树。这两个性质意味着，图中两个顶点间的路径经过的双连通分量的序列是相同的。由此得到一下算法：

1.求出图的所有双连通分量；
2.确定从顶点u到顶点v的一条路径；
3.确定路径经过的双连通分量的序列；
4.确定序列中是奇圈的双连通分量的数目，记为k，则路径数为2^k。

在分析上述算法的复杂度之间，先补充一下图的另一个性质。因为图中没有偶圈，所以图中不包含同胚于5阶完全图或3,3完全二部图的子图，根据Kuratowski定理，这个图是平面图，由此可得m = O(n)。

现在来分析算法的复杂度。第1步可以利用J. Hopcroft提出的线性时间算法在O(n + m) = O(n)时间内完成。第2步可以用宽度优先搜索在O(n)时间内实现。第3步可以直接在O(n)时间内实现。第4步是整个算法的瓶颈。 它需要计算一个O(2^(n/2))的数值。使用一般的算法实现时间复杂度将为O(n^2)，如果使用快速正交变换实现时间复杂度将为O(nlogn)。综合以上四个结果，算法的时间复杂度是O(nlogn)。算法的空间复杂度为O(n)。

  最后修改于2007-4-15 1:26:00

楼主真是辛苦了啊，刚过完零点就看到你的新贴了！

支持你的工作

 

5555~~~~
收缩所有双连通分量之后得到的图是树。这两个性质意味着，图中两个顶点间的路径经过的双连通分量的序列是相同的。

这里就没想到啊

 

如提示中所说，考虑图的双连通分量。首先解释一下什么是双连通分量。无向图中某个顶点如果被删除之后，连通分量的数目增加，那么这个顶点就叫做割点。无向图中不包含割点的极大子图就是双连通分量。

图学的太少，只有用笨方法了

 

离散数学当时没有讲图论
后来也没有看
所以没参加

 

我是这几天补的图的知识，之前都不知道什么是无向图。。。。
写得好狼狈啊~~~~　　本来都不想交卷的～～

 

楼主可不可以给出你写的代码??我想看一下你写的??

 

第4步是整个算法的瓶颈。 它需要计算一个O(2^(n/2))的数值。使用一般的算法实现时间复杂度将为O(n^2)，如果使用快速正交变换实现时间复杂度将为O(nlogn)。

收缩后不是树么？还用什么正交变换乱七八糟的啊？我记得这题是frkstyc出的题，难道楼主就是frkstyc？