在一個網絡中，節點間的鏈路越多越好？

Question

從理論上講，是完整的圖表（最好的）？因爲有每個節點的鏈接？任何參考將不勝感激。

Answer 1

這真的取決於你所說的「最好的」。如果您正在討論流量最大化，那麼您可能會通過具有適當權重的完整圖形來接近流量的理論上限。但是，如果你真的在某個真實的系統中談論「最好的」，那麼完整的圖形不太可能成爲大多數情況下構建的網絡，僅僅是因爲這樣做造成的浪費。

看起來你的問題似乎與Max-flow min-cut theorem有關。請注意，完整圖中的最小切割尺寸至少爲|V|-1，因爲每個頂點至少具有多條邊。