Mathematics

隣接行列の紹介

グラフと言う言葉の正式な数学的定義は、お互いを特別な方法を使って接続した点またはノードの集合です。例えば、ノードとして種々の産業、接続するものとして直接的な経済的な結び付きを示す経済モデルのようなものです。コンピュータソフトウエア産業は、コンピュータハードウエア産業、言い換えれば、半導体産業等と関連しています。

グラフのこの定義は、行列表現を利用することができます。ノードiとノードjが接続されているなら、方向性をもたないグラフの隣接行列の(i,j)番目と(j,i)番目の要素は1で、接続されていなければ0になります。例えば、ダイアモンド型のグラフを表す近接行列は、つぎのようになります。

多くのグラフは、1つのノードに対して比較的結合数が少ないので、ほとんどの隣接行列はスパースになります。非ゼロ要素の実際の位置は、どのようにノードに番号を付けるかに依ります。番号の付け方を変更すると、近接行列の行と列の置換が生じます。これは、スパース行列計算で時間と必要なストレージ共に重要な影響を与えます。

例題:隣接行列とグラフ

隣接行列を使ったグラフ表示