109 年 國立中山大學電機工程學系碩士班丙組《離散數學》

核心觀念

本題考查計算機科學與離散數學中**計算複雜度理論（Computational Complexity Theory）**的幾項核心定義與性質：

1. $\text{P}$ 與 $\text{NP}$ 類別定義：
   • $\text{P}$ 類別：能在多項式時間內被確定型圖靈機（Deterministic Turing Machine）求解的決策問題集合。
   • $\text{NP}$ 類別：其候選解可以在多項式時間內被確定型圖靈機**驗證（Verify）**的決策問題集合（亦即可在多項式時間內被非確定型圖靈機求解）。
2. 多項式時間歸約（Polynomial-time Reduction, $\le_p$）：
   • 若問題 $A$ 可在多項式時間內歸約至問題 $B$（記作 $A \le_p B$），代表 $B$ 的複雜度不低於 $A$（$B$ 至少與 $A$ 一樣難）。
3. NP-Hard 與 NP-Complete 定義：
   • NP-Hard：若對所有 $L \in \text{NP}$ 均滿足 $L \le_p B$，則稱 $B$ 為 NP-Hard 問題（不要求 $B \in \text{NP}$）。
   • NP-Complete（NPC）：若一個問題 $B$ 同時滿足以下兩個條件：
     1. $B \in \text{NP}$
     2. $B \in \text{NP-Hard}$（即所有 NP 問題皆可在多項式時間歸約至 $B$）
        則稱 $B$ 為 NP-Complete 問題。

解題方法

針對是非題的每一個命題，採用嚴謹數學定義檢驗與**反例構造法（Counterexample Construction）**進行分析：

• 1.1：將決策問題抽象化為語言集合 $A, B \subseteq \Sigma^*$，利用特例語言（如全集 $\Sigma^*$）構造反例驗證交集 $A \cap B$ 是否仍可為 NP-Complete。
• 1.2：利用 NP-Complete 的雙重充分必要條件（$B \in \text{NP}$ 且 $B \in \text{NP-Hard}$），檢驗歸約關係 $A \le_p B$ 能否推導出 $B \in \text{NP-Complete}$。
• 1.3：直接對照 $\text{NP}$ 類別的標準定義。
• 1.4：對照 NP-Complete 的定義，分析「是否已知演算法」與「相互歸約」是否符合定義。

選項分析

1.1 True(O) or False(X): Assume that A and B are problems. If A is an NP one and B is in P, A $\cap$ B is not NP-complete.

• 判斷：False (X)

• 詳解：
  在形式語言與複雜度理論中，決策問題表示為語言集合 $A, B \subseteq \Sigma^*$。兩問題的交集 $A \cap B$ 代表必須同時滿足問題 $A$ 與問題 $B$ 條件的輸入字串集合。
  構造以下反例：

  • 令 $A$ 為任意已知的 NP-Complete 問題（例如 3-SAT），顯然 $A \in \text{NP}$。
  • 令 $B = \Sigma^*$（即包含所有字串的語言，對任何輸入皆恆真，屬於平凡問題），顯然 $B \in \text{P}$。

  此時，$A \cap B = 3\text{-SAT} \cap \Sigma^* = 3\text{-SAT}$。
  因為 3-SAT 本身即為 NP-Complete 問題，故交集 $A \cap B$ 依然是 NP-Complete 問題。原命題宣稱「$A \cap B$ 一定不是 NP-Complete」，與此反例矛盾，故為錯誤。

1.2 True(O) or False(X): If A is in NP-complete and A can be solved in polynomial time less than B, B belongs to NP-complete.

• 判斷：False (X)
• 詳解：
  敘述「$A$ 可在少於 $B$ 的多項式時間內被解決」代表存在多項式時間歸約關係 $A \le_p B$（即 $A$ 的難度不大於 $B$）。

核心觀念

本題旨在考驗漸進符號（Big-$O$ Notation）的定義與級數和的數量級放縮（Bounding Sums）。

1. 大 $O$ 漸進符號定義：
   設 $f(N)$ 與 $g(N)$ 為非負函數。若存在正實數常數 $c$ 與正整數 $N_0$，使得對所有 $N \ge N_0$，皆滿足 $f(N) \le c \cdot g(N)$，則記作 $f(N) = O(g(N))$。
2. 級數和的漸進數量級：
   對於連續 $M$ 次方和 $S_M(N) = \sum_{k=1}^N k^M = 1^M + 2^M + \dots + N^M$，評估其漸進上界主要採用放大法（Bounding Method）或定積分夾擠法（Integral Test for Bounding Sums）。
3. 浮爾哈伯公式（Faulhaber's Formula）：
   $S_M(N) = \sum_{k=1}^N k^M = \frac{1}{M+1} N^{M+1} + \frac{1}{2} N^M + \sum_{j=2}^M \frac{B_j}{j!} \frac{M!}{(M-j+1)!} N^{M-j+1}$（其中 $B_j$ 為白努利數）。由此展開式可知，該多項式的最高次項數為 $N^{M+1}$。

解題方法

步驟一：求取漸進上界（Upper Bound）

在級數 $1^M + 2^M + \dots + N^M$ 中，由於 $N$ 與 $M$ 皆為正整數，且對所有 $1 \le k \le N$，均有 $k^M \le N^M$。
將級數中的每一項皆放大替換為最大項 $N^M$：
$1^M + 2^M + \dots + N^M \le N^M + N^M + \dots + N^M = N \cdot N^M = N^{M+1}$

選取常數 $c = 1$ 與 $N_0 = 1$，對所有 $N \ge 1$，均符合：
$\sum_{k=1}^N k^M \le 1 \cdot N^{M+1}$
根據 Big-$O$ 之定義，可直接推得：
$1^M + 2^M + \dots + N^M = O(N^{M+1})$

步驟二：證明上界之緊密性（Tightness Proof）

為確保 $L = N^{M+1}$ 為最緊密的漸進數量級（Tight Bound），需導出其漸進下界 $\Omega(N^{M+1})$。
只保留級數後半段（即 $k \ge \lceil N/2 \rceil$ 的項）：
$\sum_{k=1}^N k^M \ge \sum_{k=\lceil N/2 \rceil}^N k^M \ge \left( N - \left\lceil \frac{N}{2} \right\rceil + 1 \right) \cdot \left( \frac{N}{2} \right)^M \ge \frac{N}{2} \cdot \frac{N^M}{2^M} = \frac{1}{2^{M+1}} N^{M+1}$

選取常數 $c' = \frac{1}{2^{M+1}} > 0$，可得 $\sum_{k=1}^N k^M = \Omega(N^{M+1})$。
結合上下界可知：
$\sum_{k=1}^N k^M = \Theta(N^{M+1})$
故符合 $1^M + 2^M + \dots + N^M = O(L)$ 的最緊密函數為 $L = N^{M+1}$。

步驟三：定積分夾擠法驗證（積分解法）

因 $f(x) = x^M$ 為單調遞增函數，利用矩形面積與定積分關係夾擠：

核心觀念

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

計算生成樹數可使用矩陣樹定理：將圖的拉普拉斯矩陣刪去同一頂點對應的列與行，所得餘子式的行列式就是生成樹總數。

解題方法

依原卷 Fig. 1，六個頂點排成兩列三行，外圍構成一個六邊形，另有中間邊 $(V_2,V_5)$。邊集合為
$\{(V_1,V_2),(V_2,V_3),(V_3,V_4),(V_4,V_5),(V_5,V_6),(V_6,V_1),(V_2,V_5)\}$；
其中 $V_2$ 與 $V_1,V_3,V_5$ 相鄰，度數為 $3$。

3.1 $K_3$

設三個頂點為 $a,b,c$，邊為 $ab,ac,bc$。生成樹需含兩條邊，因此從三條邊中各刪去一條，得到全部三棵生成樹：

3.2 $K_{2,2}$

設二分部為 $\{a_1,a_2\}$ 與 $\{b_1,b_2\}$，四條邊為 $a_1b_1,a_1b_2,a_2b_1,a_2b_2$。$K_{2,2}$ 是一個四邊形，生成樹由刪去其中一條邊得到，全部四棵為：

3.3 圖中生成樹總數

依各頂點的度數及相鄰關係，按 $V_1,V_2,V_3,V_4,V_5,V_6$ 排列，拉普拉斯矩陣為

核心觀念

Dijkstra 演算法每次選取暫定距離最小的頂點，並用「目前距離加上邊權」更新相鄰頂點的距離。演算法要求所有邊權非負；無箭頭的邊視為無向邊。

解題方法

圖中可辨識的相關邊權為 $w(V1,V2)=2$、$w(V1,V3)=1$、$w(V1,V4)=4$、$w(V2,V3)=2$、$w(V3,V4)=2$、$w(V3,V5)=5$、$w(V3,V6)=7$、$w(V5,V7)=1$、$w(V6,V7)=3$。圖上 $V2$–$V5$ 與 $V4$–$V6$ 兩條邊未標出可辨識的權重；令它們分別為非負數 $x$ 與 $y$。

起點設為 $V1$，初始距離為 $d(V1)=0$，其他頂點距離為 $\infty$。處理 $V1$ 後：

接著選取距離最小的 $V3$，其距離為 $1$。經由 $V3$ 更新：

$V2$ 的距離為 $2$，處理 $V2$ 後，$V5$ 的距離更新為：

經由 $V4$ 前往 $V6$，可得：

核心觀念

本題屬於組合數學（Combinatorics）中「相異物件分組與分配（Set Partitions and Distribution）」的典型經典考題，重點考驗以下核心定義與定理：

1. 組合數（Combinations）與乘法原理（Rule of Product）：
   從 $n$ 個相異物件中任選 $k$ 個物件的分法數表示為：
   $\binom{n}{k} = C_k^n = \frac{n!}{k!(n-k)!}$
   當一個任務可拆解為多個連續獨立的階段完成時，完成該任務的總方法數等於各階段方法數之連乘積。

2. 多項式係數（Multinomial Coefficients）：
   將 $n$ 個相異物件分割入 $k$ 個指定組別，且各組人數分別指定為 $n_1, n_2, \dots, n_k$（滿足 $\sum_{i=1}^k n_i = n$）的方法數為：
   $\binom{n}{n_1, n_2, \dots, n_k} = \frac{n!}{n_1! n_2! \cdots n_k!}$

3. 可區分組（Labeled / Specific Groups）與不可區分組（Unlabeled Groups）：

   • 可區分組：若組別擁有特定名稱或標籤（如本題之 $G_1, G_2, G_3$），分配順序與組別名稱具備區別性，計算時不需除以組數階乘。
   • 不可區分組：若組別完全無名稱標籤（僅將人員分為三堆，每堆 4 人），同人數組別之間無順序差異，則計算時必須除以同人數組數之階乘 $m!$。

解題方法

題目要求將 $12$ 名學生分成三組指定名稱的組別（$G_1, G_2, G_3$），且每組人數皆為 $4$ 人。以下提供兩種標準且嚴謹的推導方式：

方法一：分階段組合選擇法（乘法原理推導）

將整體分組作業拆解為三個連續動作：

1. 選定 $G_1$ 組員：從 $12$ 名學生中挑選 $4$ 人加入 $G_1$ 組，組合數為：
   $\binom{12}{4} = \frac{12 \times 11 \times 10 \times 9}{4 \times 3 \times 2 \times 1} = 495$
2. 選定 $G_2$ 組員：從剩餘的 $8$ 名學生中挑選 $4$ 人加入 $G_2$ 組，組合數為：
   $\binom{8}{4} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 70$
3. 選定 $G_3$ 組員：最後剩餘的 $4$ 名學生直接全部編入 $G_3$ 組，組合數為：
   $\binom{4}{4} = 1$

依據乘法原理，總分法數為三個階段方法數之乘積：
$\text{總分法數} = \binom{12}{4} \times \binom{8}{4} \times \binom{4}{4} = 495 \times 70 \times 1 = 34,650$

方法二：多項式係數法（直接公式展算）

由於三組皆有明確標籤（$G_1, G_2, G_3$），此問題完全等價於將 $12$ 個相異元素分割為規模分別為 $4, 4, 4$ 的三個特定區域，可直接套用多項式係數公式：
$\binom{12}{4, 4, 4} = \frac{12!}{4! \cdot 4! \cdot 4!}$