graph - 在网络中，节点之间的链接越多越好吗？

Question

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

Answer 1

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

您的问题似乎与Max-flow min-cut theorem有关。请注意，完整图中的最小割总是至少|V|-1为 ，因为每个顶点都至少有那么多边。