109 年 國立中正大學資訊工程學系碩士班甲組《軟體設計》

這題考的是物件導向程式設計中類別繼承的基本觀念。

一個類別可以被多個其他類別繼承，也就是說，一個父類別可以有多個子類別。這在物件導向設計中是常見的「多型」和「繼承」的應用。

例如，在 C++ 中，我們可以定義一個基底類別 Base，然後讓 Derived1 和 Derived2 都繼承自 Base。

這題考的是物件導向程式設計中類別解構子的觀念。

這題考的是 C++ 中類別建構子的預設行為。

在 C++ 中，如果一個類別沒有明確定義任何建構子（constructor），編譯器會自動產生一個「預設建構子」（default constructor）。這個預設建構子是公有的（public），沒有參數，並且不做任何事情（或者說，它會依照成員的類型進行預設初始化，例如內建型別成員可能未初始化，而類別型別成員會呼叫它們各自的預設建構子）。

核心觀念

本題考查：

1. Bubble Sort 的交換條件與排序方向
2. C++ 函式參數的參考傳遞
3. vector 的模板型別宣告
4. 陣列範圍的半開區間
5. 陣列索引邊界
6. 輸入／輸出運算子方向

升冪排序要求較大的元素逐步往右移，因此相鄰元素必須在「左邊大於右邊」時交換：

每完成一輪外層迴圈，未排序區間中最大的元素會被推到最右端。

解題方法

逐行檢查程式，確認以下三件事：

• 函式參數是否能真正修改原本的資料。
• 每個索引是否都在合法範圍內。
• Bubble Sort 的交換方向是否符合升冪排序。

各行錯誤與修正

1. SwapIntegers 沒有使用參考傳遞

原程式：

void SwapIntegers (int a, int b)

這是值傳遞，函式內的 a、b 只是複本，無法改變 intVector 中的元素。

應改成：

void SwapIntegers (int &a, int &b)

其中 & 表示參考傳遞，函式內修改的就是呼叫端的原始變數。

2. 交換函式最後一步寫錯

原程式：

int temp = a;
a = b;
temp = b;

第三行再次修改 temp，卻沒有把暫存值放回 b。

正確交換流程為：

int temp = a;
a = b;
b = temp;

3. vector 缺少元素型別

原程式：

void BubbleSort (vector &intVector)

vector 是類別模板，必須指定元素型別。由於資料是整數向量，應寫成：

void BubbleSort (vector<int> &intVector)

同時加入 &，使排序函式能直接修改原本的向量。

4. 內層迴圈的 j 未宣告

原程式：

for (j = 0; j < i; j++)

必須宣告 j 的型別：

for (int j = 0; j < i; j++)

5. Bubble Sort 的比較方向錯誤

原程式：

if (intVector[j] < intVector[j + 1])

這會把較小的元素往左推，形成降冪排序。

題目要求升冪排序，且最大值要被帶到陣列尾端，因此應改成：

if (intVector[j] > intVector[j + 1])

6. vector 建構範圍少放入一個元素

原程式：

vector<int> intVector(intArray, intArray + 9);

C++ 的範圍建構採用半開區間：

因此 intArray + 9 只會取索引 $0$ 到 $8$，總共 9 個元素，遺漏索引 $9$ 的 0。

應改成：

vector<int> intVector(intArray, intArray + 10);

也可寫成：

vector<int> intVector(intArray, intArray + sizeof(intArray) / sizeof(intArray[0]));

本題中直接使用 +10 即可。

7. 呼叫函式時不應傳入位址

原程式：

BubbleSort (&intVector);

BubbleSort 的參數是 vector<int>&，呼叫時應傳入向量本身：

BubbleSort (intVector);

&intVector 是向量的位址，型別會變成指標，與函式參數不相符。

8. 輸出迴圈的邊界錯誤

原程式：

for (int i = 0; i <= intVector.size(); i++)

合法索引為：

核心觀念

本題考查單向鏈結串列的：

1. 節點資料結構宣告。
2. 動態配置新節點。
3. 將新節點插入串列最前端。
4. 更新串列的 head 指標。
5. 函式回傳新的 head 指標。

單向鏈結串列節點通常包含：

• 資料欄位：name
• 鏈結欄位：指向下一個節點的指標 link

若新節點要成為第一個節點，指標關係必須是：

接著將 newNode 作為新的 head：

題目未明確說明 32 bytes 是否包含字串結尾的 '\0'。以下採用 C 語言常見字串表示法，假設名稱最多為 32 個字元，因此配置 33 bytes，額外保留 1 byte 給 '\0'。

解題方法

先宣告節點結構：

typedef struct node {
    char name[33];          /* 最多 32 個字元，加上 '\0' */
    struct node *link;      /* 指向下一個節點 */
} Node;

插入步驟如下：

1. 使用 malloc 配置一個新節點。
2. 將輸入名稱複製到新節點的 name。
3. 將新節點的 link 指向原本的 head。
4. 回傳新節點，作為新的 head。

完整函式如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node {
    char name[33];
    struct node *link;
} Node;

Node *insert(Node *head, const char *name)
{
    Node *newNode;

    newNode = (Node *)malloc(sizeof(Node));

    if (newNode == NULL) {
        return head;
    }

    strncpy(newNode->name, name, 32);
    newNode->name[32] = '\0';

    newNode->link = head;

    return newNode;
}

使用方式：

Node *head = NULL;

head = insert(head, "Alice");
head = insert(head, "Bob");

執行後的串列為：

核心觀念

本題考查 C 語言的：

• 函式參數傳遞
• 指標與位址運算子 &
• 解參照運算子 *
• 以指標修改呼叫端變數
• 交換兩個整數的標準寫法

C 語言的函式參數預設採用「傳值呼叫」。若直接傳入 x、y，函式只會取得兩份副本，無法改變 main() 中原本的變數。

因此，必須傳入 x、y 的記憶體位址，並在 swap() 中透過指標修改其內容。

解題方法

1. 函式參數使用整數指標

x 與 y 的型別都是 int，其位址型別則是 int *，因此函式宣告為：

void swap(int *a, int *b)

其中：

• a 儲存 x 的位址
• b 儲存 y 的位址
• *a 代表位於 a 所指向位址中的整數值
• *b 代表位於 b 所指向位址中的整數值

2. 呼叫函式時傳入位址

使用位址運算子 &：

swap(&x, &y);

此時：

• a 指向 x
• b 指向 y

因此修改 *a 就等同於修改 x，修改 *b 就等同於修改 y。

3. 使用暫存變數完成交換

交換前：

使用暫存變數：

int temp;
temp = *a;
*a = *b;
*b = temp;

執行過程如下：

1. temp = *a：temp 儲存 10
2. *a = *b：將 20 寫入 x
3. *b = temp：將 10 寫入 y

交換後：

完整程式碼

核心觀念

本題考查：

1. 使用 fgets() 從標準輸入逐行讀取資料。
2. 以字串長度判斷哪一行最長。
3. 當長度相同時，保留先讀到的那一行。
4. 正確處理換行字元 '\n' 與檔案結尾 EOF。

fgets() 的特性如下：

• 最多讀取指定大小減一個字元。
• 若讀到換行字元，會將 '\n' 一併存入字串。
• 讀到檔案結尾且沒有讀到任何字元時，回傳 NULL。

因此，比較長度時應排除行尾的 '\n'。

解題方法

逐行讀取輸入資料，對每一行進行以下處理：

1. 使用 fgets() 讀入資料。
2. 若一行太長，使用多次 fgets() 接續讀完同一行。
3. 移除行尾的換行字元。
4. 計算該行長度。
5. 若目前沒有最長行，或本行長度嚴格大於目前最長長度，便更新答案。

更新條件必須使用：

if (line_length > longest_length)

不能使用 >=，因為題目要求長度相同時輸出第一行。

參考程式碼

這題考驗將中序表達式（infix expression）轉換為後序表達式（postfix expression）的能力，這通常使用堆疊（stack）來實現。

核心觀念：

• 中序表達式： 運算子位於兩個運算元之間，例如 a + b。
• 後序表達式： 運算子位於兩個運算元之後，例如 a b +。
• 運算子的優先級： 乘除 (*, /) 的優先級高於加減 (+, -)。
• 括號： 括號用於改變運算子的預設優先級。
• 堆疊（Stack）： 用於暫存運算子和處理括號。

轉換演算法（使用堆疊）：

1. 掃描中序表達式從左到右。
2. 遇到運算元：直接輸出到後序表達式。
3. 遇到開括號 (：壓入堆疊。
4. 遇到閉括號 )：將堆疊中所有在開括號之前的運算子依序彈出並輸出，直到遇到開括號。然後將開括號彈出（但不輸出）。
5. 遇到運算子：
   • 當堆疊為空或頂端是開括號時，將當前運算子壓入堆疊。
   • 否則，比較當前運算子與堆疊頂端的運算子。
     • 如果當前運算子優先級 高於 或 等於 堆疊頂端的運算子，則將當前運算子壓入堆疊。
     • 如果當前運算子優先級 低於 堆疊頂端的運算子，則彈出堆疊頂端的運算子並輸出，然後重複此步驟，直到堆疊頂端的運算子優先級低於當前運算子，或堆疊變為空，或遇到開括號。之後再將當前運算子壓入堆疊。
6. 表達式掃描完畢後，將堆疊中剩餘的所有運算子依序彈出並輸出。

運算子優先級：

• *, / : 較高
• +, - : 較低

(a) a*(b+c/d)-e

1. a：輸出 a。後序：a
2. *：堆疊為空，壓入 *。堆疊：*
3. (：壓入 (。堆疊：*, (
4. b：輸出 b。後序：a b
5. +：堆疊頂端是 (，壓入 +。堆疊：*, (, +
6. c：輸出 c。後序：a b c
7. /：/ 優先級高於 +。壓入 /。堆疊：*, (, +, /
8. d：輸出 d。後序：a b c d
9. )：彈出堆疊頂端運算子並輸出，直到遇到 (。
   • 彈出 /，輸出 /。後序：a b c d /。堆疊：*, (, +

這題考驗對二元樹（Binary Tree）計數問題的理解，這通常與卡塔蘭數（Catalan numbers）有關。

核心觀念：

• 二元樹 (Binary Tree)： 一種樹形結構，其中每個節點最多有兩個子節點（左子節點和右子節點）。
• 結構不同 (Structurally distinct)： 指的是樹的形狀不同，即使節點的值相同（但在這個問題中，我們只關心結構，節點是無標籤的）。
• 卡塔蘭數 (Catalan Numbers)： 一系列在組合數學中出現的數字序列。第 n 個卡塔蘭數 $C_n$ 可以用來計算具有 n 對括號的組合、n+1 個葉節點的二元樹（或 n 個內部節點的二元樹）的數量，以及 n 個節點的二元樹的數量（如果節點是無標籤的）。

計算公式：
對於有 n 個節點的無標籤二元樹，其結構不同的數量為第 n 個卡塔蘭數 $C_n$。
卡塔蘭數的遞迴定義是：
$C_0 = 1$
$C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$

卡塔蘭數的封閉形式（closed-form）公式是：
$C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}$

我們需要計算 $C_2, C_3, C_4, C_5$。

計算過程：

• n = 2 (2 個節點)：

  • 使用遞迴：$C_2 = C_0 C_1 + C_1 C_0$
    • 首先需要 $C_0$ 和 $C_1$。
    • $C_0 = 1$ (空樹)
    • $C_1 = C_0 C_0 = 1 \times 1 = 1$ (只有一個節點的樹)
    • 所以，$C_2 = (1 \times 1) + (1 \times 1) = 1 + 1 = 2$
  • 使用封閉形式：$C_2 = \frac{1}{2+1} \binom{2 \times 2}{2} = \frac{1}{3} \binom{4}{2} = \frac{1}{3} \times \frac{4!}{2!2!} = \frac{1}{3} \times \frac{24}{4} = \frac{1}{3} \times 6 = 2$
  • 2 個節點的二元樹數量：2

• n = 3 (3 個節點)：

  • 使用遞迴：$C_3 = C_0 C_2 + C_1 C_1 + C_2 C_0$
    • $C_3 = (1 \times 2) + (1 \times 1) + (2 \times 1) = 2 + 1 + 2 = 5$

核心觀念

本題考查兩種自我平衡搜尋樹的插入：

• AVL Tree：每個節點的平衡因子必須為 $-1,0,1$。

  $BF(v)=h(\text{left})-h(\text{right})$

  插入後若失衡，依失衡型態使用 LL、RR、LR、RL 旋轉。

• Red-Black Tree：採用標準定義：

  1. 每個節點為紅色或黑色。
  2. 根節點為黑色。
  3. 所有 NIL 葉節點為黑色。
  4. 紅色節點的子節點必須為黑色。
  5. 從任一節點到其所有後代 NIL 葉節點的每條路徑，黑色節點數相同。

  新插入節點先設為紅色，再透過重新著色與旋轉修正。

一、AVL Tree

插入順序為：

$50,\ 10,\ 80,\ 90,\ 70,\ 60,\ 65,\ 62$

插入 50、10、80、90、70

插入 70 後，樹為：

        50
       /  \
     10    80
          /  \
        70    90

插入 60

插入 60 後：

        50
       /  \
     10    80
          /  \
        70    90
       /
      60

此時節點 50 的右子樹高度過高：

$BF(50)=1-3=-2$

而插入路徑為：

$50\rightarrow80\rightarrow70\rightarrow60$

屬於 RL 型（Right-Left），必須：

1. 先對 80 做右旋。
2. 再對 50 做左旋。

旋轉後：

        70
       /  \
     50    80
    / \     \
  10  60     90

插入 65

        70
       /  \
     50    80
    / \     \
  10  60     90
        \
         65

此時尚未造成失衡。

插入 62

插入 62 後，局部結構為：

      60
        \
         65
        /
       62

節點 60 的平衡因子為：

$BF(60)=0-2=-2$

這是 RL 型，因此：

1. 對 65 做右旋。
2. 對 60 做左旋。

局部結構變成：

       62
      /  \
    60    65

因此最後的 AVL Tree 為：

          70
         /  \
       50    80
      /  \     \
    10    62     90
         /  \
        60   65

二、Red-Black Tree

以下採用標準 Red-Black Tree 插入規則：新節點為紅色，根節點最後調整為黑色。記號 $B$ 表示黑色，$R$ 表示紅色。

插入 50、10、80

      50B
     /   \
   10R   80R

插入 90

90 插入為 80 的右子節點：

      50B
     /   \
   10R   80R
             \
             90R

此時 80 與 90 同為紅色，且 80 的兄弟 10 也是紅色，因此重新著色：

• 10、80 改為黑色。
• 50 暫時改為紅色。
• 根節點 50 再改回黑色。

      50B
     /   \
   10B   80B
             \
             90R

插入 70

這題考驗對 KMP (Knuth-Morris-Pratt) 演算法中 fail 函式（也稱為 LPS 陣列或 prefix function）的理解與計算。這個函式用於計算模式字串（pattern string）中，對於每個位置 j，其最長的真前綴（proper prefix）等於真後綴（proper suffix）的長度。

核心觀念：

• KMP 演算法： 一種用於字串匹配的高效演算法。
• fail 陣列 (LPS 陣列)： 儲存模式字串的「部分匹配表」。failure[j] 表示模式字串 pat 的前綴 pat[0...j] 中，最長的真前綴等於真後綴的長度。
  • 真前綴 (proper prefix)： 不包含字串本身的前綴。
  • 真後綴 (proper suffix)： 不包含字串本身的的後綴。
• fail 函式邏輯：
  • failure[0] 總是設為 -1。這表示如果模式字串的第一個字元就不匹配，我們可以直接移動模式串。
  • 對於 j 從 1 開始，計算 failure[j]：
    • 首先，我們查看 failure[j-1] 的值，記為 i。這個 i 代表了 pat[0...j-1] 的最長真前綴/真後綴的長度。
    • 我們試圖將 pat[j] 和 pat[i+1] 進行比較。
      • 如果 pat[j] == pat[i+1]，表示我們找到了更長的前綴/後綴匹配。新的長度就是 i+1。所以 failure[j] = i+1。
      • 如果 pat[j] != pat[i+1]，表示 pat[j] 不能延長當前的匹配。我們需要縮短當前的匹配長度 i。如何縮短？我們查找 pat[0...i] 的下一個較短的真前綴/真後綴長度，這個長度就是 failure[i]。我們重複這個過程（i = failure[i]），直到找到一個 i 使得 pat[j] == pat[i+1]，或者 i 變為 -1。
      • 如果 i 變為 -1 且 pat[j] 仍然不等於 pat[0] (即 pat[i+1] 為 pat[0])，則表示沒有任何真前綴等於真後綴，failure[j] 設為 -1。
      • 如果 i 變為 -1 但 pat[j] == pat[0]，則 failure[j] 設為 0。

計算步驟：

(a) pat = "abaabaab"
n = 8
failure 陣列大小為 8。

• j = 0: failure[0] = -1

• j = 1: pat[1] = 'b'.

  • i = failure[0] = -1.
  • while (pat[1] != pat[i+1] && i >= 0): pat[1] ('b') != pat[-1+1] (pat[0]='a')，且 i (-1) < 0。迴圈不執行。
  • if (pat[1] == pat[i+1]): pat[1] ('b') == pat[0] ('a') ? False.
  • failure[1] = i = -1.
  • failure: {-1, -1, ?, ?, ?, ?, ?, ?}

• j = 2: pat[2] = 'a'.

  • i = failure[1] = -1.
  • while (pat[2] != pat[i+1] && i >= 0): pat[2] ('a') != pat[0] ('a') ? False. 迴圈不執行。
  • if (pat[2] == pat[i+1]): pat[2] ('a') == pat[0] ('a') ? True.
  • i++ (i becomes 0).
  • failure[2] = i = 0.
  • failure: {-1, -1, 0, ?, ?, ?, ?, ?}

• j = 3: pat[3] = 'a'.

  • i = failure[2] = 0.
  • while (pat[3] != pat[i+1] && i >= 0): pat[3] ('a') != pat[0+1] (pat[1]='b') ? True. 且 i (0) >= 0.
    • i = failure[i] = failure[0] = -1.
  • while 條件 i >= 0 為 False，迴圈結束。
  • if (pat[3] == pat[i+1]): pat[3] ('a') == pat[-1+1] (pat[0]='a') ? True.
  • i++ (i becomes 0).
  • failure[3] = i = 0.
  • failure: {-1, -1, 0, 0, ?, ?, ?, ?}

• j = 4: pat[4] = 'b'.

  • i = failure[3] = 0.
  • while (pat[4] != pat[i+1] && i >= 0): pat[4] ('b') != pat[0+1] (pat[1]='b') ? False. 迴圈不執行。
  • if (pat[4] == pat[i+1]): pat[4] ('b') == pat[1] ('b') ? True.
  • i++ (i becomes 1).
  • failure[4] = i = 1.
  • failure: {-1, -1, 0, 0, 1, ?, ?, ?}

• j = 5: pat[5] = 'a'.

  • i = failure[4] = 1.
  • while (pat[5] != pat[i+1] && i >= 0): pat[5] ('a') != pat[1+1] (pat[2]='a') ? False. 迴圈不執行。
  • if (pat[5] == pat[i+1]): pat[5] ('a') == pat[2] ('a') ? True.
  • i++ (i becomes 2).
  • failure[5] = i = 2.
  • failure: {-1, -1, 0, 0, 1, 2, ?, ?}

核心觀念

Quick sort 的基本流程如下：

1. 選定子序列的 pivot。
2. 進行 partition，使得：
   • pivot 左側的元素皆不大於 pivot；
   • pivot 右側的元素皆不小於 pivot。
3. pivot 定位後，再對左右兩個子序列遞迴排序。
4. 子序列長度為 $0$ 或 $1$ 時停止。

本題指定「每個子序列的第一個元素作為 pivot」。以下採用常見的雙向掃描 partition：

• 左指標由左向右尋找大於 pivot 的元素；
• 右指標由右向左尋找小於 pivot 的元素；
• 交換兩者；
• 指標交錯後，將 pivot 放到正確位置。

解題方法

原始序列為：

第 1 趟：整體序列，pivot = 55

左側尋找大於 $55$ 的元素：找到 $85$。
右側尋找小於 $55$ 的元素：找到 $15$。
交換 $85$ 與 $15$：

指標交錯後，將 pivot $55$ 與左側最後一個不大於它的元素 $15$ 交換：

此時 $55$ 已位於最終位置。

第 2 趟：左子序列，pivot = 15

左子序列為：

其餘元素皆大於 $15$，因此 pivot $15$ 已在正確位置，序列不變：

接著處理 $15$ 右側的子序列：

第 3 趟：子序列 $45,25,35$，pivot = 45

左指標掃描 $25$、$35$，兩者皆小於 $45$；指標交錯後，將 $45$ 與 $35$ 交換：

此時 $45$ 定位完成。

第 4 趟：子序列 $35,25$，pivot = 35

$25 < 35$，因此 pivot $35$ 已可定位，序列不變：

再排序子序列 $25$，其長度為 $1$，不需處理。左半部完成為：

第 5 趟：右子序列，pivot = 95

目前右子序列為：

左指標找到大於 $95$ 的 $105$；右指標找到小於 $95$ 的 $85$。交換：

指標交錯後，將 pivot $95$ 與 $85$ 交換：

此時 $95$ 定位完成。

第 6 趟：子序列 $85,65,75$，pivot = 85

核心觀念

本題涵蓋以下觀念：

• 排序演算法的時間複雜度與整數值域大小。
• DFS 在 adjacency matrix 上的複雜度。
• 動態規劃與最短路徑 DAG 的對應條件。
• 多項式歸約的方向與 NP-hard 定義。
• Ford–Fulkerson 演算法中增廣路徑的選擇與複雜度。

(1) Counting Sort

判斷：錯誤

Counting Sort 的時間複雜度不是單純的 $O(n)$，而是

其中 $k$ 是輸入整數的值域大小。例如所有元素介於 $0$ 到 $k$ 之間，則需要配置長度為 $k+1$ 的計數陣列。

題目聲稱「running time is polynomial in the input size $n$」，但若 $k$ 遠大於 $n$，例如：

此時 $n=2$，但 Counting Sort 仍可能需要處理大小約為 $10^9$ 的值域，因此時間與空間都不一定是 $n$ 的多項式。

正確敘述

Counting Sort 的時間複雜度為

只有在 $k$ 為 $n$ 的多項式，例如 $k=O(n)$ 時，才能說其複雜度是輸入大小 $n$ 的多項式。

(2) Heap Sort

判斷：正確

Heap Sort 的主要步驟如下：

1. 建立 Max Heap，時間為 $O(n)$。
2. 重複取出最大值並維護 Heap，共執行 $n$ 次。
3. 每次 Heapify 的時間為 $O(\log n)$。

因此總時間為

$O(n\log n)$ 顯然是 $n$ 的多項式，因此題目敘述正確。

補充

Heap Sort 的最壞、平均、最佳時間複雜度皆為

且額外空間為 $O(1)$，因此它也是原地排序演算法。

(3) DFS 使用 Adjacency Matrix

判斷：正確

使用 adjacency matrix 表示圖 $G=(V,E)$ 時，每個頂點都對應矩陣中的一列。DFS 訪問某個頂點 $u$ 時，需要掃描整列：

也就是檢查 $|V|$ 個可能的鄰居。

由於每個頂點最多被完整掃描一次，總時間為

因此不論實際邊數 $E$ 為何，使用 adjacency matrix 執行 DFS 的時間複雜度都是

題目敘述正確。

補充

若圖使用 adjacency list，DFS 的時間複雜度則為

因此：

• adjacency matrix：$O(V^2)$
• adjacency list：$O(V+E)$

(4) 動態規劃與最短路徑 DAG

判斷：錯誤

並非每一個 dynamic program 都能轉換成 shortest path problem。

最短路徑 DAG 的典型遞迴形式是：

也就是：

• 從所有前置狀態中取最小值。
• 每個轉移只是在前一狀態加上一個邊權重。

然而，一般動態規劃可能使用加法、乘法、最大值、布林運算等不同運算。例如 Fibonacci：

這是兩個子問題結果的「相加」，並非最短路徑所要求的「取最小值加邊權」。

正確敘述

只有當動態規劃的遞迴能寫成 min-plus 形式：

時，才可以直接對應到 DAG 上的最短路徑問題。

一般動態規劃都可以在「子問題相依關係形成的 DAG」上依拓撲順序計算，但不代表一定等價於最短路徑。

(5) 多項式歸約與 NP-hard

判斷：錯誤

題目的敘述是：

If a problem X can be reduced to a known NP-hard problem, then X must be NP-hard.

核心觀念

本題考查最大流（maximum flow）、最小割（minimum cut）、殘餘圖（residual graph）與瓶頸邊（bottleneck edge）。

依原卷圖形，邊為：

注意：原卷圖中為 $A\to D$ 與 $B\to C$，不是題幹文字列出的 $A\to B$ 與 $C\to D$。

最大流最小割定理指出：

(a) 最大流與最小割

可配置如下流量：

流量守恆成立：

• $A$ 流入 $6$，流出 $4+2=6$
• $B$ 流入 $5$，流出 $2+3=5$
• $C$ 流入 $4+2=6$，流出 $6$
• $D$ 流入 $2+3=5$，流出 $5$

因此流值為：

考慮割：

由 $X$ 指向 $\overline X$ 的邊為：

其容量為：

所以此割容量為 $11$。因為已找到流值 $11$ 且存在容量為 $11$ 的割，依最大流最小割定理：

最小割可取：

割邊為：

(b) 殘餘圖

殘餘圖規則：

• 正向剩餘容量為 $c-f$
• 若流量 $f>0$，加入反向邊，容量為 $f$

依上述流量配置，殘餘邊如下：