Notes on Graph Theory

Matrix-Tree

矩阵的秩、迹、特征值、特征向量

对角化

$G \rightarrow M, M^k, k \in N^*$.

$G=k_n$.

---

Hoffman-Singleton

$G, \Delta-free, C_4-free, r-regular$.

$(1) |v| \ge r^2+1$.

$(2) r, |v|=r^2+1$.

$G \rightarrow A, (1, 1, …, 1)A=r(1, 1, …, 1)$.

$A^2=\begin{bmatrix} r & 0/1 & 0/1 & … & 0/1 \\ 0/1 & r & 0/1 & … & 0/1 \\ 0/1 & 0/1 & r & … & 0/1 \\ … & … & … & … & … \\ 0/1 & 0/1 & 0/1 & 0/1 & r\end{bmatrix}$.

$A^2+A=\begin{bmatrix} r & 1 & 1 & … & 1 \\ 1 & r & 1 & … & 1 \\ 1 & 1 & r & … & 1 \\ … & … & … & … & … \\ 1 & 1 & 1 & 1 & r\end{bmatrix}$.

$I=\begin{bmatrix} 1 & 0 & … & 0 \\ 0 & 1 & … & 0 \\ … & … & … & … \\ 0 & 0 & 0 & 1\end{bmatrix}$.

$J=\begin{bmatrix} 1 & 1 & … & 1 \\ 1 & 1 & … & 1 \\ … & … & … & … \\ 1 & 1 & 1 & 1\end{bmatrix}$.

$A\alpha=\lambda\alpha, \lambda$是$A$特征值，$\alpha$是$A$特征向量。

$A\alpha=\lambda\alpha=\lambda I\alpha$.

$(A-\lambda I)\alpha=0$.

$f(x)=|A-\lambda I|$.

$I$特征值为$1$.

$A^2+A=(r-1)I+J$.

特征值为$r-1+n, r-1, r-1, …, r-1 (n-1)$个。

$r^2+r, r-1, r-1, …, r-1 (n-1)$个。

$\lambda^2+\lambda=r^2+r, r-1$.

$\lambda=r || {-1 \pm \sqrt{4r-3} \over 2}$.

$tr(A)=0=r+k_1{-1+\sqrt{4r-3} \over 2}+k_2{-1-\sqrt{4r-3} \over 2}, k_1+k_2=n-1$.

$r=2, 3, 7, 57$.

---

Cauchy Binet

$\begin{bmatrix} x_1 & x_2 & … & x_n \\ y_1 & y_2 & … & y_n \end{bmatrix}\begin{bmatrix} z_1 & w_1 \\ z_2 & w_2 \\ … & … \\ z_n & w_n \end{bmatrix}=\begin{bmatrix} \sum x_iz_i & \sum x_iw_i \\ \sum y_iz_i & \sum y_iw_i\end{bmatrix}=A$.

$|A|=\sum_{i, j} \begin{vmatrix}\begin{bmatrix} x_i & x_j \\ y_i & y_j \end{bmatrix}\begin{bmatrix} z_i & w_i \\ z_j & w_j \end{bmatrix}\end{vmatrix}$.

$m \times n A, n \times m B$.

$|AB|=\sum_{i_1, i_2, …, i_m} \begin{vmatrix}A\begin{bmatrix} 1 & 2 & … & m \\ i_1 & i_2 & … & i_m \end{bmatrix} B\begin{bmatrix} i_1 & i_2 & … & i_m \\ 1 & 2 & … & m \end{bmatrix}\end{vmatrix}$.

---

Laplace

$a_{i, i}=deg(v_i), a_{i, j}=v_i-v_j$间连边数的相反数。

$L(G) \rightarrow L_v(G), G=det(L_v(G))$.

$\begin{matrix} & & & e(G) & & & \\ & & e_1 & e_2 & e_3 & … & e_m \\ & v_1 & 1 & 1 & & & \\ & v_2 & 1 & & 1 & & 1 \\ v(G) & v_3 & & 1 & & & 1 \\ & … & & & & & \\ & v_n & & & 1 & & \end{matrix}$.

随意为$G$定向$\overline{G}=Q \rightarrow Q_v$。

$QQ’=L(G)$.

$det(L_v(G))=det(Q_vQ_v’)$.

Cayley Formula

完全图$K_n$的生成树个数为$n^{n-2}$。

Proofs from THE BOOK.