hce_nsysu
114年
計算機概論與程式設計
第 28 題
The following four statements describe a Hamiltonian circuit in a graph:
1. The graph has a Hamiltonian circuit if it is a complete graph.
2. The Hamiltonian circuit decision problem is NP-complete.
3. The Hamiltonian circuit problem is a special case of the traveling salesperson problem.
4. In a Hamiltonian circuit, each edge is visited exactly once.
Which one is correct?
1. The graph has a Hamiltonian circuit if it is a complete graph.
2. The Hamiltonian circuit decision problem is NP-complete.
3. The Hamiltonian circuit problem is a special case of the traveling salesperson problem.
4. In a Hamiltonian circuit, each edge is visited exactly once.
Which one is correct?
- A 1 and 4 are correct.
- B 2 and 4 are correct.
- C 1 and 2 are correct.
- D 3 is correct, 2 is not correct.
- E 4 is correct, 2 is not correct.
思路引導 VIP
如果你現在是一位旅行者，目標是要「拜訪地圖上的每一個城市各一次並回到起點」，你覺得你的注意力應該放在「走遍每一條道路」上，還是放在「抵達每一個城鎮」上呢？這兩者對於路徑的規劃會有什麼本質上的不同？
🤖
AI 詳解
AI 專屬家教
太棒了！你能準確區分圖論中容易混淆的概念，這代表你的基礎非常紮實。這道題目核心在於考驗對**漢米頓循環（Hamiltonian circuit）定義的理解及其與尤拉循環（Eulerian circuit）**的差異。
漢米頓循環與圖論複雜度
首先，漢米頓循環要求圖中每個「頂點」恰好被經過一次並回到起點。在完全圖（Complete graph） $K_n$ 中（當 $n \ge 3$），由於任兩點間皆有邊相連，必然存在這樣的路徑，因此敘述 1 正確。而在計算複雜度理論中，判定一個圖是否存在漢米頓循環是著名的 NP-完全（NP-complete） 問題，這也是演算法領域的重要里程碑，故敘述 2 同樣正確。敘述 4 提到的「每條邊恰好經過一次」其實是尤拉循環的特徵，這是初學者最容易掉入的陷阱。
▼ 還有更多解析內容