2

単純な質問で申し訳ありませんが、完全に接続されているグラフを特定する方法はありますか? グラフの全体的な接続性がグラフ分析の前提条件であることを示すいくつかの論文を読みました。Matlab のいくつかのグラフ分析ツールボックスを検索して、接続性を決定する関数を探しましたが、これらのツールボックスには少なくとも何も提供されていないようです。これについて何か提案をお願いできますか？どうもありがとう！

4

3 に答える 3

5

次のことができます。

  • G がグラフの隣接行列であると仮定します

  • G と同じサイズの対角行列である D を構築し、N 番目のノードの次数を N 番目の対角要素に入れます

  • 減算によるラプラシアン行列の作成: L = D - G

  • L の固有値を計算します(eig関数 inmatlabが自動的に実行します)

  • ゼロに等しい固有値の数は、グラフ内の連結成分の数です

  • コンポーネントの数が 1 の場合、グラフは完全に接続されています。それ以外の場合は、必要なコンポーネントの数があります。

この方法は、有向グラフと無向グラフの両方で機能します

お役に立てば幸いです

于 2015-03-15T22:06:16.887 に答える
1

私はグラフ理論の専門家ではgraphconncompありませんが、うまくいくようです。

この関数は、グラフ内のすべての連結成分を検出するため、グラフが完全に連結されている場合、S=1 成分が返され、C にはすべてのノードに対して 1 が含まれます。

例えば

[S,C] = graphconncomp(G)
if all(C==ones(size(C)))
  disp "G is fully connected";
end
于 2013-04-01T13:59:37.433 に答える
0

もう 1 つのオプションは、FEX 機能を使用することです。ここisconnectedを参照してください。

これは、グラフが接続されているかどうかを判断し、接続されている場合は出力として 1 を、それ以外の場合は 0 を示します。ただし、無向グラフでのみ機能します。

于 2014-09-15T08:23:52.273 に答える