克希荷夫矩陣─樹定理

本文的閱讀等級：高級

令 $G(V,E)$ 為一無向圖，其中 $V$ 是頂點 (vertex) 集合， $E$ 是邊 (edge) 集合，頂點數 $n=\vert V\vert$ 稱為圖 $G$ 的階 (order)。每一條無向邊 (以下簡稱邊) 有兩個頂點為其端點 (endpoint)。因此，一邊 $e\in E$ 定義為 $V$ 中兩頂點 $u$ 和 $v$ 組成的集合或無序對，記為 $e=\{u,v\}=\{v,u\}$ ，我們稱頂點 $u$ 和 $v$ 鄰接 (adjacent)，並稱頂點 $u$ 和 $v$ 與邊 $e$ 有關聯 (incident)。以下考慮簡單圖，意思是不存在自環 (self-loop)，即一邊的兩端點為同一頂點，並且不存在重邊 (multiedge)，即任意兩相異頂點至多僅存在一連接邊。若一圖的任兩頂點之間存在一序列鄰接頂點構成的連通路徑 (path)，則稱為連通圖 (connected graph)。若 $V'\subseteq V$ 且 $E'\subseteq E$ ，我們說 $G(V',E')$ 是圖 $G(V,E)$ 的一個子圖 (subgraph)。圖 $G=(V,E)$ 的一個連通元件是指子圖 $G(V',E')$ 為一連通圖，但任意 $u\in V'$ 和 $v\in V\setminus V'$ 之間不存在連通路徑。如果 $G(V,E)$ 是一個不含迴圈 (cycle) 的連通圖，則稱為一棵樹 (tree)。換一個說法， $G(V,E)$ 是一棵樹的一個等價條件為 $G$ 是連通圖且 $\vert E\vert=\vert V\vert-1$ 。給定一連通圖 $G(V,E)$ ，最小生成樹 (minimal spanning tree) 是一個連通子圖 $G(V,S)$ 且 $\vert S\vert=\vert V\vert-1$ 。若 $G$ 不是連通圖，則不存在最小生成樹。標記頂點 (labeled vertex) 是指每一頂點都有一個識別記號 (例如 $v_i$ 或 $i$ )，具有標記頂點的圖稱為標記圖。本文討論一個經典的圖論問題：給定一簡單連通標記圖 $G(V,E)$ ，共有多少棵不同的最小生成樹？這個問題的答案稱為克希荷夫矩陣─樹定理 (Kirchhoff’s matrix-tree theorem)。下面介紹一個優美的線性代數證明，預備知識包括量空間分析、行列式、特徵值與特徵向量。

對應 $n$ 階圖 $G=(V,E)$ ， $V=\{v_1,\ldots,v_n\}$ ，鄰接矩陣 (adjacency matrix) $A=[a_{ij}]$ 為一 $n\times n$ 階矩陣，定義如下： $a_{ij}=1$ 若 $\{v_i,v_j\}\in E$ ，否則 $a_{ij}=0$ (見“線性代數在圖論的應用 (一)：鄰接矩陣”)。因為 $G$ 是簡單圖，每一 $a_{ii}=0$ 。明顯地， $a_{ij}=a_{ji}$ ， $A$ 是一對稱矩陣。對於頂點 $v_i$ ，分支度 (度數，degree) $d_i$ 是與 $v_i$ 有關聯的邊數，或者說與 $v_i$ 鄰接的頂點數，即鄰接矩陣 $A$ 的第 $i$ 列 (row) 和， $d_i=\sum_{j=1}^na_{ij}$ 。對應圖 $G(V,E)$ ， $L=D-A$ 稱為拉普拉斯矩陣 (Laplacian)，其中 $D=\text{diag}(d_1,\ldots,d_n)$ 稱為分支度矩陣。因為 $A$ 和 $D$ 是對稱矩陣， $L$ 是對稱矩陣。拉普拉斯矩陣 $L=[l_{ij}]$ 的主對角元 $l_{ii}$ 等於頂點 $i$ 的分支度 $d_i$ ，非主對角元 $l_{ij}=-1$ 若頂點 $i$ 與 $j$ 鄰接，否則 $l_{ij}=0$ 。見下例： $G=(V,E)$ ，其中 $V=\{1,2,3,4\}$ ， $E=\{\{1,2\},\{1,3\},\{1,4\},\{2,4\},\{3,4\}\}$ 。

對應此 4 階圖的鄰接矩陣 $A$ 、分支度矩陣 $D$ 和拉普拉斯矩陣 $L$ 分別是

$\displaystyle A=\begin{bmatrix} 0&1&1&1\\ 1&0&0&1\\ 1&0&0&1\\ 1&1&1&0 \end{bmatrix},~~D=\begin{bmatrix} 3&0&0&0\\ 0&2&0&0\\ 0&0&2&0\\ 0&0&0&3 \end{bmatrix},~~L=\left[\!\!\begin{array}{rrrr} 3&-1&-1&-1\\ -1&2&0&-1\\ -1&0&2&-1\\ -1&-1&-1&3 \end{array}\!\!\right]$ 。

拉普拉斯矩陣 $L$ 具有下列性質 (見“線性代數在圖論的應用 (三)：拉普拉斯矩陣”)： $L$ 是半正定矩陣 (特徵值必不為負數)，最小的特徵值為 $0$ ，對應特徵向量 $\mathbf{e}=(1,\ldots,1)^T$ (由 $L$ 的每一列和皆為零即可確認)，且特徵值 $0$ 的重數等於 $G$ 的連通元件數。因為 $L$ 是實對稱矩陣，故可正交對角化，推論 $\hbox{rank}L$ 等於非零特徵值數 (見“幾何重數不大於代數重數的證明”)。因此，若 $G$ 為一 $n$ 階連通圖，則 $L$ 的特徵值 $0$ 的重數為 $1$ ，即有 $\hbox{rank}L=n-1$ 。若 $G$ 不是連通圖，則 $L$ 的特徵值 $0$ 的重數大於 $1$ ，即有 $\hbox{rank}L<n-1$ 。我們將這個結論寫入定理一。

定理一：對於一 $n$ 階圖 $G$ ，沿用前述記號，若 $\hbox{rank}L=n-1$ ，則 $G$ 是連通圖；若 $\hbox{rank}L<n-1$ ，則 $G$ 不是連通圖。

給定一無向簡單圖 $G(V,E)$ ，對於每一 $e_i=\{v_j,v_k\}\in E$ ，任意指定 $v_j$ 為邊 $e_i$ 的起始頂點， $v_k$ 為邊 $e_i$ 的終止頂點。設 $m=\vert E\vert$ 且 $n=\vert V\vert$ 。我們定義圖 $G$ 的 $m\times n$ 階有向關聯矩陣 (oriented incidence matrix) $B=[b_{ij}]$ ，其中 $b_{ij}=1$ 若 $v_j$ 是邊 $e_i$ 的起始頂點， $b_{ij}=-1$ 若 $v_j$ 是邊 $e_i$ 的終止頂點， $b_{ij}=0$ 若 $v_j$ 不是邊 $e_i$ 的一個端點 (見“線性代數在圖論的應用 (二)：關聯矩陣”)。上例 4 階圖 $G$ 的一個有向關聯矩陣為

$\displaystyle B=\left[\!\!\begin{array}{rrrr} 1&-1&0&0\\ 1&0&-1&0\\ 1&0&0&-1\\ 0&1&0&-1\\ 0&0&1&-1 \end{array}\!\!\right]$ 。

定理二：對於一 $n$ 階圖 $G$ ，

$L=B^TB=D-A$ 。

有向關聯矩陣 $B$ 的每一列有兩個非零元， $1$ 和 $-1$ ， $B$ 的第 $j$ 行 (column) 的非零元的列指標對應與頂點 $v_j$ 有關聯的邊。因為 $B^TB$ 的 $(i,j)$ 元，記為 $(B^TB)_{ij}$ ，是 $B$ 的第 $i$ 行與第 $j$ 行的內積，故 $(B^TB)_{ii}$ 等於頂點 $v_i$ 的分支度 $d_i$ ，且當 $i\neq j$ ， $(B^TB)_{ij}=-1$ 若 $\{v_i,v_j\}\in E$ ，否則 $(B^TB)_{ij}=0$ 。所以， $B^TB=D-A=L$ 。這個結果與下述事實相符：任一 $n\times n$ 階實對稱半正定矩陣 $L$ 可分解為 $L=B^TB$ ，其中 $B$ 是 $m\times n$ 階實矩陣， $\hbox{rank}B=\hbox{rank}L$ (見“半正定矩陣的判別方法”)。

我們知道 $n$ 階圖 $G(V,E)$ 的最小生成樹 $G(V,S)$ 必須滿足兩個條件： $G(V,S)$ 是一個連通圖且 $\vert S\vert=n-1$ 。在不造成混淆的情況下，以 $\left\langle S\right\rangle$ 代表子圖 $G(V,S)$ ，並約定 $\vert S\vert=n-1$ 。因此， $\left\langle S\right\rangle$ 是一最小生成樹的充要條件是 $\left\langle S\right\rangle$ 是一連通圖。令 $L_S=B_S^TB_S$ 為子圖 $\left\langle S\right\rangle$ 的拉普拉斯矩陣，其中 $B_S$ 是 $(n-1)\times n$ 階有向關聯矩陣。定理一與定理二表明子圖 $\left\langle S\right\rangle$ 是 $G$ 的一最小生成樹等價於 $\hbox{rank}B_S=\hbox{rank}L_S=n-1$ 。考慮子圖 $\left\langle S\right\rangle$ ， $S=\{\{1,2\},\{1,3\},\{1,4\}\}$ ，如下所示：

對應 $\left\langle S\right\rangle$ 的 $3\times 4$ 階有向關聯矩陣為

$\displaystyle B_S=\left[\!\!\begin{array}{rrrr} 1&-1&0&0\\ 1&0&-1&0\\ 1&0&0&-1 \end{array}\!\!\right]$ 。

不難確認 $\hbox{rank}B_S=3$ ，故 $\left\langle S\right\rangle$ 是一最小生成樹。再看 $\left\langle S'\right\rangle$ ， $S'=\{\{1,2\},\{1,4\},\{2,4\}\}$ ，如下：

對應 $\left\langle S'\right\rangle$ 的有向關聯矩陣為

$\displaystyle B_{S'}=\left[\!\!\begin{array}{rrrr} 1&-1&0&0\\ 1&0&0&-1\\ 0&1&0&-1 \end{array}\!\!\right]$ ，

其中第 2 列等於第 1 列與第 3 列的和，可知 $\hbox{rank}B_{S'}=2<3$ ，故 $\left\langle S'\right\rangle$ 不是最小生成樹。

計算 $B_S$ 的矩陣秩固然得以判定 $\left\langle S\right\rangle$ 是否為一最小生成樹，但我們冀望更簡單的算法。因為 $B_S$ 的每一列有兩個非零元， $1$ 和 $-1$ ， $n$ 維常數向量 $\mathbf{e}=(1,\ldots,1)^T$ 滿足 $B_S\mathbf{e}=\mathbf{0}$ ，或表示為 $\mathbf{b}_1+\cdots+\mathbf{b}_n=\mathbf{0}$ ，其中 $\mathbf{b}_j\in\mathbb{R}^{n-1}$ 代表 $B_S$ 的第 $j$ 個行向量。對於任一 $1\le j\le n$ ， $\mathbf{b}_j$ 可寫成其餘 $n-1$ 個行向量的線性組合，即 $\mathbf{b}_j\in\hbox{span}\{\mathbf{b}_1,\ldots,\mathbf{b}_{j-1},\mathbf{b}_{j+1},\ldots,\mathbf{b}_n\}$ ，說明 $B_S$ 的行空間為 $C(B_S)=\hbox{span}\{\mathbf{b}_1,\ldots,\mathbf{b}_{j-1},\mathbf{b}_{j+1},\ldots,\mathbf{b}_n\}$ 。若 $\hbox{rank}B_S=n-1$ ，則 $B_S$ 的任何 $n-1$ 個行向量組成一線性獨立集。反之，若 $\hbox{rank}B_S<n-1$ ，則 $B_S$ 的任何 $n-1$ 個行向量組成一線性相關集。我們可以從 $(n-1)\times n$ 階矩陣 $B_S$ 隨意選取 $n-1$ 個行向量構造一個 $(n-1)$ 階方陣，記為 $\tilde{B}_S$ 。若 $\det \tilde{B}_S\neq 0$ ，則 $\left\langle S\right\rangle$ 是最小生成樹；若 $\det \tilde{B}_S=0$ ，則 $\left\langle S\right\rangle$ 不是最小生成樹。還有一個小問題：如果 $\left\langle S\right\rangle$ 是最小生成樹， $\det\tilde{B}_S$ 的數值是多少？此數值是否隨著選取不同的 $n-1$ 個行向量而改變？以前述最小生成樹 $\left\langle S\right\rangle$ 為例，使用基本列運算的取代、交換，並僅允許乘入 $1$ 或 $-1$ 至各列，可得梯形矩陣：

$\displaystyle\begin{aligned} B_S=\left[\!\!\begin{array}{rrrr} 1&-1&0&0\\ 1&0&-1&0\\ 1&0&0&-1 \end{array}\!\!\right]&\sim \left[\!\!\begin{array}{rrrr} 1&-1&0&0\\ 0&1&-1&0\\ 1&0&0&-1 \end{array}\!\!\right]\\ &\sim \left[\!\!\begin{array}{rrrr} 1&-1&0&0\\ 0&1&-1&0\\ 0&1&0&-1 \end{array}\!\!\right]\\ &\sim\left[\!\!\begin{array}{rrrr} 1&-1&0&0\\ 0&1&-1&0\\ 0&0&1&-1 \end{array}\!\!\right]=B_T \end{aligned}$

上面 $\sim$ 表示列等價 (row equivalent)。基本列運算將 $B_S$ 轉換至梯形矩陣 $B_T$ 的實際作為是移動 $\left\langle S\right\rangle$ 的邊使之成為一道路圖 (path graph) $G(V,T)$ ，記為 $\left\langle T\right\rangle$ ，其中 $\{v_i,v_{i+1}\}\in T$ ， $1\le i\le n-1$ 。基本列運算不改變矩陣秩，故 $\hbox{rank}B_T=\hbox{rank}B_S$ ，可知 $\left\langle T\right\rangle$ 是一個最小生成樹。不僅如此，我們使用限制乘數為 $\pm 1$ 的基本列運算不改變 $\det \tilde{B}_S$ 的大小，僅可能變更 $\det \tilde{B}_S$ 的正負號，也就是說， $\vert\det\tilde{B}_T\vert=\vert\det\tilde{B}_S\vert$ 。明顯地，刪去梯形矩陣 $B_T$ 的任何一個行向量後得到的方陣 $\tilde{B}_T$ 是三角矩陣，且主對角元為 $1$ 或 $-1$ 。因此，不論如何選取 $B_S$ 的 $n-1$ 個行向量， $\vert\det\tilde{B}_S\vert=\vert\det\tilde{B}_T\vert=1$ 。

定理三：對於一 $n$ 階圖 $G$ ，子圖 $\left\langle S\right\rangle$ 滿足 $\vert S\vert=n-1$ ， $\tilde{B}_S$ 是 $B_S$ 的任何一個 $(n-1)$ 階子陣。若 $\vert\det\tilde{B}_S\vert=1$ ，則 $\left\langle S\right\rangle$ 是一最小生成樹；若 $\det\tilde{B}_S=0$ ，則 $\left\langle S\right\rangle$ 不是最小生成樹。

回到本文的問題，簡單連通標記圖 $G(V,E)$ 有多少個不同的最小生成樹？令 $t(G)$ 表示圖 $G$ 的最小生成樹總數。令 $J$ 表示每一元為 $1$ 的常數矩陣，也就是說 $J=\mathbf{e}\mathbf{e}^T$ ，其中 $\mathbf{e}=(1,\ldots,1)^T$ 。定理四說拉普拉斯矩陣 $L$ 的伴隨矩陣 (adjugate，classical adjoint) $\hbox{adj}\,L$ 是一常數矩陣，每一元皆為 $t(G)$ 。

定理四：對於一標記圖 $G$ ，

$\hbox{adj}\,L=t(G)J$ 。

下面是一些有用的伴隨矩陣性質 (見“伴隨矩陣”)：令 $P$ 和 $Q$ 是 $n\times n$ 階矩陣。

$P(\hbox{adj}\,P)=(\det P)I$
$\hbox{adj}\,(PQ)=(\hbox{adj}\,P)(\hbox{adj}\,Q)$
若 $\hbox{rank}P=n-1$ ，則 $\hbox{rank}(\hbox{adj}\,P)=1$ 。
若 $\hbox{rank}P<n-1$ ，則 $\hbox{rank}(\hbox{adj}\,P)=0$ 。
$\hbox{adj}\,(kP)=k^{n-1}\hbox{adj}\,P$
$\hbox{adj}\,(P^T)=(\hbox{adj}\,P)^T$

我們先證明 $\hbox{adj}\,L=cJ$ ，其中 $c$ 是實數。設 $G$ 是一 $n$ 階簡單圖。若 $G$ 是非連通圖，則 $\hbox{rank}L<n-1$ ，因此 $\hbox{rank}(\hbox{adj}\,L)=0$ ，即 $\hbox{adj}\,L=0$ ( $c=0$ )。若 $G$ 是連通圖，則 $\hbox{rank}L=n-1$ 。因為

$L(\hbox{adj}\,L)=(\det L)I=0$ ，

可知 $\hbox{adj}\,L$ 的每一行屬於 $L$ 的零空間 $N(L)$ 。但 $\dim N(L)=n-\hbox{rank}L=1$ 且 $L\mathbf{e}=\mathbf{0}$ ，推得 $N(L)=\hbox{span}\{\mathbf{e}\}$ 。所以， $\hbox{adj}\,L$ 的每一行可表示為 $\mathbf{e}$ 的倍數。又 $L=B^TB$ 是對稱矩陣， $\hbox{adj}\,L$ 也是對稱矩陣。以上結果可推論 $\hbox{adj}\,L=c\mathbf{e}\mathbf{e}^T=cJ$ 。

剩下來的問題是計算 $c$ 。伴隨矩陣 $\hbox{adj}\,L$ 的 $(i,j)$ 元等於 $L$ 的 $(j,i)$ 元的餘因子 (cofactor)，即

$\displaystyle (\hbox{adj}\,L)_{ij}=c_{ji}=(-1)^{i+j}\det\tilde{L}_{ji}$ ，

其中 $\tilde{L}_{ji}$ 代表移除 $L$ 的第 $j$ 列和第 $i$ 行之後得到的 $(n-1)$ 階方陣。因為 $c=c_{ij}$ ， $1\le i,j\le n$ ，可考慮 $c=c_{nn}=\det\tilde{L}_{nn}$ ，其中 $\tilde{L}_{nn}=\tilde{B}_n^T\tilde{B}_n$ ， $\tilde{B}_n$ 代表刪除有向關聯矩陣 $B$ 的第 $n$ 行所得到的 $m\times (n-1)$ 階子陣。利用 Cauchy-Binet 公式 (見“Cauchy-Binet 公式”)，

$\displaystyle \det\tilde{L}_{nn}=\det(\tilde{B}^T_n\tilde{B}_n)=\sum_{S}(\det\tilde{B}_S^T)(\det\tilde{B}_S)=\sum_S(\det\tilde{B}_S)^2$ ，

其中 $S$ 表示從 $m$ 個列選取 $n-1$ 個的組合 (列指標集)，共有 $\binom{m}{n-1}$ 種選取方式， $\tilde{B}_S$ 是從 $\tilde{B}_n$ 挑選對應 $S$ 的 $n-1$ 個列所形成的方陣。套用定理三，推得 $\det\tilde{L}_{nn}=t(G)$ ，證畢。

繼續討論前，先看一個問題：包含 $n$ 個頂點的標記樹共有多少個？答案是 $n^{n-2}$ ，稱為 Cayley 公式。我們曾經介紹德國數學家普呂弗 (Heinz Prüfer) 提出的證明 (見“電影《心靈捕手》的數學問題 (三)”)，下面說明如何利用定理四證明 Cayley 公式。每一個包含 $n$ 個頂點的標記樹與 $n$ 階完全圖 (complete graph) 的最小生成樹有一對一的對應關係 (完全圖是指任意兩相異頂點皆有一邊連接)。考慮等價的問題： $n$ 階完全圖，記為 $K_n$ ，共有多少個最小生成樹？完全圖 $K_n$ 的拉普拉斯矩陣為 (見“線性代數在圖論的應用 (三)：拉普拉斯矩陣”)

$\displaystyle L_K=nI-J=\left[\!\!\begin{array}{cccc} n-1&-1&\cdots&-1\\ -1&n-1&\cdots&-1\\ \vdots&\vdots&\ddots&\vdots\\ -1&-1&\cdots&n-1 \end{array}\!\!\right]$ 。

這種特殊形態的矩陣稱為組合矩陣 (combinatorial matrix)，一般形式如下：

$\displaystyle C=xI+yJ=\begin{bmatrix} x+y&y&\cdots&y\\ y&x+y&\cdots&y\\ \vdots&\vdots&\ddots&\vdots\\ y&y&\cdots&x+y \end{bmatrix}$ 。

若 $C$ 是 $n\times n$ 階，則伴隨矩陣為 (見“特殊矩陣 (17)：組合矩陣”)

$\displaystyle \hbox{adj}\,C=x^{n-2}(x+ny)I-x^{n-2}yJ$ 。

代入 $x=n$ ， $y=-1$ ，就有 $\hbox{adj}\,L_K=\hbox{adj}\,(nI-J)=n^{n-2}J$ ，即得 Cayley 公式 $t(K_n)=n^{n-2}$ 。

定理四可推演出 $t(G)$ 的簡明公式，稱為克希荷夫矩陣─樹定理。

克希荷夫矩陣─樹定理：：對於一 $n$ 階簡單標記圖 $G$ ，

$\displaystyle t(G)=\frac{1}{n^2}\det(L+J)$ 。

使用 $J^2=nJ$ 和 $LJ=0$ ，寫出

$\begin{aligned} (L+J)(nI-J)&=nL+nJ-LJ-J^2\\ &=nL+nJ-nJ\\ &=nL.\end{aligned}$

等號兩邊取伴隨矩陣，左邊是

$\begin{aligned} \hbox{adj}\,((L+J)(nI-J))&=(\hbox{adj}\,(L+J))(\hbox{adj}\,(nI-J))\\ &=n^{n-2}\hbox{adj}\,(L+J)J, \end{aligned}$

右邊是 (套用定理四) $\hbox{adj}\,(nL)=n^{n-1}\hbox{adj}\,L=n^{n-1}t(G)J$ 。合併可得

$\hbox{adj}\,(L+J)J=nt(G)J$ 。

等號兩邊左乘 $L+J$ ， $(L+J)\hbox{adj}\,(L+J)J=nt(G)(L+J)J$ ，繼續化簡為

$\displaystyle \det(L+J)J=nt(G)J^2=n^2t(G)J$ ，

比較 $J$ 的係數即證明所求。

下面給出 $t(G)$ 的另一個表達式。考慮 $n$ 階連通圖 $G$ ，令 $L$ 的非零特徵值為 $\lambda_1,\ldots,\lambda_{n-1}$ 。因為 $L$ 是實對稱矩陣，所有的特徵向量 $\{\mathbf{e},\mathbf{x}_1,\ldots,\mathbf{x}_{n-1}\}$ 組成一正交集，其中 $L\mathbf{e}=\mathbf{0}$ ，且 $L\mathbf{x}_i=\lambda_i\mathbf{x}_i$ ， $\mathbf{x}_i\in\hbox{span}\{\mathbf{e}\}^\perp$ 。因此， $(L+J)\mathbf{e}=L\mathbf{e}+\mathbf{e}\mathbf{e}^T\mathbf{e}=n\mathbf{e}$ ，且 $(L+J)\mathbf{x}_i=L\mathbf{x}_i+\mathbf{e}\mathbf{e}^T\mathbf{x}_i=\lambda_i\mathbf{x}_i$ ， $i=1,\ldots,n-1$ 。合併以上結果， $L+J$ 的特徵值為 $n,\lambda_1,\ldots,\lambda_{n-1}$ ，可知 $\det(L+J)=n\lambda_1\cdots\lambda_{n-1}$ ，故圖 $G$ 的最小生成樹總數為

$\displaystyle t(G)=\frac{1}{n}\lambda_1\cdots\lambda_{n-1}$ 。

最後我們計算前例 4 階圖的最小生成樹數。寫出

$\displaystyle L+J=\left[\!\!\begin{array}{rrrr} 4&0&0&0\\ 0&3&1&0\\ 0&1&3&0\\ 0&0&0&4 \end{array}\!\!\right]$ ，

則 $t(G)=4^{-2}\det(L+J)=4^{-2}\cdot 128=8$ 。另外， $L$ 的非零特徵值為 $2,4,4$ ，由此亦可得 $t(G)=(1/4)\cdot 2\cdot 4\cdot 4=8$ 。讀者不妨自行畫出所有的最小生成樹。

	陳倍恩 on 線性代數的第一堂課──矩陣乘法的定義
	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨

克希荷夫矩陣─樹定理

Leave a Reply Cancel reply

搜尋(繁體中文或英文)

訊息看板

近期文章

線性代數專欄

其他主題專欄

每週問題

數據充分性問題

其他分類

Recent Comments

近期最多人點閱

分類

Archives

標籤雲

線代線上影音課程

線代學習網站

線代電子書

矩陣計算器

LaTeX

Blogroll

訂閱

閱讀導引

學習資源

專題探究

急救查詢

其他分頁

Meta

網路狀態

Blog Stats

克希荷夫矩陣─樹定理

Share this:

Like this:

Leave a Reply Cancel reply

搜尋(繁體中文或英文)

訊息看板

近期文章

線性代數專欄

其他主題專欄

每週問題

數據充分性問題

其他分類

Recent Comments

近期最多人點閱

分類

Archives

標籤雲

線代線上影音課程

線代學習網站

線代電子書

矩陣計算器

LaTeX

Blogroll

訂閱