隣接行列

隣接行列（りんせつぎょうれつ）

グラフ理論および計算機科学の分野で、有限個の頂点を持つグラフの構造を行列で表現する方法の一つです。これは、グラフ中の頂点間に辺が存在するかどうかを示す正方行列として定義されます。

定義

頂点の集合$V$を持つ単純グラフを考えます。隣接行列$A$は、そのサイズが頂点の数$|V|$に等しい$|V| \times |V|$の正方行列です。行列の要素$A_{i,j}$は、頂点$i$から頂点$j$への辺が存在する場合に1、存在しない場合に0と定義されます。単純グラフでは自己ループ（頂点からそれ自身への辺）が許されないため、対角要素$A_{i,i}$は全て0になります。

単純グラフ以外のグラフ、例えば複数の辺が頂点間に存在したり（多重グラフ）、自己ループを持つグラフの場合も隣接行列で表現できます。この場合、行列要素$A_{i,j}$は頂点$i$と頂点$j$の間の辺の数を格納します。自己ループについては、辺を1つと数えるか、頂点-辺の接続を2つと数えるかなど、慣習によって扱いが異なりますが、一般的には1つのループに対して対角成分に2を加える場合が多いです。

この隣接行列は、グラフに関する別の表現である接続行列（頂点と辺の接続関係を示す）や次数行列（各頂点の次数を示す対角行列）とは区別される必要があります。

2部グラフにおける表現

グラフが2部グラフ、すなわち頂点集合が互いに素な二つの部分集合$U$と$V$に分割され、辺が常に$U$の頂点と$V$の頂点の間にのみ存在する構造を持つ場合、隣接行列は特別なブロック行列の形を取ります。$U$の頂点数を$r$、$V$の頂点数を$s$とすると、隣接行列$A$は以下のように表現できます。

$$
A = \begin{pmatrix} 0_{r,r} & B \\ B^T & 0_{s,s} \end{pmatrix}
$$

ここで、$0_{r,r}$と$0_{s,s}$はそれぞれ$r \times r$と$s \times s$のゼロ行列、$B$は$r \times s$の行列です。この行列$B$はbiadjacency matrixと呼ばれ、2部グラフの構造を表現する上で、隣接行列$A$よりも簡潔な場合があります。$B$の要素$B_{i,j}$は、$U$の$i$番目の頂点と$V$の$j$番目の頂点の間の辺の数（または重み）を示します。

バリエーション

隣接行列にはいくつかの派生形が存在します。例えば、単純グラフの$(a, b, c)$-「隣接行列」は、辺があれば$a$、辺がなければ$b$、対角要素を$c$とする行列です。セイデル隣接行列は、辺がある場合は-1、ない場合は1、対角要素は0とする特殊な形式で、特定のグラフ構造の研究に用いられます。

また、距離行列は、頂点間の辺の有無ではなく、最短経路の長さ（距離）を行列要素とするもので、隣接行列の概念を拡張したものと言えます。

性質

スペクトル

無向単純グラフの隣接行列は常に実対称行列であり、その固有値は全て実数で、直交する固有ベクトルを持ちます。これらの固有値の集合はグラフの「スペクトル」と呼ばれ、グラフの連結性や2部性など、構造的な性質と深く関連しています。例えば、グラフが連結であることと、最大の固有値の多重度が1であることは同値です。また、グラフが2部グラフであることは、固有値$ \lambda$に対して必ず$-\lambda$も固有値として存在することと同値です。

同型写像

二つのグラフが同型であるかどうかは、それらの隣接行列が置換行列$P$を用いて$PA_1 P^{-1} = A_2$という関係を満たすかどうかによって判断できます。これは、同型なグラフの隣接行列は相似であることを意味し、したがって同じ固有値、行列式、トレースなどの行列不変量を持ちます。ただし、これらの不変量が一致してもグラフが同型でない「等スペクトルグラフ」も存在します。

行列の冪

グラフの隣接行列$A$を$n$回掛け合わせた行列$A^n$の要素$(A^n)_{i,j}$は、頂点$i$から頂点$j$への長さ$n$の（有向または無向）パスの数を示します。この性質は、グラフ内のパスの存在や数を数える際に非常に有用です。例えば、無向グラフにおける長さ3の閉路（三角形）の数は、$A^3$のトレース（対角要素の和）を6で割ることで得られます。

データ構造としての利用

コンピュータプログラムにおいてグラフを扱う際、隣接行列は一般的なデータ構造の一つです。頂点数$|V|$のグラフに対し、$|V| \times |V|$の二次元配列として表現されます。各要素は辺の有無を示す1ビットあれば十分なため、ビット列として効率的に格納することも可能です。

しかし、頂点数に対して辺が非常に少ない「疎なグラフ」の場合、行列のほとんどの要素が0となり、多くのメモリが無駄になります。このような場合は、辺が存在する頂点のペアだけをリスト形式で保持する「隣接リスト」の方がメモリ効率が良いことが一般的です。

操作の効率性も異なります。特定の2つの頂点間に辺があるかどうかの判定は、隣接行列では行列要素を直接参照するため非常に速い一方、隣接リストでは隣接リストを走査する必要があり、遅くなることがあります。逆に、ある頂点に隣接する全ての頂点を列挙する操作は、隣接リストではリストを読み進めるだけで済むのに対し、隣接行列では対応する行全体を走査する必要があるため、隣接リストの方が効率的な場合があります。

隣接行列は、密なグラフや辺の有無判定を頻繁に行うアルゴリズムに適しています。また、行列演算が可能なため、スペクトルグラフ理論のような数学的な解析を行う際にも自然な表現形式となります。

もう一度検索