これは、グラフのエッジ接続とその最小カットの間の接続を尋ねる質問です。
ご存知のように、無向グラフのエッジ接続性は、kグラフを切断するために削除する必要があるエッジの最小数です。たとえば、ツリーのエッジ接続性は 1 で、サイクルのエッジ接続性は 2 です。
私の考えでは、最小限のカットの容量はエッジの接続性と等しくなければなりません。カットとは、グラフを 2 つの切断部分に分離することだからです。エッジの接続性がわかっている場合、グラフを 2 つの切断部分にするには、k少なくともエッジを削除または切断する必要があることを意味します。kしたがって、最小カットの容量は になりますk。
この質問についての結論や証拠が見つからなかったので、ここで質問します。私の考えが正しいかどうかを確認したり、他のアイデアを教えてもらえますか?