<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=default"></script>
一些矩陣分類
$Z$-矩陣: 非對(duì)角元素為非正實(shí)數(shù)的矩陣.
$M$-矩陣: 所有特征值的實(shí)部為非負(fù)實(shí)數(shù)的$Z$-矩陣.
圖(graph)
給定一個(gè)節(jié)點(diǎn)集 合$V$ 和 這些節(jié)點(diǎn)形成的邊集合 $E$, 就構(gòu)成了一個(gè)圖 $G := (V, E)$.
如果 $E$ 中的邊沒有方向, 就稱 $G$ 為無向圖(undirected graph)；如果 有方向, 則稱 $G$ 為有向圖(directed graph).
如果 $E$ 中的每條邊有一個(gè)權(quán)重值, 則稱 $G$ 為帶權(quán)圖(weighted graph); 如果沒有, 則稱 $G$ 為無權(quán)圖(unweighted graph).
如果 $G$ 中任一個(gè)節(jié)點(diǎn) $v_i$ 都沒有指向自身的邊, 或者多于1條指向另外一個(gè)節(jié)點(diǎn)$v_j$的邊, 則稱 $G$ 為簡(jiǎn)單圖(simple graph) , 否則稱為非簡(jiǎn)單圖(nonsimple graph).
圖 $G$ 中如果任意兩個(gè)節(jié)點(diǎn)都存在一條路徑, 則稱 $G$ 為連通圖(Connected Graph).
圖 $G$ 的連通分量(Connected Component)是$G$的一個(gè)最大連通子圖.
正則圖(Regular Graph)中每個(gè)節(jié)點(diǎn)的度是一樣的.
Laplacian 矩陣#
給定一個(gè)無向, 無權(quán)的簡(jiǎn)單圖 $G =(V,E)$, $n = |V|$ 表示節(jié)點(diǎn)個(gè)數(shù), Laplacian 矩陣 $L$ 一個(gè)定義如下 $n\times n$矩陣
$$ L = D - A$$
其中 $D$ 是 $G$ 的度矩陣(degree matrix), 它為對(duì)角矩陣, 且$D_{i,i}$為節(jié)點(diǎn) $v_i$的度; $A$ 為 $G$ 的鄰接矩陣(adjacency matrix), 如果節(jié)點(diǎn) $v_i$ 和 $v_j$ 之間存在一條邊 $\in E$, 則 $A_{i,j} = A_{j,i} = 1$, 否則 $A_{i,j}= A_{j,i} = 0$, 可見 $A$ 是一個(gè)對(duì)稱矩陣.
Laplacian 矩陣的性質(zhì)
給定一個(gè)無向圖 $G$, 設(shè)它的 Laplacian 矩陣 $L$ 的特征值為 $\lambda_0 \leq \lambda_1 \cdots \lambda_{n-1} $:
- $L$ 是一個(gè)對(duì)稱矩陣.
- $L$ 是半正定的, 由對(duì)稱和對(duì)角占優(yōu)可以證明.
- $L$ 是一個(gè) $M$ 矩陣.
- $L$ 的行和\列和都為0, 所以0是$L$的特征值, 對(duì)應(yīng)特征向量 為 $n$ 維向量 $ ( 1, 1, 1, \ldots, 1) $.
- $L$ 的特征值中 0 出現(xiàn)的次數(shù)為連通子圖的個(gè)數(shù).
- $L$ 最小的非零的特征值稱為 $L$ 的譜隙(spectral gap).
- $L$ 第二最小的特征值稱為 $G$ 的代數(shù)連通度(algebra connectivity).
