知识卡片

普通读书笔记卡 · 3714.c

哈密顿环证书是顶点顺序

理解等级:中级

哈密顿环须经过图中每个顶点恰好一次并闭合。

给出顶点顺序后,验证者可检查它是全体顶点的排列且相邻边与首尾边都存在;验证高效,不意味着可高效找到该顺序。

这张卡片看不懂?

已有反馈 · 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

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[35000,40000))。 - 结论依据:原文§34.1–34.2的编码、形式语言、验证定义及证明;章末练习不作已解结论。 - 原始内容: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 ( n 2 ) 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