交大115 資料結構與演算法第16題｜演算法 Ch5 NP Complete Problems

演算法›Ch5 NP Complete Problems

第 12 題／共 30 題

12. Hamiltonian Cycle、NP-Complete、Tractability

#AL-05-012中Hamiltonian CycleNP-CompleteTractability

5% Given a graph $G=(V,E)$ , to answer whether there is Hamiltonian Cycle in $G$ is NP-Complete. Do you think the function $f(G,u,v,k)$ is tractable? The function $f$ returns yes if there is a path of length $k$ from $u$ to $v$ in $G$ , otherwise it returns no. If you think it is tractable, give me your reasons, or try to argue that the function $f$ is not tractable.

📄 交大115

▤完整推導請見《WH 資工筆記 · 演算法》Ch5 NP Complete Problems

本章題號 · 1–20 / 30