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.

RegMs If

418 I'm a teapot

Leave a Reply

Your email address will not be published. Required fields are marked *