在一个网络中，节点间的链路越多越好？

Question

从理论上讲，是完整的图表（最好的）？因为有每个节点的链接？任何参考将不胜感激。

Answer 1

这真的取决于你所说的“最好的”。如果您正在讨论流量最大化，那么您可能会通过具有适当权重的完整图形来接近流量的理论上限。但是，如果你真的在某个真实的系统中谈论“最好的”，那么完整的图形不太可能成为大多数情况下构建的网络，仅仅是因为这样做造成的浪费。

看起来你的问题似乎与Max-flow min-cut theorem有关。请注意，完整图中的最小切割尺寸至少为|V|-1，因为每个顶点至少具有多条边。