应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 专业学科区 » 信息科学 » 程序算法 » 图论算法求助！
51/1返回列表
查看: 1848  |  回复: 8
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

wgh0

木虫 (著名写手)

[求助] 图论算法求助！

图G=(V, E)，V为结点集合，E为边集合，已知结点v与结点u1，u2，u3。问：是否存在v与u1，v与u2，v与u3之间的三条不相交路径？不相交路径的意思是三条路径不存在共享的边。

谢谢！
回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
循序渐进！
1楼 2013-07-09 22:07:50
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

wgh0

木虫 (著名写手)
送红花一朵
引用回帖:
5楼: Originally posted by dameng at 2013-07-14 00:44:21
详见 “多路径优化问题的研究进展 高宏 张可佳”，该综述对你的问题会有很大帮助，

谢谢，我已经看到了你说的综述，我研究研究！
赞一下 回复此楼
循序渐进！
7楼2013-07-14 16:46:52
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 9 个回答

bych3384

木虫 (正式写手)

【答案】应助回帖

★ ★ ★ ★
感谢参与，应助指数 +1
wgh0: 金币+4, ★★★很有帮助 2013-07-12 09:27:39
何谓是否存在？要证明么？取决于图的结构。要找出来么？可以先找一条路径，然后删除该路径上的所有边，再找第二条，删除路径上所有边，再找第三条，这样有可能找不到，但是一种启发式算法，也有可能找到，第二种算法是构造一个整数规划模型，用解整数规划的方法去求解。
赞一下(1人) 回复此楼
2楼2013-07-11 10:29:10
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

wgh0

木虫 (著名写手)
引用回帖:
2楼: Originally posted by bych3384 at 2013-07-11 10:29:10
何谓是否存在？要证明么？取决于图的结构。要找出来么？可以先找一条路径，然后删除该路径上的所有边，再找第二条，删除路径上所有边，再找第三条，这样有可能找不到，但是一种启发式算法，也有可能找到，第二种算法 ...

存在主要是指能否找到这样的三条路径。这个不需要证明，只要能够给出具体算法，或者算法思想就行，因为我需要编程实现这个问题，我是用matlab。
我也想过先找出第一条，然后删除的方法。但是我有一些疑问，就是这样能够保证在找不到的情况下，确实途中没有这样的三条路径吗？
关于你说的启发式算法与整数规划模型，你能够说的在详细一点吗？
谢谢！
赞一下 回复此楼
循序渐进！
3楼2013-07-12 09:27:26
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

bych3384

木虫 (正式写手)

【答案】应助回帖

★
wgh0: 金币+1, ★★★很有帮助 2013-07-14 16:41:54
所谓启发式，就是那个寻找-删除的方式啦，但一次成功可能会有难度，因为两点之间的路径可能有很多条。但可以将这所有的路径枚举出来，再做组合匹配。比如说：
（1）找出V到u1之间的所有路，记为A
(2)找出V到u2之间的所有路，记为B
(3)找出V到u2之间的所有路，记为C
（可以用DFS或BFS搜索所有路）
（4）在A，B，C中寻找没有公共边的路。
至于整数规划，可以对每条边设置一个0-1变量，如果该边在路上取1，否则取0，具体的目标函数和约束条件需要你去研究啦
赞一下(1人) 回复此楼

» 本帖已获得的红花（最新10朵）

wgh0
4楼2013-07-13 09:22:18
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 9 个回答
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[职场人生] 40+中年人失业后，还能找到好工作吗？ +11 xqy2009 2026-10-13 13/650 2026-10-15 21:32 by bear2007
[有机交流] 用NBS溴化时溶剂除了CCl4外还有什么 +3 18834002860 2026-10-12 6/300 2026-10-15 14:30 by 长沙摩尔信息科�
[基金申请] 申请科研项目纯靠实力能成功吗？ 200+7 David1982 2026-10-13 11/550 2026-10-15 10:30 by zyqchem
[硕博家园] 极限拉扯，如何抉择 +11 Isak0320 2026-10-12 15/750 2026-10-14 21:55 by 猫鱼不是鱼
[有机交流] OpenAI又攻克数学难题了，离AI做有机合成还有多远？ +8 wangyl_123 2026-10-10 13/650 2026-10-14 15:12 by zuesli
[教师之家] 课题组会帮你通过考核么？ +4 好运来～9527 2026-10-10 7/350 2026-10-13 08:41 by xli1984
[公派出国] 售一区SCI文章T0P，我:8O.551.O54,科目全,可十急 +5 qR2AdCWTVtkw 2026-10-09 9/450 2026-10-11 22:34 by XQNyDCa1Tk5n
[找工作] 售SCI一区T0P文章，我:8.O55.1.O.54,科目全,可十急 +5 qR2AdCWTVtkw 2026-10-09 8/400 2026-10-11 22:26 by XQNyDCa1Tk5n
[公派出国] 售SCI一区文章，我:8O5.5.1.O5.4,科目全,可伽急 +5 qR2AdCWTVtkw 2026-10-09 10/500 2026-10-11 22:26 by XQNyDCa1Tk5n
[考博] 售SCI一区T0P文章，我:8.O55.1.O.54,科目全,可十急 +5 qR2AdCWTVtkw 2026-10-09 9/450 2026-10-11 22:15 by XQNyDCa1Tk5n
[考博] 售SCI一区文章，我:8.O.55.1.O.54,科目齐全,可伽急 +3 qR2AdCWTVtkw 2026-10-09 7/350 2026-10-11 22:11 by XQNyDCa1Tk5n
[教师之家] 售SCI文章，我:8O5.5.1.O.54,科目齐全,可+急 (EPI+-1)(金币-50) +5 qR2AdCWTVtkw 2026-10-09 10/500 2026-10-11 22:06 by XQNyDCa1Tk5n
[教师之家] 售SCI一区T0P文章，我:8.O.55.1.O.5.4,科目全,可+急 (EPI+-1)(金币-50) +5 qR2AdCWTVtkw 2026-10-09 10/500 2026-10-11 14:25 by VOMexwnDzOFZ
[教师之家] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 (EPI+-1)(金币-50) +4 qR2AdCWTVtkw 2026-10-09 7/350 2026-10-11 14:05 by VOMexwnDzOFZ
[考研] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 +5 qR2AdCWTVtkw 2026-10-09 8/400 2026-10-11 13:51 by VOMexwnDzOFZ
[硕博家园] 售SCI-T0P文章，我:8O.5.5.1.O.54,科目齐全,可+急 +5 qR2AdCWTVtkw 2026-10-09 8/400 2026-10-11 13:45 by VOMexwnDzOFZ
[找工作] 售SCI一区T0P文章，我:8O.55.1.O.5.4,科目齐全,可+急 +3 qR2AdCWTVtkw 2026-10-09 7/350 2026-10-11 10:54 by VOMexwnDzOFZ
[找工作] 售SCI一区T0P文章，我:8O.55.1.O.5.4,科目齐全,可+急 +4 qR2AdCWTVtkw 2026-10-09 7/350 2026-10-11 10:34 by VOMexwnDzOFZ
[考博] 招收博士生一名 +3 mandolin 2026-10-10 3/150 2026-10-11 10:21 by 不是山谷！
[公派出国] 售SCI一区T0P文章，我:8O.55.1.O.54,科目全,可伽急 +4 qR2AdCWTVtkw 2026-10-09 4/200 2026-10-11 03:14 by M0zrYVSAnxpE
信息提示
关闭
请填处理意见
关闭