ryamadaのコンピュータ・数学メモ

隣接代数

隣接代数グラフグラフ理論スペクトル *-代数

こちらで代数的確率論・量子確率論のことを書いた
その中に出てくる隣接代数というものを整理する
隣接行列とは、いわゆるグラフ $G=(V,E)$ の $|V| \times |V|$ 行列のことで、エッジで結ばれたノードに対応する要素が１でそれ以外が０であるような行列のこと
グラフは有限かも無限かもしれないないけれど、「局所有限」であることを仮定することもできる（こともある）
局所有限とは、全てのノードの次数が有限であることである
そうすると、隣接行列のm乗 $A^m$ を考えたとき、 $(A^m)_{xy} = \sum_{x_1,...,x_m-1 \in V} A_{x_1x_1}A_{xx2}...A_{x_{m-1}y}$ の和の中に現れる項のうち有限個のものだけが非０であるので、 $A^m$ の(x,y)成分が定義できる、という意味で、局所有限なら無限グラフでも隣接行列Aの生成する $A^0,A,A^2,...$ は隣接代数を構成することが示せる
さらに、 $A^m$ を用いた複素係数多項式全体も通常の行列演算で可換な*^代数になる
これがグラフGの隣接代数
*-代数には対合の存在が必要だがそれは
- $(\sum_{i=0}^m c_i A^i )^* = \sum_{i=0}^m \bar{c_i} A^i$ で与えられる