スペクトルグラフ理論について詳しく解説

導入

スペクトル グラフ理論は、グラフのスペクトルとそのプロパティの間の関係に焦点を当てており、代数グラフ理論の一部です。グラフは複数の行列で表すことができ、行列の固有値がそのスペクトルを構成します。一般に、隣接行列と正規化ラプラシアン行列に興味があります。

行列とその関係

グラフG = ( V , E )について考えます。ここで、 V は頂点のセットを示し、 E はエッジのセットを示します。グラフには| があります。 V | = n個の頂点、で示される

と| E | = m 個のエッジ、で示される 。グラフGの隣接行列Aの各要素は次のように定義されます。

$$ {a_{ij}=\left\{\begin{array}{rl} 1 & \mbox{si } (v_i,v_j)\in E \\ 0 & \mbox{sinon.} \end{array}\right.} $$

次数行列Dは対角行列で、要素D _{i i は}頂点iの接続数、つまりその次数に対応します。この行列と前の行列を使用して、ラプラシアン行列L = D − Aを定義することもできます。その正規化形式L ‘は、 L ‘ = D ^{− 1 / 2} L D ^{− 1 / 2} = I − D ^{− 1 / 2} A D ^{− 1 / 2}によって取得します。ここで、 I は単位行列を示します。または、直接取得することもできます。各要素ごとに次のようになります。

$$ {\ell_{i,j}:= \begin{cases} 1 & \mbox{si}\ i = j\ \mbox{et}\ \deg(v_i) \neq 0\\ -\frac{1}{\sqrt{\deg(v_i)\deg(v_j)}} & \mbox{si}\ i \neq j\ \mbox{et}\ v_i \text{ est adjacent a } v_j \\ 0 & \text{sinon}. \end{cases} } $$

最後に、グラフG = ( V , E )の出現行列Mは、次の次元行列|になります。 V | × | E |ここで、頂点v _iがエッジx _jの端点である場合、エントリb _{i j}は 1、そうでない場合は 0 です。次の一連の関係があります。ここで、 I は単位行列を示します。

• A = M M ^T − D
• 折れ線グラフL ( G )の隣接行列の場合、 A = M ^T M − 2 I
• 細分グラフS ( G )の隣接行列の場合、
  $$ {A = \begin{pmatrix} 0 &M^T\\ M & 0\\ \end{pmatrix}} $$

行列のスペクトルはその固有値のセットです

;拡張して、グラフのスペクトルについて話します。固有値λの代数的多重度は、 特性多項式の単項式( X − λ)のべき乗(つまり、特性多項式の根の多重度) であることを思い出してください。特性多項式を変更して、グラフの他の特性を考慮することも可能です。デフォルトでは、多項式P _G (λ) = |を考慮します。 λ I − A | 、ただし、 R _G (λ) = |などの変形にも興味があるかもしれません。 λ I − D − A |またはQ _G (λ) = | D | ^{− 1} * | λ D − A | 。

正規化されたラプラシアン行列のスペクトル

固有値λ _{1 は}、グラフの代数的接続性と呼ばれます。スペクトルの重要な特性を以下にまとめます。

• _λ0 = 0 。
• $$ {\sum_i \lambda_i \le n} $$
  グラフがつながっている場合。
• もし
  $$ {n \ge 2} $$
  そして G が完全なグラフであるとすると、
  $$ {\lambda_1 = \frac{n}{n-1}} $$
  、 さもないと
  $$ {\lambda_1 \le 1} $$
  。
• グラフが接続されている場合は、 λ ₁ > 0 になります。 λ _i = 0の場合、
  $$ {\lambda_{i+1} \neq 0} $$
  この場合、 G は正確にi + 1 個のコンポーネント (つまり、接続されたグラフ) を持ちます。
• $$ {\lambda_i \le 2} $$
  $$ {\forall i \le n – 1} $$
  。

この行列の他のプロパティの中でも、その行列式はグラフ内のスパニング ツリーの数を与えます。

隣接行列スペクトル

グラフ行列は正であり、グラフがつながっている場合は減らすことができません。無向グラフの場合、行列は対称かつエルミート行列です。つまり、

またははAの随伴行列です。行列のトレースはループ数の 2 倍に等しくなります。実際、対角線上の要素はループの存在を示し、トレースはこれらの要素の合計です。次のようなプロパティがあります。

• 行列のスペクトル半径ρ( A ) 、つまり最大固有値は次の条件を満たします。
  $$ {2 \cdot \cos(\frac{\pi}{n + 1}) \le \rho (A) \le n – 1} $$
  接続されたグラフの場合。パスの場合は下限に到達し、完全なグラフでは上限に到達します。
• グラフがk正則の場合、 ρ( A ) = kとなり、 ρ( A )の多重度が連結成分の数を与えます。
• グラフにサイクルが含まれていない場合に限り、すべての固有値はゼロになります。
• − ρ( A )も固有値である場合、グラフには奇数長サイクルのみが含まれます。
• k 個の異なる固有値がある場合、直径D は次の条件を満たします。
  $$ {D \le m – 1} $$
  。
• 最大安定のサイズtは次の条件を満たします。
  $$ {t \le p_0 + min(p_-,p_+)} $$
  ここで、 p ₋ 、 p ₀ 、 p _{+ は}それぞれ、0 以上の小さい固有値の数です。
• $$ {\frac{\rho(A)}{-q} + 1 \le \chi(G) \le \rho(A) + 1} $$
  ここで、 χ( G )は色彩数、 q は最小の固有値です。