108 年 國立成功大學工程科學系碩士班乙組《計算機概論》

核心觀念

設函數集合為

$$\mathcal{F}=\{f\mid f:\mathbb{Z}\to\mathbb{Z}\}.$$

關係 $R$ 是等價關係，必須同時滿足：

1. 自反性：對所有 $f\in\mathcal{F}$，皆有 $fRf$。
2. 對稱性：若 $fRg$，則必有 $gRf$。
3. 遞移性：若 $fRg$ 且 $gRh$，則必有 $fRh$。

判斷此題時，只要分別檢查這三項即可。若要證明不具某項性質，只需找出一組反例。

---

選項分析

(a) $\{(f,g)\mid f(1)=g(1)\}$

此關係表示兩函數在 $x=1$ 的函數值相同。

自反性

對任意函數 $f$，必然有

$$f(1)=f(1),$$

因此 $fRf$，具備自反性。

對稱性

若 $fRg$，則

$$f(1)=g(1).$$

等式具有對稱性，因此

$$g(1)=f(1),$$

故 $gRf$，具備對稱性。

遞移性

若 $fRg$ 且 $gRh$，則

$$f(1)=g(1),\qquad g(1)=h(1).$$

由等式的遞移性可得

$$f(1)=h(1),$$

所以 $fRh$，具備遞移性。

因此，(a) 是等價關係。

---

(b) $\{(f,g)\mid f(0)=g(1)\text{ 且 }f(1)=g(0)\}$

此關係表示 $f$ 與 $g$ 在 $0$、$1$ 的函數值互相交換。

自反性

若要具備自反性，對所有 $f$ 必須有

$$f(0)=f(1).$$

但取函數 $f(x)=x$，則

$$f(0)=0,\qquad f(1)=1,$$

不滿足 $f(0)=f(1)$。因此此關係不具自反性。

對稱性

若 $fRg$，則

$$f(0)=g(1),\qquad f(1)=g(0).$$

將等式左右對調，可得

$$g(1)=f(0),\qquad g(0)=f(1),$$

也就是

$$g(0)=f(1),\qquad g(1)=f(0).$$

因此 $gRf$，具備對稱性。

遞移性

令三個函數在 $0,1$ 的函數值如下：

$$(f(0),f(1))=(0,1),$$ $$(g(0),g(1))=(1,0),$$ $$(h(0),h(1))=(0,1).$$

則

$$f(0)=0=g(1),\qquad f(1)=1=g(0),$$

所以 $fRg$；同理，

$$g(0)=1=h(1),\qquad g(1)=0=h(0),$$

所以 $gRh。

但

$$f(0)=0\ne h(1)=1,$$

故 $f\not Rh$。因此此關係不具遞移性。

所以，(b) 具對稱性，但缺乏自反性與遞移性。

---

(c) $\{(f,g)\mid f(x)-g(x)=1\text{，對所有 }x\in\mathbb{Z}\}$

此關係要求兩函數在每一個整數點的函數值都相差 $1$。

自反性

若 $fRf$，則必須有

$$f(x)-f(x)=1.$$

但實際上

$$f(x)-f(x)=0\ne 1.$$

因此不具自反性。

對稱性

若 $fRg$，則

$$f(x)-g(x)=1.$$

交換 $f,g$ 後得到

$$g(x)-f(x)=-1\ne 1.$$

因此 $g\not Rf$，不具對稱性。

遞移性

若 $fRg$ 且 $gRh

本題考驗對數學歸納法第二原理（又稱強歸納法）的理解與應用。

核心觀念： 數學歸納法第二原理，質數的定義與性質。

(a) 數學歸納法第二原理 (The Second Principle of Mathematical Induction)

數學歸納法第二原理（或稱強歸納法）如下：
假設 $P(n)$ 是一個關於正整數 $n$ 的敘述。若滿足以下兩個條件：

1. 基本情況 (Base Case)： $P(1)$ 為真。
2. 歸納步驟 (Inductive Step)： 對於任意整數 $k \ge 1$，如果 $P(1), P(2), \dots, P(k)$ 都為真，則 $P(k+1)$ 也為真。

則對於所有大於等於 1 的正整數 $n$，敘述 $P(n)$ 都為真。

說明：
與標準的數學歸納法（第一原理）僅假設 $P(k)$ 為真來證明 $P(k+1)$ 為真不同，第二原理允許我們假設從 $P(1)$ 到 $P(k)$ 的所有敘述都為真，這提供了更強的假設，使得在證明某些性質時更加方便。

(b) 證明大於 1 的整數皆可寫為質數的乘積

我們需要證明：對於任意整數 $n > 1$， $n$ 可以被寫成質數的乘積。
我們將使用數學歸納法第二原理來證明此敘述。

設 $P(n)$ 為敘述：「整數 $n$ 可以被寫成質數的乘積」。

1. 基本情況 (Base Case)：
   考慮最小的大於 1 的整數，即 $n=2$。
   $n=2$ 本身就是一個質數，因此它可以被寫成質數的乘積（一個質數的乘積）。所以 $P(2)$ 為真。

2. 歸納步驟 (Inductive Step)：
   假設對於所有滿足 $1 < k < n$ 的整數 $k$，敘述 $P(k)$ 都為真。也就是說，假設所有大於 1 且小於 $n$ 的整數都可以寫成質數的乘積。
   我們需要證明 $P(n)$ 也為真，即證明整數 $n$ 可以被寫成質數的乘積。

核心觀念

設 $a_n$ 表示長度為 $n$ 的三元字串數量，其中每個字元只能是 $0$、$1$、$2$，且不含有連續的兩個 $0$，也就是不出現子字串 $00$。

本題使用「依最後一個字元分類」的遞迴計數法，將長度為 $n$ 的合法字串分成兩類：

1. 最後一個字元是 $1$ 或 $2$。
2. 最後一個字元是 $0$。

解題方法

（a）建立遞迴關係

情況一：最後一個字元是 $1$ 或 $2$

前面的 $n-1$ 個字元只要是合法字串即可，共有 $a_{n-1}$ 種。

最後一個字元有 $2$ 種選擇，因此此類共有

$$2a_{n-1}$$

種。

情況二：最後一個字元是 $0$

為避免出現 $00$，倒數第二個字元必須是 $1$ 或 $2$。

前面的 $n-2$ 個字元形成任意合法字串，共有 $a_{n-2}$ 種；倒數第二個字元有 $2$ 種選擇。因此此類共有

$$2a_{n-2}$$

種。

合併兩種情況，得到

$$a_n=2a_{n-1}+2a_{n-2},\qquad n\ge 2.$$

（b）初始條件

長度為 $0$ 的空字串視為一種合法字串，因此

$$a_0=1.$$

長度為 $1$ 時，字串可以是 $0$、$1$ 或 $2$，三者皆合法，因此

$$a_1=3.$$

所以初始條件為

$$\boxed{a_0=1,\qquad a_1=3}.$$

若從長度 $2$ 開始使用遞迴式，也可先計算

本題考驗鴿籠原理（Pigeonhole Principle）的應用。

核心觀念： 鴿籠原理，反證法。

(a) 證明從前八個正整數中選五個，必有一對和為 9

我們考慮前八個正整數：$\{1, 2, 3, 4, 5, 6, 7, 8\}$。
我們要找出所有和為 9 的整數對：
$(1, 8)$
$(2, 7)$
$(3, 6)$
$(4, 5)$

我們可以將這八個數字分成四對，每一對的和都為 9。這四對是：
$\{1, 8\}, \{2, 7\}, \{3, 6\}, \{4, 5\}$

現在，我們從這八個數字中選取五個數字。將這五個數字視為「鴿子」，而上述四個數字對視為「鴿籠」。
根據鴿籠原理，如果我們有 $N$ 個鴿子要放入 $K$ 個鴿籠，且 $N > K$，則至少有一個鴿籠中至少有 $\lceil N/K \rceil$ 個鴿子。

在這裡，我們選了 5 個數字（鴿子），而這 5 個數字來自 4 個對（鴿籠）。
由於 $5 > 4$，根據鴿籠原理，至少有一個對（鴿籠）會包含至少 $\lceil 5/4 \rceil = 2$ 個數字。
如果一個對（例如 $\{1, 8\}$）包含了兩個數字，這意味著我們選取的這兩個數字就是 1 和 8。它們的和是 $1+8=9$。
因此，如果我們從 $\{1, 2, 3, 4, 5, 6, 7, 8\}$ 中選取五個數字，必有一對數字的和為 9。

另一種表述方式（更直接）：
我們將這八個數字分成四組，每組包含兩個數字，且每組內任意兩個數字相加都等於 9：
組 1: $\{1, 8\}$
組 2: $\{2, 7\}$
組 3: $\{3, 6\}$
組 4: $\{4, 5\}$

本題考驗圖論中遞移閉包（Transitive Closure）的計算，以及利用矩陣運算來實現。

核心觀念： 遞移閉包的定義，Warshall 演算法或矩陣乘法。

設關係 $R$ 在一個有 $n$ 個元素的集合上的表示矩陣為 $M_R$。
遞移閉包 $R^*$ 的矩陣表示 $M_{R^*}$ 可以通過 Warshall 演算法計算。
Warshall 演算法的基本思想是：對於集合中的每一個點 $k$，檢查是否存在從點 $i$ 到點 $j$ 的路徑，該路徑可以經過點 $k$。

矩陣表示法：
若 $M_R$ 是關係 $R$ 的鄰接矩陣，則 $M_{R^2} = M_R \times M_R$ (矩陣乘法，但這裡的乘法是邏輯乘法，即 $1+1=1$，$0+0=0$，$1+0=1$，$0 \times 1 = 0$，$1 \times 1 = 1$ 等)。
更精確地說，在二元關係的上下文中，我們通常進行布林矩陣乘法（Boolean matrix multiplication），其中加法對應於邏輯 OR，乘法對應於邏輯 AND。
$M_{R^2}[i, j] = \bigvee_{k=1}^n (M_R[i, k] \land M_R[k, j])$。
遞移閉包 $R^*$ 包含所有長度為 1 的路徑，以及所有長度為 2, 3, ..., n 的路徑。
$M_{R^*} = M_R \lor M_R^2 \lor M_R^3 \lor \dots \lor M_R^n$。
其中 $\lor$ 是矩陣的邏輯 OR 運算。

對於一個有 $n$ 個元素的集合，遞移閉包的矩陣 $M_{R^*}$ 可以通過計算 $M_R$ 的 $n$ 次方（布林矩陣乘法），然後將 $M_R$ 和所有 $M_R^k$ ($k=2, \dots, n$) 的結果進行邏輯 OR 運算得到。
然而，更有效的方法是使用 Warshall 演算法。

Warshall 演算法：
初始化 $M = M_R$。
對於 $k$ 從 1 到 $n$：
對於 $i$ 從 1 到 $n$：
對於 $j$ 從 1 到 $n$：
$M[i, j] = M[i, j] \lor (M[i, k] \land M[k, j])$

這裡，集合的元素數量是 3，所以 $n=3$。
$M_R = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \end{bmatrix}$

步驟 1：k = 1
$M^{(1)} = M_R$
對於 $i=1, \dots, 3$, $j=1, \dots, 3$: $M^{(1)}[i, j] = M_R[i, j] \lor (M_R[i, 1] \land M_R[1, j])$

$i=1$: $M[1,j] = M_R[1,j] \lor (M_R[1,1] \land M_R[1,j]) = M_R[1,j] \lor (1 \land M_R[1,j]) = M_R[1,j]$ (第一列不受影響)
$i=2$: $M[2,j] = M_R[2,j] \lor (M_R[2,1] \land M_R[1,j]) = M_R[2,j] \lor (0 \land M_R[1,j]) = M_R[2,j]$ (第二列不受影響)
$i=3$: $M[3,j] = M_R[3,j] \lor (M_R[3,1] \land M_R[1,j]) = M_R[3,j] \lor (1 \land M_R[1,j])$
$j=1$: $M[3,1] = M_R[3,1] \lor (1 \land M_R[1,1]) = 1 \lor (1 \land 1) = 1 \lor 1 = 1$
$j=2$: $M[3,2] = M_R[3,2] \lor (1 \land M_R[1,2]) = 1 \lor (1 \land 0) = 1 \lor 0 = 1$
$j=3$: $M[3,3] = M_R[3,3] \lor (1 \land M_R[1,3]) = 0 \lor (1 \land 1) = 0 \lor 1 = 1$
所以，經過 $k=1$ 後的矩陣是：
$M^{(1)} = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix}$

步驟 2：k = 2
$M^{(2)}[i, j] = M^{(1)}[i, j] \lor (M^{(1)}[i, 2] \land M^{(1)}[2, j])$

$i=1$: $M[1,j] = M^{(1)}[1,j] \lor (M^{(1)}[1,2] \land M^{(1)}[2,j]) = M^{(1)}[1,j] \lor (0 \land M^{(1)}[2,j]) = M^{(1)}[1,j]$ (第一列不受影響)
$i=2$: $M[2,j] = M^{(1)}[2,j] \lor (M^{(1)}[2,2] \land M^{(1)}[2,j]) = M^{(1)}[2,j] \lor (1 \land M^{(1)}[2,j]) = M^{(1)}[2,j]$ (第二列不受影響)
$i=3$: $M[3,j] = M^{(1)}[3,j] \lor (M^{(1)}[3,2] \land M^{(1)}[2,j]) = M^{(1)}[3,j] \lor (1 \land M^{(1)}[2,j])$
$j=1$: $M[3,1] = M^{(1)}[3,1] \lor (1 \land M^{(1)}[2,1]) = 1 \lor (1 \land 0) = 1 \lor 0 = 1$
$j=2$: $M[3,2] = M^{(1)}[3,2] \lor (1 \land M^{(1)}[2,2]) = 1 \lor (1 \land 1) = 1 \lor 1 = 1$
$j=3$: $M[3,3] = M^{(1)}[3,3] \lor (1 \land M^{(1)}[2,3]) = 1 \lor (1 \land 0) = 1 \lor 0 = 1$
所以，經過 $k=2$ 後的矩陣是：
$M^{(2)} = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix}$ (與 $M^{(1)}$ 相同)

步驟 3：k = 3
$M^{(3)}[i, j] = M^{(2)}[i, j] \lor (M^{(2)}[i, 3] \land M^{(2)}[3, j])$

$i=1$: $M[1,j] = M^{(2)}[1,j] \lor (M^{(2)}[1,3] \land M^{(2)}[3,j]) = M^{(2)}[1,j] \lor (1 \land M^{(2)}[3,j])$
$j=1$: $M[1,1] = M^{(2)}[1,1] \lor (1 \land M^{(2)}[3,1]) = 1 \lor (1 \land 1) = 1 \lor 1 = 1$
$j=2$: $M[1,2] = M^{(2)}[1,2] \lor (1 \land M^{(2)}[3,2]) = 0 \lor (1 \land 1) = 0 \lor 1 = 1$
$j=3$: $M[1,3] = M^{(2)}[1,3] \lor (1 \land M^{(2)}[3,3]) = 1 \lor (1 \land 1) = 1 \lor 1 = 1$
$i=2$: $M[2,j] = M^{(2)}[2,j] \lor (M^{(2)}[2,3] \land M^{(2)}[3,j]) = M^{(2)}[2,j] \lor (0 \land M^{(2)}[3,j]) = M^{(2)}[2,j]$ (第二列不受影響)

本題考驗對偏序關係（Partial Ordering Relation）定義的理解。

核心觀念： 偏序關係的定義（自反性、反對稱性、遞移性）。

一個關係 $R$ 在一個集合 $S$ 上稱為一個偏序關係，如果它滿足以下三個性質：

1. 自反性 (Reflexivity)： 對於 $S$ 中的任意元素 $a$，必須有 $a R a$。
2. 反對稱性 (Antisymmetry)： 對於 $S$ 中的任意元素 $a, b$，如果 $a R b$ 且 $b R a$，則必須有 $a = b$。
3. 遞移性 (Transitivity)： 對於 $S$ 中的任意元素 $a, b, c$，如果 $a R b$ 且 $b R c$，則必須有 $a R c$。

我們要證明關係 $\geq$ 在整數集合 $Z$ 上是一個偏序關係。

證明：
設 $a, b, c$ 是任意三個整數。

1. 自反性：
   對於任意整數 $a \in Z$，我們知道 $a = a$。因此，$a \geq a$ 成立。
   所以，$\geq$ 是自反的。

2. 反對稱性：
   對於任意整數 $a, b \in Z$，假設 $a \geq b$ 且 $b \geq a$。

本題考驗對等價關係（equivalence relation）定義的理解，並將其應用於圖論中的路徑概念。

核心觀念： 等價關係的定義（自反性、對稱性、遞移性），圖中的路徑。

一個關係 $R$ 在集合 $V$ 上是一個等價關係，如果它滿足以下三個性質：

1. 自反性 (Reflexivity)： 對於 $V$ 中的任意元素 $u$，必須有 $(u, u) \in R$。
2. 對稱性 (Symmetry)： 對於 $V$ 中的任意元素 $u, v$，如果 $(u, v) \in R$，則必須有 $(v, u) \in R$。
3. 遞移性 (Transitivity)： 對於 $V$ 中的任意元素 $u, v, w$，如果 $(u, v) \in R$ 且 $(v, w) \in R$，則必須有 $(u, w) \in R$。

給定一個簡單圖 $G = (V, E)$。關係 $R$ 定義在頂點集合 $V$ 上，其中 $(u, v) \in R$ 若且唯若存在一條從 $u$ 到 $v$ 的路徑，或者 $u=v$。
我們需要證明 $R$ 是等價關係。

證明：
令 $u, v, w$ 是圖 $G$ 的任意三個頂點。

1. 自反性：
   我們需要證明對於任意頂點 $u \in V$， $(u, u) \in R$。
   根據 $R$ 的定義，如果 $u=u$，則 $(u, u) \in R$。
   每個頂點都等於自身，所以存在一條從 $u$ 到 $u$ 的「長度為 0 的路徑」（或者直接滿足 $u=v$ 的條件）。
   因此，$R$ 是自反的。

2. 對稱性：
   我們需要證明對於任意頂點 $u, v \in V$，如果 $(u, v) \in R$，則 $(v, u) \in R$。
   假設 $(u, v) \in R$。根據定義，這意味著：

   • 存在一條從 $u$ 到 $v$ 的路徑，或者

   • $u = v$。

   • 情況 1： $u = v$。
     如果 $u = v$，那麼 $(u, u) \in R$。這也意味著 $(v, u) \in R$（因為 $v=u$）。

   • 情況 2： 存在一條從 $u$ 到 $v$ 的路徑。
     設這條路徑為 $u = x_0, x_1, \dots, x_k = v$。
     由於圖是無向圖（題目中提到「connected undirected graph」在第 8 題，雖然此處未明確說明，但一般圖論中的「簡單圖」且討論路徑時，若未特別說明通常是無向的。即使是方向圖，如果存在從 $u$ 到 $v$ 的路徑，我們也需要證明是否存在從 $v$ 到 $u$ 的路徑。然而，題目通常預設「簡單圖」為無向圖，若為有向圖則會明確標示。假設為無向圖），如果存在一條從 $u$ 到 $v$ 的路徑，那麼我們也可以沿著相同的邊反方向行走，從 $v$ 到 $u$ 找到一條路徑：$v = x_k, x_{k-1}, \dots, x_0 = u$。
     因此，存在一條從 $v$ 到 $u$ 的路徑。
     根據 $R$ 的定義，這意味著 $(v, u) \in R$。

本題考驗圖論中連通圖（Connected Graph）的定義及其性質。

核心觀念： 連通圖的定義，路徑（Path），簡單路徑（Simple Path）。

定義：

• 無向圖 (Undirected Graph)： 一個圖 $G=(V, E)$，其中邊集 $E$ 中的邊是無序對 $\{u, v\}$。
• 連通圖 (Connected Graph)： 一個無向圖，對於圖中任意兩個不同的頂點 $u$ 和 $v$，都存在一條從 $u$ 到 $v$ 的路徑。
• 路徑 (Path)： 一個頂點序列 $v_0, v_1, \dots, v_k$，其中 $\{v_{i-1}, v_i\}$ 是圖中的一條邊，對於所有 $i = 1, \dots, k$。
• 簡單路徑 (Simple Path)： 一個路徑，其中所有頂點都是不同的（除了起點和終點可能相同，但這裡題目要求是「distinct vertices」，所以起點和終點也必須不同）。也就是說，在一個簡單路徑 $v_0, v_1, \dots, v_k$ 中，$v_i \neq v_j$ 對於所有 $i \neq j$。

題目要求：
證明對於一個連通的無向圖，任意兩個不同的頂點之間都存在一條簡單路徑。

證明：
假設 $G=(V, E)$ 是一個連通的無向圖。
令 $u$ 和 $v$ 是圖 $G$ 中任意兩個不同的頂點 ($u \neq v$)。
由於圖 $G$ 是連通的，根據連通圖的定義，必然存在一條從 $u$ 到 $v$ 的路徑。
設這條路徑為 $P = (v_0, v_1, \dots, v_k)$，其中 $v_0 = u$ 且 $v_k = v$。

現在我們需要證明這條路徑 $P$ 可以被簡化成一條簡單路徑。
如果路徑 $P$ 本身就是一條簡單路徑，那麼我們的證明就完成了。
如果路徑 $P$ 不是一條簡單路徑，這意味著路徑中至少有兩個頂點是重複的。也就是說，存在 $i$ 和 $j$ 使得 $0 \le i < j \le k$ 且 $v_i = v_j$。

我們可以通過「縮短」路徑來去除重複的頂點。
假設路徑 $P$ 第一次出現重複頂點是在 $v_i = v_j$（其中 $j$ 是第一個使得 $v_j$ 重複的索引，而 $v_i$ 是第一次出現的那個相同的頂點，且 $i < j$）。
那麼，我們可以構造一個新的路徑 $P'$，將原路徑 $P$ 中從 $v_i$ 到 $v_j$ 的部分替換掉。
新的路徑 $P'$ 可以是：
$(v_0, v_1, \dots, v_i, v_{j+1}, \dots, v_k)$。

這個新的路徑 $P'$ 仍然從 $u=v_0$ 開始，並結束於 $v=v_k$。
由於我們移除了從 $v_i$ 到 $v_j$ 的這一段（包括 $v_j$），路徑的長度縮短了。

本題是一個典型的圖著色（Graph Coloring）問題，可以轉化為尋找課程時間表的問題。

核心觀念： 圖的著色，關聯圖（Interval Graph 或 Conflict Graph），最小著色數。

問題轉化：
我們可以將這個問題建模成一個圖論問題。

1. 頂點 (Vertices)： 將每一門課程視為圖中的一個頂點。這裡有 A, B, C, D, E, F, G 共 7 個頂點。
2. 邊 (Edges)： 如果兩門課程有共同的學生，則在這兩門課程對應的頂點之間連一條邊。這意味著這兩門課程不能安排在同一個考試時間。
3. 目標： 我們需要為這個圖的頂點分配「考試時間」，使得相鄰的頂點（有共同學生的課程）被分配到不同的考試時間。我們希望使用的考試時間（顏色）的數量最少。這個問題實際上是在尋找圖的最小著色數（chromatic number）。

建立關聯圖：
根據題目給出的「有共同學生的課程對」，我們建立圖的邊：

• A: 和 B, C, D, G 有共同學生。連邊 (A,B), (A,C), (A,D), (A,G)。
• B: 和 A, C, D, E, G 有共同學生。連邊 (B,A), (B,C), (B,D), (B,E), (B,G)。 (A,B) 已有。
• C: 和 A, B, D, F, G 有共同學生。連邊 (C,A), (C,B), (C,D), (C,F), (C,G)。 (A,C), (B,C) 已有。
• D: 和 A, B, C, E, F 有共同學生。連邊 (D,A), (D,B), (D,C), (D,E), (D,F)。 (A,D), (B,D), (C,D) 已有。
• E: 和 B, D, F, G 有共同學生。連邊 (E,B), (E,D), (E,F), (E,G)。 (B,E), (D,E) 已有。
• F: 和 C, D, E, G 有共同學生。連邊 (F,C), (F,D), (F,E), (F,G)。 (C,F), (D,F), (E,F) 已有。
• G: 和 A, B, C, E, F 有共同學生。連邊 (G,A), (G,B), (G,C), (G,E), (G,F)。 (A,G), (B,G), (C,G), (E,G), (F,G) 已有。

整理邊集（不重複）：
(A,B), (A,C), (A,D), (A,G)
(B,C), (B,D), (B,E), (B,G)
(C,D), (C,F), (C,G)
(D,E), (D,F)
(E,F), (E,G)
(F,G)

圖的結構分析：
這個圖是一個 7 個頂點的圖。我們需要找到最小的「顏色數」（考試時間數）。
首先，尋找圖中的「完全子圖」（Clique），因為一個大小為 $k$ 的完全子圖至少需要 $k$ 種顏色。
觀察：

• 頂點 A, B, C, D 之間是否有互相連接？
  • A-B, A-C, A-D
  • B-C, B-D
  • C-D
    是的，頂點 A, B, C, D 構成一個 $K_4$（四個頂點的完全圖）。
    這意味著 A, B, C, D 四門課程之間都有共同的學生，所以這四門課程必須安排在不同的考試時間。
    因此，我們至少需要 4 個考試時間。

圖著色（分配考試時間）：
我們嘗試使用 4 個時間點（例如，時間 1, 2, 3, 4）來安排考試。

1. 給 A, B, C, D 著色：
   由於 A, B, C, D 構成 $K_4$，它們必須有不同的顏色。
   令：
   A: 時間 1
   B: 時間 2
   C: 時間 3
   D: 時間 4

2. 給 E 著色：
   E 與 B, D, F, G 有共同學生。
   E 不能與 B (時間 2) 同時考試。
   E 不能與 D (時間 4) 同時考試。
   E 可以與 A (時間 1) 同時考試。
   E 可以與 C (時間 3) 同時考試。
   我們還有 F 和 G 未確定顏色。
   E 與 F 有共同學生，E 與 G 有共同學生。
   我們需要檢查 E 的鄰居：B (時間 2), D (時間 4), F, G。
   所以，E 的顏色不能是 2 或 4。我們可以給 E 著色為 1 或 3。
   假設我們給 E 著色為 1。
   A: 1
   B: 2
   C: 3
   D: 4
   E: 1 (因為 E 和 A 沒有邊)

3. 給 F 著色：
   F 與 C, D, E, G 有共同學生。
   F 不能與 C (時間 3) 同時考試。
   F 不能與 D (時間 4) 同時考試。
   F 不能與 E (時間 1) 同時考試。
   F 的鄰居是 C (3), D (4), E (1), G。
   F 的顏色不能是 1, 3, 4。
   所以 F 的顏色必須是 2。
   A: 1
   B: 2
   C: 3
   D: 4
   E: 1
   F: 2

核心觀念

本題考查以子集合建構法（subset construction），將 NFA 轉換為 DFA。

DFA 的每一個狀態，代表 NFA 可能同時所在的狀態集合。DFA 狀態若包含 NFA 的終止狀態，便是 DFA 的終止狀態。

由圖可讀得：

• 初始狀態：$S_0$
• 終止狀態：$S_0,S_1$
• 轉移：
  • $S_0 \xrightarrow{0,1} S_1$
  • $S_0 \xrightarrow{1} S_2$
  • $S_2 \xrightarrow{0} S_1$
  • $S_2 \xrightarrow{1} S_2$

解題方法：子集合建構法

令 DFA 初始狀態為：

$$A=\{S_0\}$$

依序計算各集合在輸入 $0,1$ 下的轉移。

DFA 狀態	NFA 狀態集合	輸入 $0$	輸入 $1$	是否終止狀態
$A$	$\{S_0\}$	$\{S_1\}=B$	$\{S_1,S_2\}=C$	是
$B$	$\{S_1\}$	$\varnothing=E$	$\varnothing=E$	是
$C$	$\{S_1,S_2\}$	$\{S_1\}=B$	$\{S_2\}=D$	是
$D$	$\{S_2\}$	$\{S_1\}=B$	$\{S_2\}=D$	否
$E$	$\varnothing$	$\varnothing=E$	$\varnothing=E$	否

其中：

• $A$ 是初始狀態。
• $A,B,C$ 為終止狀態，因為集合中含有 $S_0$ 或 $S_1$。
• $E$ 是死狀態，代表 NFA 已沒有任何可能的所在狀態。

因此，子集合建構所得的 DFA 為：

$$Q=\{A,B,C,D,E\}$$ $$\Sigma=\{0,1\}$$ $$q_0=A$$ $$F=\{A,B,C\}$$

轉移函數如下：

$$\delta(A,0)=B,\qquad \delta(A,1)=C$$