109 年 國立成功大學電機工程學系碩士班丁組《離散數學》

核心觀念

圖同構是指兩個圖的頂點之間存在一對一對應，而且對應前後的頂點鄰接關係完全相同。圖同構會保留頂點度數，因此可先比較度數序列，再確認候選圖的連接方式是否一致。

解題方法

圖中，$A$ 有一個三角形，三角形的兩個度數為 $3$ 的頂點各接一個端點；$R$ 的左上頂點經曲線連到右中頂點，與左中頂點形成三角形，而左中、右中頂點各接一個端點。$F$ 與 $T$ 都有一個度數為 $3$ 的頂點，並連著一個度數為 $2$ 的頂點；$K$ 與 $X$ 都是中心頂點連接四個端點。

比較各圖度數序列如下，括號內由大到小排列：

度數序列不同的圖不可能同構；度數序列相同時，還要確認鄰接結構一致。

各圖分析與對應

核心觀念

偏序關係須滿足反身性、反對稱性與遞移性。此題的關係由平方值決定大小：平方值較小的元素在下方；平方值相同時，只有元素本身才互相關聯。因此，$-k$ 與 $k$（$k\ne 0$）彼此不可比較。

解題方法

令 $xRy$ 表示 $x^2<y^2$ 或 $x=y$。

• **反身性：**任取 $x\in X$，都有 $x=x$，所以 $xRx$。
• **反對稱性：**若 $xRy$ 且 $yRx$，若 $x\ne y$，則必須同時有 $x^2<y^2$ 與 $y^2<x^2$，矛盾。因此 $x=y$。
• **遞移性：**若 $xRy$ 且 $yRz$，若 $x=y$ 或 $y=z$，可直接得到 $xRz$；若 $x\ne y$ 且 $y\ne z$，則 $x^2<y^2<z^2$，所以 $x^2<z^2$，仍有 $xRz$。

故 $R$ 是 $X$ 上的偏序。

(b) Hasse 圖

按平方值分層，從下到上依序為

觀念分析

1. 迴圈執行次數：
   三層迴圈的指標範圍為 $1 \le k \le j \le i \le 87$。這相當於在 $1$ 到 $87$ 中允許重複挑選 $3$ 個數，總執行次數為重複組合 $C(87+3-1, 3) = C(89, 3) = \frac{89 \times 88 \times 87}{3!} = 113,444$ 次。

2. increment 與 sum 的遞迴關係：
   設第 $m$ 次執行迴圈內區塊時（$1 \le m \le N$，其中 $N = C(89, 3) = 113,444$）：

   • increment 的值為 $a_m = -3m$
   • sum 的值為 $S_N = \sum_{m=1}^{N} a_m = -3 \sum_{m=1}^{N} m = -3 \times \frac{N(N+1)}{2}$

第 4 題詳解

(a) 遞迴關係式推導

設長度為 $n$ 且符合條件（無連續 T 且無連續 G）的 DNA 鏈中：

• 以 A 結尾的字串數為 $a_n$
• 以 C 結尾的字串數為 $c_n$
• 以 G 結尾的字串數為 $g_n$
• 以 T 結尾的字串數為 $t_n$

由對稱性可知：

1. $a_n = c_n = g(n-1)$ （因前一個位置可接 A, C, G, T 任意字元）
2. $g_n = a_{n-1} + c_{n-1} + t_{n-1} = g(n-1) - g_{n-1}$ （因前一個位置不能為 G）
3. $t_n = a_{n-1} + c_{n-1} + g_{n-1} = g(n-1) - t_{n-1}$ （因前一個位置不能為 T）

將以上四式相加，得長度為 $n$ 的總方法數 $g(n)$：
$g(n) = a_n + c_n + g_n + t_n = 2g(n-1) + (g(n-1) - g_{n-1}) + (g(n-1) - t_{n-1})$
$g(n) = 4g(n-1) - (g_{n-1} + t_{n-1})$

又由 $g(n-1) = a_{n-1} + c_{n-1} + g_{n-1} + t_{n-1} = 2g(n-2) + g_{n-1} + t_{n-1}$，可得：
$g_{n-1} + t_{n-1} = g(n-1) - 2g(n-2)$

代回總式：
$g(n) = 4g(n-1) - [g(n-1) - 2g(n-2)] = 3g(n-1) + 2g(n-2)$

初始條件：

• $n = 1$：A, C, G, T 共 4 種，故 $g(1) = 4$。
• $n = 2$：總共 $4^2 = 16$ 種，扣除 GG 與 TT 2 種不合，故 $g(2) = 14$。

(b) 求解遞迴關係式

特徵方程式為：
$x^2 - 3x - 2 = 0$

解得特徵根：
$x = \frac{3 \pm \sqrt{17}}{2}$

核心觀念

本題核心在於考察**鴿籠原理（Pigeonhole Principle，或稱鴿巢原理）與同餘（Modular Arithmetic）**的應用。

1. 同餘與差之倍數定義：若兩整數 $a, b$ 除以 $10$ 的餘數相同，則其差 $a - b$ 為 $10$ 的倍數，記作 $a \equiv b \pmod{10}$。
2. 同餘與和之倍數定義：若兩整數 $a, b$ 除以 $10$ 的餘數分別為 $r_1, r_2$，且滿足 $r_1 + r_2 = 10$ 或 $r_1 + r_2 = 0$，則其和 $a + b$ 為 $10$ 的倍數，記作 $a + b \equiv 0 \pmod{10}$。
3. 鴿籠原理：若將 $n$ 個物品放入 $k$ 個鴿籠中，且 $n > k$，則至少有一個鴿籠包含不少於 $2$ 個物品。

解題方法

步驟一：劃分鴿籠（餘數分類）
任何整數除以 $10$ 的餘數必屬於集合 $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$。
為了使「餘數相同」（兩數之差為 $10$ 的倍數）或「餘數相加為 $10$」（兩數之和為 $10$ 的倍數）必然成立，將這 $10$ 個餘數劃分為 $6$ 個鴿籠（子集合）：

• 鴿籠 $H_0 = \{0\}$
• 鴿籠 $H_5 = \{5\}$
• 鴿籠 $H_1 = \{1, 9\}$（因為 $1 + 9 = 10 \equiv 0 \pmod{10}$）
• 鴿籠 $H_2 = \{2, 8\}$（因為 $2 + 8 = 10 \equiv 0 \pmod{10}$）
• 鴿籠 $H_3 = \{3, 7\}$（因為 $3 + 7 = 10 \equiv 0 \pmod{10}$）
• 鴿籠 $H_4 = \{4, 6\}$（因為 $4 + 6 = 10 \equiv 0 \pmod{10}$）

鴿籠總數為 $k = 6$。

步驟二：套用鴿籠原理
設給定的 $7$ 個相異整數為 $a_1, a_2, \dots, a_7$，其除以 $10$ 的餘數分別為 $r_1, r_2, \dots, r_7$（物品數 $n = 7$）。
由於物品數 $n = 7$ 大於鴿籠數 $k = 6$，根據鴿籠原理，必定存在至少兩個數字 $a_i$ 與 $a_j$（$i \neq j$）對應的餘數屬於同一個鴿籠。

步驟三：分情況討論證明
假設 $a_i, a_j$ 的餘數 $r_i, r_j$ 落入同一鴿籠：

1. 若落入 $H_0 = \{0\}$：則 $r_i = r_j = 0$，可得 $a_i - a_j \equiv 0 - 0 = 0 \pmod{10}$，即兩數之差為 $10$ 的倍數。
2. 若落入 $H_5 = \{5\}$：則 $r_i = r_j = 5$，可得 $a_i - a_j \equiv 5 - 5 = 0 \pmod{10}$，即兩數之差為 $10$ 的倍數。
3. 若落入 $H_m = \{m, 10-m\}$（其中 $m \in \{1, 2, 3, 4\}$）：

在演算法效率分析中，雖然 Big-O（$\mathcal{O}$）、Big-$\Theta$、Big-$\Omega$ 各有其數學定義，但實際應用與文獻中最常使用 Big-O notation，主因如下：

核心原因解析

1. 提供最壞情況的上界保障（Upper Bound Security）

   • Big-O 代表演算法執行時間或空間特性的漸近上界（Asymptotic Upper Bound）。
   • 在工程與實際應用中，系統開發者最關心的是「最壞情況（Worst-case）」的效能上限，以確保程式在任何輸入下均不會超過可接受的時間與資源極限。

2. 資訊取得的現實可行性（Practical Feasibility）

   • 求出嚴格的漸近緊確界（Tightly Bounded）Big-$\Theta$ 往往需要精確掌握演算法的上界與下界，在許多複雜演算

本題考查組合計數中的取斥原理（Inclusion-Exclusion Principle）。

題目條件整理

各年級人數如下：

• 大一（Freshmen, $F$）：3 人
• 大二（Sophomores, $O$）：4 人
• 大三（Juniors, $J$）：4 人
• 大四（Seniors, $S$）：5 人

總人數 $N = 3 + 4 + 4 + 5 = 16$ 人。
欲選出 8 人委員會，且每個年級至少有 1 人。

求解步驟

1. 任意選出 8 人的總組合數

$|U| = \binom{16}{8} = 12870$

2. 定義排斥集合與計算取斥原理

令 $P_F, P_O, P_J, P_S$ 分別表示「未包含大一」、「未包含大二」、「未包含大三」、「未包含大四」的選法集合。
所求為都不缺少任何年級的組合數：
$N_{valid} = |U| - \sum |P_i| + \sum |P_i \cap P_j| - \sum |P_i \cap P_j \cap P_k| + |P_F \cap P_O \cap P_J \cap P_S|$

• 扣除缺少 1 個年級的情形（$\sum |P_i|$）：
  • 缺 $F$（從 13 人選 8 人）：$\binom{13}{8} = 1287$