113 年 國立中正大學資訊工程學系碩士班乙組《數學》

核心觀念

本題考三重純量積與向量三重積。三重純量積可寫成行列式：

交換兩個向量會改變符號；向量三重積則使用公式：

由於三重純量積為 $-4\ne 0$，$\mathbf{u},\mathbf{v},\mathbf{w}$ 線性獨立。

解題方法

先用三重純量積的交換符號性質判斷 (A)，再用向量三重積公式化簡 (C)、(D)。對 (E)，需判斷題目給定條件是否足以保證兩個向量相等；可比較公式，並用符合已知條件的例子檢驗。

選項分析

(A) 錯誤。
交換三重純量積中的前兩個向量，結果變號：

因此不等於 $-4$。

(B) 正確。
任意向量與自身的外積為零，所以：

(C) 正確。
利用向量三重積公式：

核心觀念

子空間是向量空間的子集合，必須包含零向量，且對向量加法與純量乘法封閉。若集合中的向量可寫成若干向量的線性組合，也可直接判定它是子空間。

解題方法

逐一檢查各選項的限制式是否為齊次線性條件，或是否能寫成向量的線性組合。非齊次條件常會使零向量不在集合內；齊次線性條件則可確保集合包含零向量，並對加法與純量乘法封閉。

選項分析

(A) 正確。
集合中的向量可寫成

因此此集合是由 $(1,0,0)$ 張成的子空間，也就是 $\mathbb{R}^3$ 中的 $x$ 軸。

(B) 錯誤。
每個向量的第二個分量固定為 $1$，所以零向量 $(0,0,0)$ 不在此集合中。未包含零向量的集合不是子空間。

核心觀念

向量 $\mathbf{u}$ 為 $5\times 1$，$\mathbf{v}^{T}$ 為 $1\times 5$，所以外積 $\mathbf{u}\mathbf{v}^{T}$ 是 $5\times 5$ 矩陣。其第 $j$ 欄等於 $v_j\mathbf{u}$，因此每一欄都是 $\mathbf{u}$ 的倍數。

矩陣的秩是其欄向量所張成空間的維度。當 $\mathbf{u}$、$\mathbf{v}$ 都不為零向量時，$\mathbf{u}\mathbf{v}^{T}$ 的所有欄都落在 $\mathbf{u}$ 張成的一維空間中，且至少有一欄非零，因此秩為 $1$。

解題方法

本題的兩個向量都不是零向量。逐欄觀察外積：

核心觀念

若矩陣 $A$ 的特徵值為 $\lambda$，則 $A^7$ 的特徵值為 $\lambda^7$。這是矩陣特徵值的冪次性質：若 $Av=\lambda v$，則

此外，三角矩陣的特徵值就是其對角線上的元素。

解題方法

題目中的 $A$ 是下三角矩陣，因此其特徵值為對角線元素：

將各特徵值取七次方，即得 $A^7$ 的特徵值：

核心觀念

內積所定義的長度為 $\|\mathbf{u}\|=\sqrt{\mathbf{u}\cdot\mathbf{u}}$。因此，這個內積下的單位圓是所有滿足 $\mathbf{u}\cdot\mathbf{u}=1$ 的向量所構成的集合。

解題方法

令 $\mathbf{u}=(u_1,u_2)$，代入題目給定的內積：

令其等於 $1$，得到單位圓的方程式：

這是以原點為中心的橢圓。與標準式 $\frac{x^2}{a^2}+\frac{y^2}{b^2}=1$ 比較，可知沿 $u_1$ 軸的半短軸長度為 $2$，沿 $u_2$ 軸的半長軸長度為 $4$。因此橢圓在 $u_1$ 軸的截點為 $(\pm2,0)$，在 $u_2$ 軸的截點為 $(0,\pm4)$，形狀沿 $u_2$ 軸較長。

也可用參數式表示：

示意圖如下，縱軸方向較長：

核心觀念

本題考查將英文敘述轉換成謂詞邏輯。「沒有任何喜劇得獎」表示：對每一部電影，若它是喜劇，就沒有得獎。題目中 $C(y)$ 表示 $y$ 是喜劇，$A(y)$ 表示 $y$ 得獎。

解題方法

$y$ 的論域是所有電影，因此使用全稱量詞 $\forall y$。英文中的「若是喜劇，就沒有得獎」可寫成條件命題 $C(y)\to\neg A(y)$，所以：

核心觀念

本題考查將自然語言敘述轉換為一階邏輯式。$S(x,y)$ 表示人物 $x$ 看過電影 $y$，$L(x,y)$ 表示人物 $x$ 喜歡電影 $y$。「沒喜歡」須以否定符號 $\neg$ 表示；「但」連接兩個同時成立的敘述，因此使用合取符號 $\land$。

解題方法

以 Lois 代入人物變數 $x$，以 Casablanca 代入電影變數 $y$。「Lois 看過 Casablanca」寫成 $S(\text{Lois},\text{Casablanca})$；

核心觀念

本題考一階述詞邏輯的量詞順序與條件句翻譯：

• 「有些人」表示存在量詞 $\exists x$。
• 「每一部喜劇」表示全稱量詞 $\forall y$，並以 $C(y)$ 限定電影是喜劇。
• 「看過」以述詞 $S(x,y)$ 表示。

解題方法

先翻譯「有些人」，因此先寫 $\exists x$。接著描述這個人看過每一部喜劇：對所有電影 $y$，若 $y$ 是喜劇，則此人看過 $y$。所以全稱量詞範圍內使用條件句 $C(y)\to S(x,y)$。

核心觀念

題目考查含有「每一個」與「沒有人」的述詞邏輯翻譯。由於「沒有人」表示不存在這樣的人，可用存在量詞的否定表示；「喜歡他看過的每一部電影」則要用條件句表達：對每部電影，只要他看過，就表示他喜歡。

解題方法

「某人喜歡他看過的每一部電影」可寫成：

題目說「沒有人」符合這項條件，因此將整句否定：

使用量詞否定律與德摩根律，可得等價形式：

核心觀念

本題考查將英文敘述翻譯成述詞邏輯。「Ben has never seen a movie that won an award」表示：對每一部電影，只要它得過獎，Ben 就沒有看過它。

其中 $A(y)$ 表示「電影 $y$ 得過獎」，$S(x,y)$ 表示「人物 $x$ 看過電影 $y$」。Ben 是人物，因此代入 $S$ 的第一個位置。

解題方法

以 $y$ 遍歷所有電影。對任一部電影 $y$，若 $y$ 得過獎，則 Ben 沒有看過 $y$：

核心觀念

圖中的 $T$-omino 由 $4$ 個單位方格組成：一排 $3$ 格，並在中間那格下方接 $1$ 格。拼放時可旋轉圖形。證明的關鍵是先展示一個 $4\times4$ 方格的拼法，再把較大的棋盤分割成 $4\times4$ 方塊。

解題方法

原圖中的 $T$-omino 是上方橫排 $3$ 格、中央格下方接 $1$ 格。以下用字母標示同一塊拼片；每個字母恰好出現 $4$ 次：

其中 $A$、$D$ 是橫放的 $T$-omino，$B$、$C$ 是旋轉後的 $T$-omino。

核心觀念

平面圖是指能畫在平面上，使任意兩條邊只在共同端點相交的圖。原圖畫法有交叉，並不足以證明它是非平面圖；必須證明無論如何重畫，都無法消除交叉。

依 Kuratowski 定理，若圖中含有 $K_5$ 或 $K_{3,3}$ 的細分子圖，則此圖為非平面圖。「細分」是將一條邊改成一條路徑，在邊上插入度數為 $2$ 的頂點。

解題方法

原圖共有 $8$ 個頂點、$18$ 條邊，其中中央的 $c-f$ 也是一條邊；$c-f$ 與 $d-e$ 的交叉處沒有標示頂點，因此不視為連接點。以下找出圖中的 $K_{3,3}$ 細分子圖。

取兩組分支頂點：

$K_{3,3}$ 要求兩組之間的每一對頂點都有連線。本圖可用下列九條路徑實現：

核心觀念

樹是連通且沒有環的圖。樹的基本性質是：若有 $n$ 個頂點，邊數必為 $n-1$。

解題方法

題目給定 $T$ 是有 $999$ 個頂點的樹，套用樹的邊數公式：

核心觀念

根樹是指定一個頂點為根的樹。兩棵根樹同構，必須存在保留相鄰關係且把根映到根的頂點對應；子樹的排列順序不影響同構。因此可依根的子樹大小分類。

解題方法

四個頂點中，根的每個子樹至少含一個頂點。按照根的子樹頂點數分組：

• 根只有一個子樹：該子樹有三個頂點。三頂點根樹有兩種，分別是根到兩個頂點依序相連的鏈，以及根直接連到兩個葉節點。合併根後得到兩種四頂點根樹。
• 根有兩個子樹：子樹大小只能是 $1$ 與 $2$。

核心觀念

前置表示法（prefix notation）將運算子寫在其運算元之前。二元運算的格式為「運算子、左運算元、右運算元」，例如 $a+b$ 寫成 $+\,a\,b$。

解題方法

原式 $3n-(k+5)$ 的最外層運算是減法，左運算元為乘積 $3n$，右運算元為和 $k+5$。

核心觀念

生成樹是包含圖中所有頂點，且連通、沒有環的子圖。對有 $n$ 個頂點的連通圖，生成樹恰有 $n-1$ 條邊。

環圖 $C_7$ 有 7 個頂點和 7 條邊。從環上刪除任意一條邊，剩下的圖仍連通，且不再有環，因此是一棵生成樹。

解題方法

核心觀念

$Q_4$ 是四維超立方體，每個頂點可用 4 位元的 $0$、$1$ 組合表示，因此共有 $2^4=16$ 個頂點。最小生成樹是連接圖中所有頂點的樹；含有 $V$ 個頂點的樹恰有 $V-1$ 條邊。

解題方法

核心觀念

滿二元樹（full binary tree）中，每個節點都有 $0$ 個或 $2$ 個子節點。若樹高以「根節點到最深葉節點的邊數」計算，樹高為 $h$ 的二元樹最多有

個節點。

解題方法

要容納 $101$ 個節點，樹高 $h$ 必須滿足

因此

而 $2^6=64<102\le128=2^7$，所以 $h+1\ge7$，即 $h\ge6$。

核心觀念

滿二元樹（full binary tree）中，每個內部頂點恰有 $2$ 個子頂點。若葉頂點數為 $L$，內部頂點數為 $I$，則總頂點數為 $I+L$。

解題方法

每個內部頂點都連出 $2$ 條通往子頂點的邊，因此邊數為 $2I$。另一方面，任何有 $I+L$ 個頂點的樹，邊數皆為頂點數減 $1$，所以

核心觀念

圖的關聯矩陣以「頂點」對應列、以「邊」對應行（欄）。因此，矩陣的列數等於頂點數，欄數等於邊數；若使用有向關聯矩陣，矩陣尺寸也相同。

解題方法

採用常見定義：輪形圖 $W_n$ 由一個 $n$ 邊形 $C_n$ 加上一個中心頂點組成，中心頂點連接到 $C_n$ 的每個頂點。

因此，$W_n$ 有 $n+1$ 個頂點。邊分成兩類：

核心觀念

若圖是連通的，且每個頂點的度數都是偶數，則圖有 Euler circuit（尤拉迴路）：一條從同一頂點出發並回到該頂點，且每條邊恰好經過一次的封閉路徑。

解題方法

在完全圖 $K_n$ 中，每個頂點都與其餘 $n-1$ 個頂點相鄰，因此每個頂點的度數為

$K_n$ 是連通圖；要有 Euler circuit，所有頂點的度數都必須是偶數。因此

核心觀念

二分圖的每條邊都連接兩個不同部份的頂點，所以沿著路徑或迴路行走時，頂點必須在兩部份之間交替。Hamilton 路徑須恰好經過每個頂點一次；Hamilton 迴路則須恰好經過每個頂點一次，並回到起點。

解題方法

設 $K_{m,n}$ 的兩部份分別有 $m$ 個與 $n$ 個頂點。

若存在 Hamilton 路徑，路徑上的頂點會交替來自兩部份。因此兩部份的頂點數最多相差 $1$，也就是

反過來，若 $|m-n|\leq 1$，可將兩部份頂點交替排列；因為 $K_{m,n}$ 中兩部份間的每一對頂點都有邊相連，這個排列便形成 Hamilton 路徑。因此，$K_{m,n}$ 有 Hamilton 路徑的充要條件是 $|m-n|\leq 1$。

若存在 Hamilton 迴路，沿迴路交替經過兩部份的頂點，兩部份的頂點數必須相等。當 $m=n\geq 2$ 時，可將頂點交替排列並首尾相接，形成 Hamilton 迴路。