強く接続されたコンポーネント

Question

グラフGの総V個の頂点とEエッジの総数が与えられた場合、グラフの強く接続されたコンポーネント内の最小の頂点数&エッジで最も強く接続されたコンポーネントをどのように計算できますか？

例： 5つの頂点と7つのエッジを持つグラフの場合、接続コンポーネントの最小サイズは3です。
このグラフは、より多くの接続コンポーネントがあり、最小値が3になるようにモデル化できます。

私が直面している問題は、私には与えられていません。エッジの総数のみが与えられる。私は深さの最初の検索を使用してTarjan'sアルゴリズムを使用したいと思ったが、私はエッジ情報が必要です。

頂点の数が最小で、頂点の総数とエッジの総数だけで、強く連結されたコンポーネントのサイズを見つけることは可能ですか？

Answer 1

私が考えることのできる最も単純な方法は、動作するものが見つかるまで、Complete Graphsサイズ1、次に2などのコンポーネントを形成するためにエッジを利用しようと考えることです。

サイズnの完全グラフは、（n - n）/ 2エッジを持ちます。だから、あなたはその後、グラフの辺の数で使用されるエッジの数を比較することができ

numFullComponents := V/n //integer division 
numEdgesUsed := numFullComponents * n * (n-1)/2 //This is edges from full components 
    + (V%n) * (V%n - 1)/2 //a complete graph on the remainder nodes 

ようになりますサイズnの成分に分割します。少なくともEエッジを使用する最小のnが解です。