知识卡片
哈密顿环证书是顶点顺序
哈密顿环须经过图中每个顶点恰好一次并闭合。
给出顶点顺序后,验证者可检查它是全体顶点的排列且相邻边与首尾边都存在;验证高效,不意味着可高效找到该顺序。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
Verification algorithms Consider a slightly easier problem. Suppose that a friend tells you that a given graph G is hamiltonian, and then the friend offers to prove it by giving you the vertices in order along the hamiltonian cycle. It would certainly be easy enough to verify the proof: simply verify that the provided cycle is hamiltonian by checking whether it is a permutation of the vertices of V and whether each of the consecutive edges along the cycle actually exists in the graph. You could certainly implement this verification algorithm to run in O(n2) time, where n is the length of the encoding of G. Thus, a proof that a hamiltonian cycle exists in a graph can be verified in polynomial time. We define a verification algorithm as being a two-argument algorithm A, where one argument is an ordinary input string x and the other is a binary string y called a