Algorithmics (演算法) Fall 2016

Lecturer: 江振瑞
Teaching Assistants (TAs): 吳宗勳林育勳鍾偉勝林廷諭李睿恩陳韋儒曾翊銘
Time: 週二 14:00~16:50
Place: A204
TA Class: 週二 13:00~13:50
Scoring：

期中考(分析與設計概念)(20%)
期末考(分析與設計概念)(25%)
程式設計作業、報告、課程參與度及程式設計競賽成績(55%)

TextBook:

My Book's Manuscript (book1-6.zip)
Introduction to the Design and Analysis of Algorithms -- A Strategic Approach (2/e), R.C.T. Lee et. al., McGraw Hill, 2005.
Introduction to Algorithms (3/e), Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein, MIT Press, 2009.

Reference Books:

Algorithm Design: Foundations, Analysis, and Internet Examples, Michael T. Goodrich, Roberto Tamassia, Wiley, 2002. (有中譯本)
Computer Algorithms, Ellis Horowitz et. al., Silicon Press, 2008.
中文Java程式設計 (第三版) SIM-908A , 江振瑞著, 儒林出版社, 2006.
物件導向資料結構 — 使用Java語言, 江振瑞著, 松崗圖書公司, 2005.
Algorithms, S. Dasgupta, C. Papadimitriou and U. Vazirani, McGraw Hill, 2008.
Programming Challenges, Steven S. Skiena and Miguel Revilla, Elsevier, 2003.
The Algorithm Design Manual, Steven S. Skiena, Elsevier.

Syllabus:

1. 認識演算法 -- 從食譜到高階程式語言: (Alg-Intro.pptx)

.1 演算法名稱的由來
.2 什麼是演算法?
.3 演算法的例子
.4 如何表示演算法?
.5 如何實作演算法? (EuclidGCD.c)(EuclidGCD.cpp)(EucidCGDClass1.java)

(EucidCGDClass.java)

(EuclidGCD.py)
.6 演算法的正確性

Homework1: (9/20; Due day: 9/27 before TA's class)

(A)

使用虛擬瑪(pseudo code)寫一個演算法，輸入一個整數n(n>2)並輸出小於n的最大因數(factor) (Write an algorithm using the pseudo code to input an integer n and output the n's largest factor that is less than n.)

(B)

使用虛擬瑪(pseudo code)寫一個演算法，輸入一個整數n(n>2)並輸出所有n除了本身以外的正因數(factor)總和 (Write an algorithm using the pseudo code to input an integer n and output the total summation of all n's factors except n.)
(C) 使用虛擬瑪(pseudo code)寫一個演算法，輸入整數n及m(n>m>2)，輸出所有比n小並大於m的n的因數(factor)總和，若無此因數則輸出0 (Write an algorithm using the pseudo code to input integers n and m, and output all n's factors larger than m and less than n.)
(D) 使用虛擬瑪(pseudo code)寫一個演算法，輸入一個整數n並判斷n是否為完美數(perfect number) (Write an algorithm using the pseudo code to input an integer n and output (decide) if n is a perfect number.)
(E) 使用虛擬瑪(pseudo code)寫一個演算法，輸入一個整數n(n>0)並判斷n是否為快樂數(happy number) (Write an algorithm to input an integer n and output (decide) if n is a happy number.)
註: 快樂數有以下的特性：在給定的進位制下，該數字所有數位(digits)的平方和，得到的新數再次求所有數位的平方和，如此重複進行，最終結果必為1。例如，以十進位為例：
28 → 2²+8²= 68 → 6²+8²=100 → 1²+0²+0²=1，因此28是快樂數
(F) 使用虛擬瑪(pseudo code)寫一個演算法，以輸入一個具有n個元素的集合S並輸出S的幂集(pwoer set) (Write an algorithm to input a set S of n elements and output the power set of S.)

2. 演算法複雜度分析範例(以排序演算法為例)(Alg-Analysis.pptx)
.1 演算法的效能
.2 演算法的時間複雜度
.3 大O漸進記號
.4 降低演算法時間複雜度量級
.5 漸進記號(asymptotical notation): Big O, Big Omega, Theta
.6 多項式時間、指數時間及偽多項式時間演算法

.7 氣泡排序(bubble sort)演算法

.8 插入排序(insertion sort)演算法

Problem Set 2:
(A) 在氣泡排序(bubble sort)演算法中，若在某回合中完全沒有任何資料對調，則可推論資料已經排序完成而立即結束演算法執行，這稱為改良

氣泡排序(improved bubble sort)演算法。請

以虛擬碼描述

「改良

氣泡排序演算法」。(請注意:在有些文獻中，所謂「氣泡排序

演算法」其實指的是「

改良

氣泡排序演算法」)

(B) 分析

改良

氣泡排序演算法最佳、最差與平均

時間複雜度

Programming Problem Set 2
(PA) 寫一個程式實作基數排序演算法

3. 分治(divide-and-conquer)演算法: (Alg-Divide&Conquer.pptx) (10/11)

若是問題規模(problem size)夠小，就直接解決之；反之，若問題規模較大，就將其分割(divide)成兩個或多個子問題(分割階段)，然後將每個子問題遞迴地(recursively)征服(conquer)解決之(征服階段)。之後再將每個子問題的解答合併(merge)，使其成為原問題的解答(合併階段)。
3.1 合併排序(merge sort)演算法 (屬分治演算法)
3.2 快速排序(quick sort)演算法 (屬分治演算法)

3.3 分治缺陷棋盤填滿(tiling a defective chessboard)演算法
3.4 分治二維求秩(2D rank finding)演算法
3.5 分治二維最大點(2D maxima finding)演算法
3.6 分治最近二維點對(closest pair of 2D points)演算法
Problem Set 3:
(A) 舉出一個方法讓快速排序(quick sort)演算法避免產生最壞狀況。
(B) 寫一個分治演算法來解決一個給定數值集合的求秩(rank finding)問題，並進行複雜度分析。
(C) 寫一個分治演算法來找出一群在X軸上的點中的最近點對(closest pair of points on X-axis)，並進行複雜度分析。
(D) 畫出n log n、n log² n及n²圖形(n=2, 4, 8, ..., 128)並比較之。
(E) 說明如何使用預先排序(pre-sorting)於分治最近二維點對 (closest pair of 2D points)演算法。
3.7 最大連續子序列和(Maximum Contiguous Subsequence Sum, MCSS)演算法 (MCSS.zip) (10/18)

4. 刪尋(prune-and-search)演算法: (Alg-Prune&Search.pptx) (10/18)
刪尋(prune-and-search)演算法包含多次迭代 (iteration)，在每一次的迭代中，均刪除(prune)輸入資料的一部分(假設為f部份, 0<f<1)，而後再遞迴地(recursively)以相同的演算法在剩餘的資料中搜尋(search)出解答。在經過一定次數的迭代後，輸入資料的規模將會變得相當小，而能在常數時間內直接找出解答。
假設一個刪除-搜尋演算法的時間複雜度為T(n)，並且每次迭代所需的時間為O(n^k)(k為大於0的常數)，則T(n)=T((1-f)n)+O(n^k)。由於 1-f<1，我們可得T(n)=O(n^k)。

4.1 二元搜尋(binary search)演算法
4.2 選取(selection)與中位數(median)演算法
4.3 限制的一圓心(constrained 1-center)演算法
4.4 簡化的二變數線性規劃(simplified 2-variable linear programming)演算法
Problem Set 4:
(A) 仿照merge sort的執行過程範例說明方式，畫圖說明S=(-2, 1, -3, 4, -1, 2, 1, -5)使用最大連續非空子序列和分治演算法(MCSS演算法)」的執行過程。
(B) 仿照merge sort的執行過程範例說明方式，畫圖說明S=(-2, -1, -3, -4, -1, -2, -1, -5)使用最大連續可空子序列和分治演算法(MCSS演算法)」的執行過程。
(C) 在選取刪尋演算法中，若每個分割子集改為3個元素，則其最壞狀況時間複雜度是否依然為O(n)，為什麼?
(D) 在選取刪尋演算法中，將每個分割子集改為6個元素後重新分析其時間複雜度。
(E) 有一個刪尋演算法其時間複雜度為T(n)=T((7/8)n)+cn²，詳細分析其時間複雜度並以大O記號表示。

5. 貪婪演算法(greedy algorithm): (Alg-Greedy.pptx) (10/25)
貪婪演算法(greedy algorithm)一步步地建構出一個問題的完整解答。其每一步都藉由貪婪解題策略(greed strategy)增加一部份的解答到完整解答中。所謂貪婪解題策略為: 每一次都選擇當下最好的部份解答加入完整解答中。
5.1 背包演算法(knapsack algorithm) (帶出0/1背包問題後可以在之後講授NP-hard問題)
5.2 Huffman編碼演算法
5.3 Kruskal最小含括樹(minimum spanning tree, MST)演算法
5.4 Prim最小含括樹(minimum spanning tree, MST)演算法
5.5 Dijkstra最短路徑演算法
Problem Set 5:
(A) 以刪尋演算法解決以下限制的一圓心問題: (0,0),(1,1),(2,2),(3,3),(4,2),(5,1),(6,0),(2,0)，圓心在y=0上。(可以精確繪圖說明即可)
(B) 以刪尋演算法解決以下限制的一圓心問題: (0,0),(1,1),(2,2),(3,3),(4,2),(5,1),(6,0),(4,0)，圓心在y=3上。(可以精確繪圖說明即可)
(C) 一個背包容量為10，現在有5個物品，重量分別為4、3、6、2、5，價格分別為10、9、 12、4、8，求背包能夠裝入零碎(fractional)物品的最大價值為何?

(D) 分別利用Kruskal's演算法與Prim's演算法求出以下圖(graph)的最小生成樹 (minimum spanning tree, MST)

(E) 利用Huffman 編碼演算法替以下字元編碼A(42%)、B(17%)、C (28%)、D (13%)。(備註:括號中為字元出現頻率)
(F) 利用Dijkstra演算法求以下圖(graph)頂點4到各頂點的最短路徑(shortest path)距離(成本)
Introduction to Software Defined Networking (SDN) Multicast (SDN-Multicast.pptx) (10/25)

6. 動態規劃(dynamic programming)演算法: (Alg-DP.pptx) (11/1)
動態規劃(dynamic programming)演算法籍由將原問題分解成一系列子問題 (subproblems)，並依序解決子問題來解決原問題。為避免一再地解重複的子問題，一旦解出子問題的解答(solution)，即會將其存在表格(或陣列)中。當需要用到某一子問題的解答時，與其重新計算其解答，演算法會取而代之地從表格中直接取出其解答以節省計算時間，是一個「以空間換取時間」的演算法。一個動態規劃演算法會先從最簡單的子問題先解起，並以一定的程序持續運行直至求出原問題解答為止。

最佳解原則(Principle of optimality): 假設為了解決一個問題，我們必須作出一系列的決策 D1, D2, …, Dn。若這一系列的決策是最佳解，則針對於前n-k個(或最後n-k個)決策所產生的狀態(子問題)而言，最後的k個(或前k個)決策(1<= k<=n)必定也是最佳的。

6.1 最長共同子序列(longest common subsequence, LCS or LCSS)演算法
6.2 0/1背包動態規劃演算法(0/1 knapsack dynamic programming algorithm)
6.3 Bellman-Ford最短路徑演算法
6.4 Floyd-Warshall最短路徑演算法

Problem Set 6:

A. 畫圖說明利用利用Floyd-Warshall演算法求以下圖(graph)全對最短路徑(all-pair shortest path)距離(成本)(此圖的啟始距離矩陣如下，以經過的中間節點為s, a, b, c, d的順序寫出距離矩陣的改變過程。)
(d->b的加權在圖形與表格中誤植為不一致的值，同學可以將之改為5或6讓圖形與表格一致後解題都算答對。)

B. 求出以下給定圖(graph)的Floyd-Warshall演算法的啟始前節點矩陣(陣列)，並求出最後的前節點矩陣(陣列)。

C. 以下是Floyd-Warshall演算法針對具有五個節點(記為1、2、3、4、5)的圖產生的前節點矩陣(陣列)，說明如何藉以找出節點1到節點3的最短路徑，及節點5到節點2的最短路徑。

D. 針對以下的給定圖，列出Bellman-Ford最短路徑演算法執行過程，說明Bellman -Ford最短路徑演算法如何檢查出一給定圖具有負循環(negative-weight cycle)。

E. 說明X=ABCBA與Y=BDCA兩個字串藉由動態規劃演算法求出最長共同子序列的過程
F. 給定一個0/1背包問題如下；背包荷重W=12，且4個物品其重量各為6、4、5、3，其價值各為20、30、40、10，說明藉由動態規劃演算法解決此0/1背包問題的過程。

(圖形相關演算法複雜度比較)

期中考: (時間: 11/8 下午2:00-3:50)(範圍: 已授課的部份)(參考講義: book1-8.zip)
7. (11/22) 再探動態規劃演算法(dynamic programming algorithm revisited): (PDA-2.pptx)
最大連續子序列和(maximum contiguous subsequence sum, MCSS)動態規劃演算法
矩陣鏈乘積(matrix-chain product)動態規劃演算法
最佳二元搜尋樹動態規劃演算法
子集合加總動態規劃演算法
多項式及偽多項式時間
Problem Set 7
A. 如何將「最大連續非空子序列和動態規劃演算法」修改為「最大連續可空子序列和動態規劃演算法」?
B. 藉由動態規劃演算法來替一矩陣鏈(其維度序列為 <5, 20, 10, 12> )加上括號來最佳化矩陣相乘次數。
C. 以子集合加總動態規劃演算法解決以下子集合加總問題: 給定整數集合S={1, 2, 4, 7}及整數c=10。
D. 給定p1=0.2, p2=0.15, p3=0.3; q0=0.1, q1=0.08, q2=0.07, q3=0.1,以最佳二元搜尋樹動態規劃演算法建構出最佳二元搜尋樹。
E. 修改子集合加總動態規劃演算法使其傳回加總值為c的子集合若此子集合存在；否則傳回空集合。
F. 以下列之動態規劃演算法解決以下多階圖最短路徑問題，請注意，多階圖中邊的加權修改如下: AD改為11；AE改為4；ET改為2；FT改為13。
8. (11/29) Evolutionary Algorithms and AR (Augmented Reality) (ITNAC2016.pptx)(SmartCity2016.pptx)

9. MOOCs (演算法基礎與應用)(Youtube video: https://youtu.be/jon0-ouFtYI)
(12/6之前觀看影片，12/6繳交習題與實習報告) 樹搜尋(tree search)與回溯(backtracking)演算法: (Alg4-1203(NoMark).pptx)(更正: 投影片第36和37頁樹第三層右邊的三個節點由左而右依序為"2' "4' "5") (Youtube video:https://youtu.be/mM93FheJEGQ)
*許多問題的尋找解答過程可以使用樹 (tree)來表達，這類問題也都可以建構出解答空間樹(solution space tree)。因此要找到這些問題的解答，不管是可行解(feasible solution)或是最佳解(optimal solution)，就轉變成一個樹搜尋(tree search)問題。
*有許多方法可以拜訪(visit)與拓展(expand)一個解答空間樹，包括深度優先搜尋(depth-first search, DFS)、廣度優先搜尋(breadth- first search, BFS)、登山搜尋(hill climbing search, HCS)以及最佳優先搜尋(best-first search)等演算法。
.1 廣度優先搜尋(breadth-first search, BFS)演算法
.2 深度優先搜尋(depth-first search, DFS)演算法
.3 登山搜尋法(hill climbing search, HCS)演算法
.4 最佳優先搜尋法(best-first search)演算法
.5 回溯(backtracking)演算法
Problem Set 8: (12/6下午2:00習題課前繳交)
A. 給定一集合S={7, 4, 1, 2, 11}以及一加總值10，利用深度優先搜尋法來解子集合加總問題，你必須畫出解出問題的解答空間樹(solution space tree)。
B. 以深度優先搜尋演算法找出以下圖(graph)的漢米爾頓迴路 (Hamiltonian circuit)，你必須畫出解出問題的解答空間樹(solution space tree)。

C. 以廣度優先搜尋演算法找出上圖的漢米爾頓迴路，你必須畫出解出問題的解答空間樹(solution space tree)。
D. 以空單格的移動方向為上下左右的次序，以廣度優先搜尋演算法下解決以下的八拼圖(8- puzzle)問題。
起始狀態:

2		3
1	8	4
7	6	5

目標狀態:

1	2	3
8		4
7	6	5

E. 以空單格的移動方向為上下左右的次序，以深度優先搜尋演算法解決D題中的八拼圖(8- puzzle)問題。
F. 以空單格的移動方向為上下左右的次序，以登山搜尋演算法解決D題中的八拼圖(8-puzzle)問題。而評估函數為方塊錯置的數目，若有相同的情形，則以空單格移動方向上下左右為其優先順序。
G. 以空單格的移動方向為上下左右的次序，以最佳優先搜尋演算法解決D題中的八拼圖(8-puzzle)問題。而評估函數為方塊錯置的數目，若有相同的情形，則以空單格移動方向上下左右為其優先順序。

10. (12/13之前觀看影片，12/13繳交習題與實習報告) 分支定界(Branch and Bound)演算法 (Branch&Bound.zip) (Youtube video Part1: https://youtu.be/KUlDxRV6fsU)(Youtube video Part2: https://youtu.be/R91wC81n6Yk)
*分支定界(branch and bound)是一個拜訪與拓展解答空間樹的特殊方法，用於找出問題的最佳解。其做法相當於找出一種方法來切割出解答空間的分支(branch)，然後以上界(upper bound)與下界(lower bound)的概念來加快最佳解的搜尋。
*對於尋找最小成本(minimum cost)解答的最佳化問題而言，分支定界演算法會針對每一分支的解答預測其成本下界(lower bound)，並利用找出可行解來得到問題的成本上界(upper bound)。如果有一個解答的成本下界超過問題成本上界，則這個解不可能是最佳的，因此演算法會中止(terminate)與這個解相關聯的整個分支的搜尋。
*而對於尋找最大利益(maximum benefit)解答的最佳化問題而言，分支定界演算法會針對每一分支的解答預測其利益上界(upper bound)，並利用找出可行解來得到問題的利益下界(lower bound)。如果有一個解答的利益上界低於問題利益下界，則這個解不可能是最佳的，因此演算法會中止(terminate)與這個解相關聯的整個分支的搜尋。
.1 基本概念
.2 分支定界演算法(配合登山搜尋法)解決多階圖最短路徑問題
.3 分支定界演算法(配合最佳優先搜尋法)解決旅行推銷員問題
.4 分支定界演算法(配合最佳優先搜尋法)解決0/1背包問題
.5 一個特殊的分支定界演算法: A*演算法
Problem Set 9: (12/13下午2:00習題課前繳交)
A. 以分支定界演算法解決以下多階圖最短路徑問題。

B. 給定一0/1背包問題，其背包可載重C=10,且有三物品的重量分別為10, 3, 5，而其利潤分別為40, 20, 30，求出可以放入背包中物品利潤的負值的最小化，使用分支定界演算法來解此0/1背包問題。（註: 必須畫出搜尋樹）(此題使用負的目標函數值，因此feasible solution是求出upper bound，而且我們不斷地嘗試降低upper bound)
C. 同上題，但目標改為求出可以放入背包中物品利潤的最大化，使用分支定界演算法來解此0/1背包問題。（註: 必須畫出搜尋樹）(此題使用正的目標函數值，因此feasible solution是求出lower bound，而且我們不斷地嘗試提高lower bound)
D. 使用A*演算法來解以下之多階圖最短路徑問題。（註: 必須畫出搜尋樹）

E. 將A題的S與T對調，箭頭反向解題。
F. 將B題所有成本乘以2減3解題。
G. 將C題的物品重量改為20, 5, 6解題。
H. 將D題的V0與V8對調，箭頭反向解由V8到V0的最段路徑問題。

11. (12/20) (下午13:00開始上課)
最小成本最大流量演算法(Minimum-Cost Maximum-Flow Alg., Min-Cost Max-Flow Alg., MCMF Alg.)(MCMF-New.zip)
應用實例 1: Paper: Yung-Liang Lai and Jehn-Ruey Jiang, "Sink-Connected Barrier Coverage Optimization for Wireless Sensor Networks," in Proc. of 2011 International Conference on Wireless and Mobile Communications (ICWMC 2011), 2011. (Slides)
應用實例 2: Paper: Yung-Liang Lai, and Jehn-Ruey Jiang, "Barrier Coverage with Optimized Quality for Wireless Sensor Networks," in Proc. of the 15th International Symposium on Wireless Personal Multimedia Communications Symposium (WPMC'12), 2012. (Slides)
應用實例 3: Jehn-Ruey Jiang, Guan-Yi Sung, and Jih-Wei Wu, "LOM: A Leader Oriented Matchmaking Algorithm for Multiplayer Online Games," in Proc. of International Conference on Internet Studies (NETs 2015), 2015. (Distinguished Paper Award)(LOM.ppt)

*匈牙利演算法(Hungarian Algorithm)(HungarianAlg.zip)(The algorithm will be taught if time is available.)
Problem Set 10:
A.以Ford-Fulkerson演算法 (搭配Hill-Climbing Search)解決以下最大流量問題(圖的有向邊(directed edge)上所標示的為容量(capacity))
MaximumFlow

B. 以Edmonds -Karp演算法解決以下最大流量問題(圖的有向邊(directed edge)上所標示的為容量(capacity))
C. 自行設計一個流網 (flow network)(除s、t外具有4個節點，並具有10個edge)，以Edmonds-Karp演算法解決其最大流量問題。
D. 完成投影片p30之Bellman-Ford演算法檢測負加權循環範例到iteration 8
E. 完成投影片p30之Bellman- Ford演算法檢測負加權循環範例到iteration 8，並加入predecessor註記
F. 說明如何detect投影片p30之負加權循環
(Optional, for Hangarian Algorithm)
A. 使用匈牙利演算法(Hungarian algorithm)來解以下的指派問題(assignment problem)（註: 必須寫出演算法執行過程中的每個中間結果）

	Task A	Task B	Task C
Tim	$1	$2	$3
Bob	$2	$3	$2
Alex	$2	$2	$3

B. 自行設計一個指派問題(assignment problem)的4x4成本矩陣，並以匈牙利演算法(Hungarian algorithm)找出最大權重完美二分匹配(Maximum-Weight Perfect Bipartite Matching)。
C. 說明如何使用匈牙利演算法(Hungarian algorithm)解決最小歐氏平面權重配對(Minimum Euclidean Weighted Matching)問題。所謂最小歐氏平面權重配對問題描述如下: 給定n個點(n為偶數)，如何將此n個點匹配形成n/2個點對，讓每個點對形成一條線段，而此n/2條線段具有最小的長度總和。
D. 隨意畫出四個歐氏平面點(2D point)，設其距離皆為整數(以公分計算)，以匈牙利演算法(Hungarian algorithm)找出其最小歐氏平面權重配對(Minimum Euclidean Weighted Matching)。
E. 說明如何將匈牙利演算法能夠解答的最小成本指派問題(assignment problem)變轉為(reduce to)最大流問題
F. 將以下最小成本指派問題(assignment problem)轉換為流網(flow network)，以便使用最大流(max-flow)演算法解決之

	Task 1	Task 2	Task 3
Carl	$24	$28	$24
Bob	$26	$32	$28
Alex	$24	$28	$30

12. (12/27) 問題下界與問題分類: P、NP、NP困難與NP完全問題*一個問題的下界為任何能解決此問題的演算法至少所需的時間複雜度。(The lower bound of a problem is the least time complexity required for any algorithm which can be used to solve this problem.) (ProblemLB.zip)
*NP完全問題理論: 若任何一個NP完全問題可在多項式時間被解決，則每一個NP問題皆可在多項式時間獲得解決(也就是P=NP)。 If any one NP-complete problem can be solved in polynomial time, then every problem in NP can also be solved in polynomial time (i.e., P=NP). (Recipe, Cook and Carp)(NPC.zip)
*(NPC理論測驗及解答)
Problem Set 11:
A. 證明支配集問題(dominating set problem)為NP問題。
B. 證明點覆蓋問題(vertex cover problem)為NP問題。
C. 證明集團問題(clique problem)為NP問題。
D. 證明著色問題(chromatic coloring problem)為NP問題。
E. 證明0/1 背包問題(0/1 knapsack problem)為NP問題。
F. 證明3-滿足問題(3-SAT problem)為NP問題。
G. 證明Steiner tree決策問題為NP問題。
13. (1/3)近似演算法 (Approximation algorithms) (ApproximationAlgorithm.zip)

EulerianTour.zip

From Wiki: URL: https://zh.wikipedia.org/wiki/%E4%B8%80%E7%AC%94%E7%94%BB%E9%97%AE%E9%A2%98
定理一
*連通的無向圖G有歐拉路徑的充要條件是： G中奇頂點（連接的邊數量為奇數的頂點）的數目等於0或者2。
*連通的無向圖G是歐拉環（存在歐拉迴路）的充要條件是： G中每個頂點的度都是偶數。

定理二
*一個連通的有向圖可以表示為一條從頂點 u到 v的（不閉合的）歐拉路徑的充要條件是： u的出度（從這個頂點發出的有向邊的數量）比入度（指向這個頂點的有向邊的數量）多1， v的出度比入度少1，而其它頂點的出度和入度都相等。
*一個連通的有向圖是歐拉環（存在歐拉迴路）的充要條件是：每個頂點的出度和入度都相等。

Problem Set 12:

A. 使用2-近似演算法

(2-approximation algorithm)

來解決

以下圖的

頂點覆蓋問題(vertex cover problem)。

（註: 須描述在執行演算法過程的每個中間結果。）

B. 使用歐拉旅途演算法來找出以下圖的歐拉旅途。（註: 須描述在執行演算法過程的每個中間結果。）

C. 將以自然語言撰寫的「無向圖歐拉旅途/路徑演算法」改為以虛擬碼撰寫
D. 以自然語言撰寫「有向圖歐拉旅途/路徑演算法」
E. 以虛擬碼撰寫「有向圖歐拉旅途/路徑演算法」
F. 分析兩個演算法的時間複雜度