1 基本概念
隣接行列は、グラフの頂点間の結びつきを数表として整理する表現法である。頂点を行と列に対応させ、要素に辺の有無や本数を置くことで、図形的な構造を行列演算の対象に変換できる。これにより、グラフの性質を代数的に調べたり、計算機上で一貫した形式に扱ったりしやすくなる。
1.1 隣接行列の定義
頂点の集合を順序づけ、その順番に従って行と列を並べた正方行列を隣接行列という。一般には、成分が 0 と 1 の場合には辺の不存在と存在を表し、必要に応じて辺の本数や重みを数値として記録する。
1.2 頂点と行列要素の対応
行番号と列番号は、それぞれ特定の頂点を示す。行 i、列 j の成分は、頂点 i から頂点 j への関係を表し、無向グラフでは両者の結びつき、有向グラフでは向きをもつ接続を記述する。頂点の並べ方を変えると行列の配置も変わるが、表すグラフそのものは同じである。
1.3 無向グラフにおける性質
無向グラフでは、辺に向きがないため、隣接行列は左右対称の形をとる。したがって、ある頂点対の接続情報は行と列の入れ替えに対して不変である。
1.3.1 対称性
無向グラフの隣接行列では、行 i 列 j の値と行 j 列 i の値が一致する。これは、頂点 i と頂点 j の関係が双方向に同じ意味をもつためであり、行列全体が対称行列になることを意味する。
1.3.2 対角成分
対角成分は、各頂点から自分自身への接続を表す位置である。単純な無向グラフでは通常 0 が入るが、自己ループを許す場合には 1 やそれ以上の値を置くことがある。対角の値は、そのグラフが自己ループを含むかどうかを示す手がかりになる。
1.4 有向グラフにおける性質
有向グラフでは、辺が始点と終点をもつため、隣接行列は一般に対称にならない。行と列の役割の違いが、そのまま辺の向きに対応する。
1.4.1 入次数と出次数との関係
有向グラフでは、ある頂点の行に現れる値の合計が出次数、列に現れる値の合計が入次数に対応する。つまり、行方向にたどると外向きの辺を数えられ、列方向に注目すると流入する辺の数を把握できる。
1.4.2 非対称な成分
有向グラフの隣接行列では、行 i 列 j と行 j 列 i が異なることが多い。これは、頂点 i から j への辺はあっても、その逆向きが存在しない場合があるためである。こうした非対称性が、向きの情報を行列の内部に保持する。
2 具体的な表現
隣接行列の記法は、グラフの種類に応じて少しずつ変化する。単純グラフ、多重辺を含む場合、重み付きの場合では、成分に入る値の意味が異なるが、いずれも頂点間の対応関係を整理する点は共通している。
2.1 単純グラフの隣接行列
単純グラフでは、同じ頂点対の間に高々 1 本の辺しかなく、自己ループも持たないことが多い。このため、隣接行列は 0 と 1 を中心とする分かりやすい形になり、接続の有無を明確に読み取れる。
2.2 重複辺を含むグラフの表現
多重辺を許すグラフでは、同じ頂点の組に複数の辺が存在しうる。隣接行列では、その本数を成分にそのまま反映することで、単なる有無だけでなく接続の量も表せる。
2.2.1 多重辺の扱い
多重辺がある場合、対応する成分には辺の本数を整数として記録することが多い。これにより、1 組の頂点間にどれだけ多くの接続があるかを、行列の値として直接示せる。
2.2.2 自己ループの扱い
自己ループは、ある頂点から同じ頂点へ戻る辺である。隣接行列では対角成分に反映され、必要に応じてその本数を数える。自己ループを扱うかどうかは、採用するグラフの定義に依存する。
2.3 重み付きグラフの隣接行列
重み付きグラフでは、辺に長さ、費用、容量などの値が付随する。隣接行列は、その重みを成分に入れることで、構造と属性を同時に保持できる。
2.3.1 重みの記録方法
辺が存在する位置には、その重みを数値として書き込む。重みが実数や整数で与えられることもあり、用途に応じて負の値を含める場合もある。こうして、単なる接続情報よりも豊かな表現が可能になる。
2.3.2 存在しない辺の表現
辺がない箇所には、0 を用いることが多い。ただし、重みとして 0 が意味をもつ場面では、存在しないことを別の値や記号で区別することもある。実装上は、欠損と真の 0 を混同しない設計が重要である。
3 数学的性質
隣接行列は、行列論の道具を通じてグラフの振る舞いを調べる基盤になる。和、積、固有値といった概念を用いると、接続の合成や構造の大局的な特徴を解析できる。
3.1 行列の和とグラフの合併
2 つのグラフの隣接行列を加えると、同じ頂点集合上で辺情報を重ね合わせた表現になる。重複があれば値が大きくなり、どの接続が追加されたかを数値的に把握できる。これはグラフの統合や比較に役立つ。
3.2 行列の累乗と経路の数
隣接行列の累乗は、頂点間を何段階かでたどる経路の情報を含む。次数を上げるほど、単発の辺ではなく、連続した移動の組合せを表現する。
3.2.1 二乗の意味
隣接行列の 2 乗は、ある頂点から別の頂点へ 2 本の辺を連続して通る経路の数に関係する。中継点を介した到達可能性を調べる際に有効であり、近接関係の一段深い情報を与える。
3.2.2 高次累乗の解釈
n 乗の成分は、長さ n の歩道や経路の数を示す。これにより、遠い頂点同士がどのように結びつくか、また何通りの経路が存在するかを算出できる。反復的な接続構造の解析にも利用される。
3.3 固有値とスペクトル
隣接行列の固有値の集合は、グラフのスペクトルと呼ばれる。これは、局所的な接続だけでは見えにくい全体構造を要約する量として扱われる。
3.3.1 グラフ構造との関連
固有値の分布は、連結性、規則性、対称性の程度などと関わることがある。特定の値の並びから、グラフの性質を推測したり、類似した構造を比較したりできる。
3.3.2 行列の対角化
対角化が可能な場合、隣接行列は扱いやすい形に変換される。これにより、累乗計算やスペクトル解析が簡潔になり、グラフに関する複雑な問題を整理して考えやすくなる。
4 アルゴリズムと応用
隣接行列は、理論的な記述だけでなく、計算機による処理にも適している。探索、判定、経路計算などで用いられ、実装の単純さと演算のしやすさが利点となる。
4.1 グラフ探索での利用
頂点間の接続を表形式で持つため、ある頂点から到達できる候補を体系的に調べられる。深さ優先探索や幅優先探索のような手続きでは、隣接判定を行列参照で実行できる。
4.2 連結性の判定
グラフが全体としてつながっているかどうかを確認する際にも、隣接行列は役立つ。行列の情報をもとに到達可能な頂点を広げていくことで、成分の分割や連結部分の把握が可能になる。
4.3 最短経路問題への応用
重み付き隣接行列は、経路上の費用や距離を表す入力として利用される。直接の辺だけでなく、複数の辺を組み合わせた経路を比較する際の基礎データとなり、最短経路を求める手法と組み合わせやすい。
4.4 計算量と記憶量
隣接行列は、頂点数に対して固定サイズの二次元配列を要するため、記憶領域が頂点数の二乗に比例する。その代わり、辺の存在確認は定数時間で行いやすく、アクセスの見通しがよい。
4.4.1 隣接リストとの比較
隣接リストは、各頂点に接続先の一覧を持つ方式で、辺が少ないグラフでは空間効率が高い。これに対し、隣接行列は密なグラフで扱いやすく、任意の頂点対について即座に接続判定を行える点が強みである。
4.4.2 疎行列と密行列の違い
辺が少ない場合、行列の大半は 0 で埋まるため疎行列とみなせる。逆に、多くの成分が非零になる場合は密行列に近づく。実際の計算では、この性質に応じて保存形式やアルゴリズムを選ぶことが重要である。
</INTERNAL_LINK_CANDIDATES> 頂点（グラフを構成する個々の要素） 辺（頂点どうしを結ぶ接続） 行列（数を表形式で並べた配列） 対称行列（転置しても同じになる行列） 入次数（外から入ってくる辺の数） 出次数（外へ出ていく辺の数） 多重辺（同じ頂点対の間に複数ある辺） 自己ループ（同じ頂点に戻る辺） 重み付きグラフ（辺に数値属性が付いたグラフ） 固有値（行列の特徴を表す数） スペクトル（行列の固有値の集合） 対角化（行列を簡単な形に変換する操作） 深さ優先探索（グラフをたどる探索法） 幅優先探索（層ごとに広がる探索法） 連結性（グラフ全体がつながっている性質） 最短経路問題（2点間の最も短い経路を求める問題） 隣接リスト（各頂点の接続先を列挙する表現） 疎行列（非零成分が少ない行列） 密行列（非零成分が多い行列）