110 年 國立成功大學資訊工程系碩士班《計算機數學》

核心觀念

生成樹是包含圖中所有頂點的連通無環子圖；若有 $n$ 個頂點，生成樹恰有 $n-1$ 條邊。

本題用到兩個計數觀念：

• 共用單一頂點的乘法原理：兩個子圖只共用一個頂點，且沒有其他邊相連，整體生成樹數等於兩個子圖生成樹數的乘積。
• Cayley 公式：具有相異頂點標號的完全圖 $K_n$，共有 $n^{n-2}$ 棵生成樹，因此 $K_4$ 有 $4^2=16$ 棵。

解題方法

圖中央是四個頂點形成的環 $C_4$，四個角落各有一個 $K_4$。每個外側 $K_4$ 都以兩條邊連到同一個中央頂點；圖中沒有黑點的線段交叉處不算頂點。

一、計算一個外側區塊的生成樹數

將一個 $K_4$ 的頂點記為 $a,b,c,d$，相鄰的中央頂點記為 $v$，兩條連接邊為 $va,vb$。此區塊共五個頂點，依生成樹中 $v$ 的度數分類。

1. $v$ 的度數為 $1$

   在 $va,vb$ 中選一條，另四個頂點必須形成一棵 $K_4$ 的生成樹，因此共有

   $$2\times16=32$$

   棵。

2. $v$ 的度數為 $2$

   必須同時選取 $va,vb$。為避免形成環，$K_4$ 內選取的邊必須形成恰有兩個連通分量的森林，且 $a,b$ 分屬不同分量。

   在這種森林中加入邊 $ab$，便得到一棵包含 $ab$ 的 $K_4$ 生成樹；反過來，從包含 $ab$ 的生成樹刪去 $ab$，就得到所需森林。因此，只須計算包含固定邊 $ab$ 的生成樹數。

核心觀念

正整數有序對可依照 $x+y$ 的值分層排列：先列出 $x+y=2$ 的有序對，再列 $x+y=3$、$x+y=4$，依此類推。每一層內依 $x$ 由小到大排列。

第 $s$ 層共有 $s-1$ 個有序對。前 $s-2$ 層合計有

$$1+2+\cdots +(s-2)=\frac{(s-2)(s-1)}{2}$$

個有序對，這是三角數。因此，位於第 $s$ 層、且第一個座標為 $x$ 的有序對，其編號為

$$n=\frac{(s-2)(s-1)}{2}+x$$

其中 $s=x+y$。

解題方法

要找映射到 $465$ 的有序對，先判斷 $465$ 落在哪一層。比較相鄰三角數：

$$T_{29}=\frac{29\cdot30}{2}=435$$

核心觀念

要證明方程有整數解，只需找出一個整數，代入原式後使等式成立。若多項式在 $x=a$ 時等於 $0$，則 $a$ 是方程的根；依因式定理，$x-a$ 也是該多項式的因式。

解題方法

令

$$f(x)=x^5-2x^4+x^3-2x^2-7x-1.$$

代入整數 $x=-1$：

核心觀念

使用鴿籠原理。四個頂點若分成三種顏色，至少有兩個頂點同色；因此每一欄都至少有一組「同色的兩列」。把這組資訊記為「列對＋顏色」，再統計所有可能的類型。

解題方法

固定一欄，從四個頂點中任取兩個同色頂點。這樣的同色列對至少存在一組，因為只有三種顏色。

四列共有

$$\binom{4}{2}=6$$

種列對。每一種列對可以搭配三種顏色，因此「列對＋顏色」總共只有

$$6\times 3=18$$

種類型。

核心觀念

本題要證明的命題是「若 $2^N-1$ 是質數，則 $N$ 是質數」。使用逆否證法：若命題形式為「若 $P$，則 $Q$」，它的逆否命題是「若非 $Q$，則非 $P$」。原命題與逆否命題等價。

質數是大於 $1$、且正因數只有 $1$ 和自身的整數。因此，正整數 $N$ 不是質數時，可能是 $N=1$，也可能是大於 $1$ 的合數。

解題方法

證明逆否命題：若 $N$ 不是質數，則 $2^N-1$ 不是質數。

• 若 $N=1$，則

  $$2^N-1=2^1-1=1。$$

  因為 $1$ 不是質數，所以結論成立。

• 若 $N$ 是合數，則可寫成 $N=ab$，其中 $a,b$ 都是大於 $1$ 的正整數。利用平方差以外的一般因式分解公式 $x^b-1=(x-1)(x^{b-1}+x^{b-2}+\cdots+x+1)$，令 $x=2^a$，得到

核心觀念

因為 $\gcd(5,7)=1$，正整數 $5$ 元與 $7$ 元的非負整數組合，從一定門檻起可以表示所有整數。這題的門檻是 $5\cdot7-5-7+1=24$。

解題方法

先列出連續五個整數 $24$ 到 $28$ 的表示方式：

$$\begin{aligned} 24&=5\cdot2+7\cdot2,\\ 25&=5\cdot5+7\cdot0,\\ 26&=5\cdot1+7\cdot3,\\ 27&=5\cdot4+7\cdot1,\\ 28&=5\cdot0+7\cdot4. \end{aligned}$$

核心觀念

每次遞迴把 $N$ 個數分成兩個各有 $N/2$ 個數的子集合。子集合各自找出最大值與最小值後，只需比較兩次：

• 比較 $M_1$ 與 $M_2$，取較大者作為整體最大值。
• 比較 $m_1$ 與 $m_2$，取較小者作為整體最小值。

當集合只剩兩個數時，進行一次比較即可同時找出最大值與最小值。

解題方法

以 $T(N)$ 表示處理 $N$ 個數所需的比較次數。基底情況為：

$$T(2)=1$$

當 $N>2$ 時，兩個大小為 $N/2$ 的子集合各需 $T(N/2)$ 次比較，合併結果再需兩次比較，因此：

$$T(N)=2T\left(\frac{N}{2}\right)+2$$

因為 $N=2^k$，令 $N=2^k$ 並逐層展開遞迴。到達大小為 $2$ 的子集合時，共有 $N/2$ 個，每個各比較一次，合計 $N/2$ 次。其餘合併步驟的比較次數為：

$$2\left(\frac{N}{4}+\frac{N}{8}+\cdots+1\right)$$

括號內是等比級數：

核心觀念

雖然模型含有指數項 $(-2)^x$ 與 $(-1)^{x+1}$，但未知數只有係數 $C,D$，而且它們以線性方式出現。因此，這是線性最小平方法問題。

令每個觀測點的預測值為 $\hat y_i$，最小平方法選擇 $C,D$，使殘差平方和

$$S(C,D)=\sum_{i=1}^{3}(y_i-\hat y_i)^2$$

達到最小。可藉由建立設計矩陣，解正規方程 $A^{\mathsf T}A\begin{bmatrix}C\\D\end{bmatrix}=A^{\mathsf T}\mathbf y$。

解題方法

先代入三個 $x$ 值，將模型改寫成線性方程：

$$\begin{aligned} x=0 &: \quad \hat y=C-D,\\ x=1 &: \quad \hat y=-2C+D,\\ x=2 &: \quad \hat y=4C-D. \end{aligned}$$

因此，設計矩陣與觀測向量為

$$A= \begin{bmatrix} 1&-1\\ -2&1\\ 4&-1 \end{bmatrix}, \qquad \mathbf y= \begin{bmatrix} 0\\4\\6 \end{bmatrix}.$$

計算正規方程所需的矩陣與向量：

核心觀念

Gram–Schmidt 正交化將 $A$ 的欄向量依序改寫成互相正交的向量，並將其標準化，得到薄 QR 分解：

$$A=QR,\qquad Q^TQ=I,$$

其中 $Q$ 的欄向量正交規一，$R$ 為上三角矩陣。對超定系統 $Ax\approx b$，令殘差 $r=b-Ax$。最小平方法要求 $r$ 與 $A$ 的欄空間正交，因此

$$A^Tr=0.$$

代入 $A=QR$，可得 $R x=Q^T b$。本題的 $A$ 欄滿秩，故此方程有唯一解。

解題方法

將 $A$ 的三個欄向量記為

$$a_1=\begin{bmatrix}1\\1\\-1\\0\end{bmatrix},\qquad a_2=\begin{bmatrix}1\\1\\0\\0\end{bmatrix},\qquad a_3=\begin{bmatrix}1\\0\\1\\1\end{bmatrix}.$$

1. Gram–Schmidt 正交化

先取第一個欄向量：

$$u_1=a_1,\qquad \|u_1\|=\sqrt{3},\qquad q_1=\frac{u_1}{\|u_1\|} =\frac{1}{\sqrt{3}}\begin{bmatrix}1\\1\\-1\\0\end{bmatrix}.$$

將 $a_2$ 在 $q_1$ 方向的分量扣除：

$$r_{12}=q_1^Ta_2=\frac{2}{\sqrt{3}},$$ $$u_2=a_2-r_{12}q_1 =\frac{1}{3}\begin{bmatrix}1\\1\\2\\0\end{bmatrix}.$$

由 $\|u_2\|=\frac{\sqrt{6}}{3}$，得到

$$q_2=\frac{u_2}{\|u_2\|} =\frac{1}{\sqrt{6}}\begin{bmatrix}1\\1\\2\\0\end{bmatrix}.$$

接著計算 $a_3$ 在前兩個正交方向上的投影係數：

$$r_{13}=q_1^Ta_3=0,\qquad r_{23}=q_2^Ta_3=\frac{3}{\sqrt{6}}=\frac{\sqrt{6}}{2}.$$

扣除投影後，

$$u_3=a_3-r_{13}q_1-r_{23}q_2 =\frac{1}{2}\begin{bmatrix}1\\-1\\0\\2\end{bmatrix}.$$

因為 $\|u_3\|=\frac{\sqrt{6}}{2}$，所以

$$q_3=\frac{u_3}{\|u_3\|} =\frac{1}{\sqrt{6}}\begin{bmatrix}1\\-1\\0\\2\end{bmatrix}.$$

對角線上的係數為 $r_{jj}=\|u_j\|$，非對角線係數為 $r_{ij}=q_i^Ta_j$。因此

$$Q= \begin{bmatrix} \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{6}} & \frac{1}{\sqrt{6}}\\ \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{6}} & -\frac{1}{\sqrt{6}}\\ -\frac{1}{\sqrt{3}} & \frac{2}{\sqrt{6}} & 0\\ 0 & 0 & \frac{2}{\sqrt{6}} \end{bmatrix}, \qquad R= \begin{bmatrix} \sqrt{3} & \frac{2}{\sqrt{3}} & 0\\ 0 & \frac{\sqrt{6}}{3} & \frac{\sqrt{6}}{2}\\ 0 & 0 & \frac{\sqrt{6}}{2} \end{bmatrix}.$$

核心觀念

矩陣 $A$ 的偽逆記為 $A^+$。若 $A$ 的欄向量線性獨立，則可用

$$A^+=(A^{\mathsf T}A)^{-1}A^{\mathsf T}.$$

本題的 $A$ 為 $3\times 2$ 矩陣；只要兩個欄向量線性獨立，上式即可使用。

解題方法

令 $A$ 的兩個欄向量為

$$\mathbf a_1= \begin{bmatrix} 10\\-11\\-2 \end{bmatrix}, \qquad \mathbf a_2= \begin{bmatrix} 5\\2\\14 \end{bmatrix}.$$

計算內積：

$$\mathbf a_1^{\mathsf T}\mathbf a_1 =10^2+(-11)^2+(-2)^2=225,$$ $$\mathbf a_2^{\mathsf T}\mathbf a_2 =5^2+2^2+14^2=225,$$ $$\mathbf a_1^{\mathsf T}\mathbf a_2 =10(5)+(-11)(2)+(-2)(14)=0.$$

核心觀念

循環矩陣的特徵向量可由單位根組成。對題目給定的循環矩陣，向量若為
$\begin{bmatrix}1&r&r^2&r^3\end{bmatrix}^{T}$，其中 $r^4=1$，其特徵值就是第一列與該向量的內積：

$$\lambda=c_0+c_1r+c_2r^2+c_3r^3.$$

解題方法

第一個特徵向量對應 $r=\mathrm{i}$，且 $\mathrm{i}^4=1$。因此

$$\lambda_0 =c_0+c_1\mathrm{i}+c_2\mathrm{i}^2+c_3\mathrm{i}^3 =c_0+\mathrm{i}c_1-c_2-\mathrm{i}c_3.$$