graph - ネットワークでは、ノード間のリンクが多いほど良いですか?

Question

理論的には、完全なグラフが望ましい (最良の) ものですか? 各ノードへのリンクがあるからですか？任意の参照をいただければ幸いです。

Answer 1

それは、「最高」が何を意味するかによって異なります。フローの最大化について話している場合は、適切な重みを持つ完全なグラフを用意することで、フローの理論上の上限に近づく可能性があります。ただし、実際のシステムで「最良」について本当に話している場合、完全なグラフは、無駄な費用がかかるため、ほとんどの場合に構築するネットワークになる可能性はほとんどありません。

あなたの質問はMax-flow min-cut theorem に関連しているようです。|V|-1すべての頂点には少なくともその数のエッジがあるため、完全なグラフの最小カットは常に少なくとも のサイズになることに注意してください。