首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

请问一个图论算法

2012-02-07 
请教一个图论算法在一个无向图中,给出两个点u和v,并且u和v间没有边,求出这两个点间最多的不相交的简单路径

请教一个图论算法
在一个无向图中,给出两个点u和v,并且u和v间没有边,求出这两个点间最多的不相交的简单路径数目?

[解决办法]
网络流吧


[解决办法]
如果这个题很好的解决了,那么
今年google最后一道题目就简单了

请问 u,v之间是否存在一条经过K-1个节点的路径(可以重复)。

[解决办法]
如果是

5----6
  /    /|
 /    / |
1----2  |
|    |  8
|    | /
|    |/
3----4 

在3-6之间有几个不相交的简单路径数?


[解决办法]
一个相似的问题:
给出一组顶点对(ui,vi),如何尽量的把它们连接起来(ui连接vi),并且通路不相交

更实际的问题:
ui,vi是平面上的点,如何用直线段把它们在这个平面上连接起来,通路不相交,并且线段具有宽度

热点排行