请教一个图论算法
在一个无向图中,给出两个点u和v,并且u和v间没有边,求出这两个点间最多的不相交的简单路径数目?
[解决办法]
网络流吧
[解决办法]
如果这个题很好的解决了,那么
今年google最后一道题目就简单了
请问 u,v之间是否存在一条经过K-1个节点的路径(可以重复)。
[解决办法]
如果是
5----6
/ /|
/ / |
1----2 |
| | 8
| | /
| |/
3----4
在3-6之间有几个不相交的简单路径数?
[解决办法]
一个相似的问题:
给出一组顶点对(ui,vi),如何尽量的把它们连接起来(ui连接vi),并且通路不相交
更实际的问题:
ui,vi是平面上的点,如何用直线段把它们在这个平面上连接起来,通路不相交,并且线段具有宽度