图论防御问题，秋季诶

yunxilee · 发表于 2010-12-2 20:41

敌对双方隔岸对峙。共有14座桥连接两岸及岛屿。为阻止对方部队过河，至少应切断几座桥梁？
请问如何用excel求解？谢谢，这是图论哪一个模型。

bl5062 · 发表于 2011-3-29 12:55

excel没上传啊，好像是求最短路径吧，当最短路径为无限大就是切断了。

luyuanhong · 发表于 2011-3-29 14:32

下面引用由yunxilee在 2010/12/02 08:41pm 发表的内容：
敌对双方隔岸对峙。共有14座桥连接两岸及岛屿。为阻止对方部队过河，至少应切断几座桥梁？
请问如何用excel求解？谢谢，这是图论哪一个模型。

看来只要切断 6，7，12 这三座桥就可以了。
这样的问题，与图论中“图的连接性”有关。

雷明85639720 · 发表于 2012-5-1 12:09

我的回答请看我的《回答网友yunxilee》一文。雷明

cong2498 · 发表于 2017-1-12 10:14

厉害了

		自动登录	找回密码
密码			注册

图论 防御问题 ，秋季诶