战斗在法国-华人娱乐互动门户 » 学校/专业中心 » 自然学科类 » 请教algorithme中最小流的个数与节点的关系

angel7512 发表于 2007-11-24 10:40

请教algorithme中最小流的个数与节点的关系

在有向图中le nombre de coupes minimals 与节点个数的关系

princehahaha 发表于 2007-11-24 13:47

我不觉得这两个有直接的关系,流量主要看arc，想想如果有好多节点但arc上的流量都一样怎么办？

angel7512 发表于 2007-11-24 19:13

可能我没有表达清楚题目是这样的cherche la coupe minimale  dans un graphe orienté
1.construire une famille de graphes telle que le nombre de S-t coupes croît de manière exponentielle avec N le nombre de sommets
2.construire une famille de graphes telle que le nombre de coupes minimales croît de manière exponentielle avec N le nombre de sommets
我想了半天是不是这样
节点数  2   le nombre de coupe     1    le nombre de coupes minimal  1
节点数 3   le nombre de coupe       3    le nombre de coupes minimal  2
节点数 4  le nombre de coupe       9    le nombre de coupes minimal  4
节点数 5  le nombre de coupe       21    le nombre de coupes minimal  6

[align=right][[i] 本帖最后由 angel7512 于 2007-11-25 22:43 编辑 [/i]][/align]

princehahaha 发表于 2007-11-25 16:37

这个应该是让你写arc上的流量的，比如流量这个样那么minimum cut的个数就成指数级增长

angel7512 发表于 2007-11-25 22:44

谢谢楼上的回答但是能不能在详细一些呢

查看完整版本: 请教algorithme中最小流的个数与节点的关系