【グラフ理論】隣接行列とは？ 定義・イメージから隣接行列の固有値の重要性についても解説
こんにちは！半沢です！
今回の記事ではグラフ理論における隣接行列(adjacency matrix)について解説したいと思います。
定義を見ただけではどのように用いるのかが分かりにくいので，そのイメージについても話していきたいと思います。
ぜひ読んでいってください。
隣接行列(adjacency matrix)
定義
\(n\,\)点\(\,v_1,v_2,\ldots,v_n\,\)からなる無向単純グラフ\(\,G=(V,E)\,\)に対し，
\(a_{ij} = \left\{\begin{array}{ll}1 & (v_iv_j\in E) \\0 & (v_iv_j \not\in E)\end{array}\right.\)
から定められる\(\,n\,\)次正方行列\(\,A=(a_{ij})\,\)を\(\,G\,\)の隣接行列と呼ぶ。
※無向単純でないグラフの隣接行列も定義することは可能ですが，このサイトでは取り扱いません。
具体例を通してその定義を確認していきましょう。
上のように頂点に番号\(\,v_1,v_2,v_3,v_4\,\)をつけたグラフの隣接行列は次のようになります。
\(\begin{pmatrix}\; 0 & 1 & 0 & 0\; \\ \;1 & 0 & 1 & 1\; \\ \;0 & 1 & 0 & 1\; \\ \;0 & 1 & 1 & 0\; \end{pmatrix}\)
頂点の番号の付け方として下の図のようなものも考えられるので，
\(\begin{pmatrix}\; 0 & 0 & 0 & 1\; \\ \;0 & 0 & 1 & 1\; \\ \;0 & 1 & 0 & 1\; \\ \;1 & 1 & 1 & 0\; \end{pmatrix}\)
も同じグラフの隣接行列となります。
定義から簡単分かる次のpointをしっかり押さえておきましょう。
- 隣接行列は対角成分が\(\,0\,\)の，実対称行列である。
- 隣接行列は頂点の番号の付け方によって異なる。
性質
この節では隣接行列のイメージを持つ上で重要な性質を紹介&証明していきたいと思います。
性質\([1]\)
グラフ\(\,G=(V,E)\,\)の隣接行列を\(\,A=(a_{ij})\,\)とおくと，
\(A^n\,\)の第\(\,(i,j)\,\)成分\(\,a_{ij}^{(n)}\,\)は長さ\(\,n\,\)の\(\,v_i\text{-}v_j\,\)歩道の本数に等しい。
それでは性質\([1]\)の証明です。
行列の積の定義から
\(\displaystyle a_{ij}^{(n)}=\sum_{k_1,k_2,\ldots,k_{n-1} \geq 1}^{|V|}a_{ik_1}a_{k_1k_2}\cdots a_{k_{n-1}j}\)
となります。
\(a_{ij}\,\)の値が\(\,1,0\,\)のみであることから
この和の各項\(\,a_{ik_1}a_{k_1k_2}\cdots a_{k_{n-1}j}\,\)の値も\(\,0,1\,\)です。
この項が\(\,1\,\)となるときについて考えると
となります。
つまり長さ\(\,n\,\)の歩道\(\,v_iv_{k_1}\cdots v_{j}\,\)があると，
\(a_{ik_1}a_{k_1k_2}\cdots a_{k_{n-1}j}\,\)は\(\,+1\,\)カウントしてくれます。
よって，これらを足し上げた\(a_{ij}^{(n)}\)について
\(a_{ij}^{(n)}=(\)長さ\(\,n\,\)の\(\,v_i\text{-}v_j\)歩道の本数\()\)
となります。
したがって証明終了です。\(\quad\square\)
性質\([1]\)から次の性質が簡単に導かれます。
性質\([2]\)
\(A^{2}\,\)の第\(\,(i,i)\,\)成分\(\,a_{ii}^{(2)}\,\)は点\(\,v_i\,\)の次数となる。
性質\([3]\)
\(\dfrac{\mathrm{tr}(A^3)}{6}\)はグラフ\(\,G\,\)内の三角形の個数である。
これらの性質から分かるように，隣接行列\(\,A\,\)のイメージは次のようになります。
\(A^{n}\,\)は長さ\(\,n\,\)の歩道についての情報をもつ。
固有値
隣接行列はもちろん行列なので，その固有値を考えることができます。
さらに隣接行列は頂点の番号の付け方によって異なりますが，
その固有値は番号の付け方によらないという良い性質を持っています。(補遺より)。
そのため隣接行列の固有値は，グラフの不変量として機能します。
実際にそのことを利用して，このサイトでは友好定理の証明を行っています。
さて隣接行列は実対称行列で，その固有値はすべて実数なので，それらを
\(\alpha_1\geq \alpha_2\geq\cdots\geq \alpha_n\)
と書くことにします。
隣接行列は対角成分が\(\,0\,\)で\(\,\mathrm{tr}(A)=0\,\)より，まず簡単に\(\,\alpha_1\geq 0,\alpha_n\leq 0\,\)が分かります。
さらに隣接行列の固有値について次のことが知られています。
グラフ\(\,G\,\)の最大次数を\(\,\Delta\,\)とおくと，
その隣接行列\(\,A\,\)の固有値は\(\,-\Delta\,\)から\(\,\Delta\,\)の間にある。
それでは証明です。
\(\alpha_1\leq \Delta\,\)かつ\(\,\alpha_n\geq -\Delta\,\)を示せば良いですね。
まず\(\,\alpha_1\leq \Delta\,\)を示します。
\(\alpha_1\,\)の固有ベクトルを\(\,\mathbf{x}\,\)とおきます。
\(\mathbf{x}\,\)の成分でその絶対値が最大であるものを\(\,x_j\,\)とおきます。
\(\mathbf{x}\not=0\,\)より\(\,x_j\not=0\,\)です。
もし\(\,x_j\,\)が負なら，固有ベクトルを\(\,-\mathbf{x}\,\)に取り換えることで\(\,x_j\gt 0\,\)としても構いません。
このとき頂点\(\,v_j\,\)と隣接している点の集合を\(\,N(j)\,\)と書くことにすると
\(\displaystyle \alpha_1x_j=(Ax)_j=\sum_{v_i\in N(j)}x_i\leq \sum_{v_i\in N(j)}x_j=x_jd(v_j)\leq x_j\Delta\)
よって\(\,\alpha\leq \Delta\,\)となります。
\(\,\alpha_n\geq -\Delta\,\)も同様に示すことができるので，証明終了です。\(\quad\square\)
まとめ
今回の記事では隣接行列を解説いたしました。
隣接行列のイメージをつかむことができたでしょうか？
隣接行列の固有値はグラフの不変量となるので，スペクトラルグラフ理論と呼ばれる分野ではかなり重宝されます。
興味のある方は友好定理の証明で隣接行列の固有値の威力をぜひ味わってみてください。
もし「説明がわかりにくい」などご要望・ご感想がありましたら，
X（旧:Twitter）で#トイカラでつぶやいていただけると，できる限り対応します。
ここまで読んでいただき，ありがとうございました。
補遺
ここでは固有値で触れた
隣接行列の固有値は頂点の番号の付け方によらない。
を示していきたいと思います。
ある頂点の番号の付け方\(\,v_1,v_2,\ldots,v_n\,\)を固定し，その隣接行列を\(\,A\,\)とおきます。
別の頂点の番号の付け方は，ある\(\,n\,\)文字の置換\(\,\pi\,\)を用いて\(\,v_{\pi(1)},v_{\pi(2)},\ldots,v_{\pi(n)}\,\)と書けます。
この隣接行列は\(\,A\,\)の行，列をそれぞれ置換\(\,\pi\,\)で入れ替えたものです。
このことを行列の操作で表せば，置換行列\(\,P_\pi\,\)(分からない方はWikipediaを参照してください)を用いて
\(P_{\pi}AP_{\pi}^{-1}\,\)と表せます。
ここでこの\(\,P_{\pi}AP_{\pi}^{-1}\,\)の特性方程式は
となり\(\,A\,\)の特性方程式に一致します。
よって\(\,A\,\)と\(\,P_{\pi}AP_{\pi}^{-1}\,\)の固有値も一致し，題意は示されました。\(\quad\square\)
参考図書
- \([1]\) 惠羅博,土屋守正.”シリーズ／情報科学の数学 増補改訂版 グラフ理論”.増補改訂版.産業図書.2010出版.p24-26.
- \([2]\) “置換行列 – Wikipedia”.Wikipedia.2023-01-15更新.https://ja.wikipedia.org/wiki/%E7%BD%AE%E6%8F%9B%E8%A1%8C%E5%88%97.2024-07-07参照
