グラフ理論の特にグラフのスペクトルに関するまとめ

参考書一覧

情報数理の基礎と応用

疑問点

特性方程式の係数が何を意味するか(特にc_n,n>3)
グラフのスペクトルを何に使うのか

前提

グラフ G = (V, E)
- Vは頂点の集合
- Eは辺の集合
隣接行列 A: グラフGの辺の情報を保持したn次行列を
- A_{i,j}: 頂点iと頂点jの隣接関係を表す
  - 値が1であれば両頂点は隣接している
  - 値が0であれば両頂点は隣接していない
  - (無向グラフであれば) A{i,j} = A{j,i}
  - 対角成分 A_{i,i}は0

グラフの特性方程式

頂点数がnのグラフGの特性多項式は以下のn次多項式となる．

$\phi_G(\lambda) = | \lambda E - A | \\ = \lambda^n + c_1 \lambda^{n-1} + c_2 \lambda^{n-2} + \cdots + c_{n-1} \lambda + c_n$

係数c_k

c_1 = 0
c_2 = - ｜E|
c_3 = -2|#triangles|

グラフの固有値

グラフGの特性多項式の実根を指す．

グラフのスペクトル

グラフGのスペクトルは固有値とその重複度によって，以下のように定義される．

$\mathrm{Spec}(G) = \begin{pmatrix} \lambda_1 & \lambda_2 & \cdots & \lambda_s \\ m_1 & m_2 & \cdots & m_s \end{pmatrix} \\ \sum_{i=1}^s m_i \lambda_i = \textrm{Tr}A = 0$

グラフのスペクトル分布

グラフGの固有値の重複度の離散分布をスペクトル分布と呼ぶ．

$\mu_G = \frac{1}{|V|} \sum_{i=1}^s m_i \delta_{\lambda_i}$

I am Charmie

メモとログ

Graph Theory: Spectrum