图论中的汉密尔顿回路：零知识证明 Peggy 如何证明她知道 G 的汉密尔顿回路？

交互式零知识证明（Interactive Zero-Knowledge Proof，简称IZKP）是指证明者（Peggy）通过与验证者（Victor）的互动来证明自己知道某些信息，而不泄露这些信息的具体内容。

在图论的数学领域中，'Hamiltonian 路径' 是一个无向图中每个顶点只访问一次的路径。'Hamiltonian 回路' 是一个 'Hamiltonian 路径'，它以相同的顶点开始和结束。确定图中是否存在 'Hamiltonian 路径' 和 '回路' 是 NP 完全问题。

假设 Peggy 知道一个大图 G 的 'Hamiltonian 回路'，Victor 知道 G, 但不知道这个回路。Peggy 将证明她知道这个回路而不透露它。她怎样做？

Peggy 先选定一个随机的图 G'，并将其转化为哈密顿图（即包含一个哈密顿回路的图）。
Peggy 将 G' 的哈密顿回路分解为一些边的组合，比如将哈密顿回路分成两条路径并将它们拼接起来。
Peggy 将这些边的组合发送给 Victor，告诉他这些组合是哈密顿回路的一部分。
Victor 随机选择一个组合，并要求 Peggy 在 G 中展示这个组合对应的路径。如果这个组合确实是哈密顿回路的一部分，那么 Peggy 可以轻松地展示出对应的路径。
如果 Victor 对所有的组合都进行了检验，且 Peggy 都能够展示出对应的路径，那么 Victor 可以得出结论：Peggy 知道 G 的哈密顿回路的存在。
如果 Victor 想要验证这个结论，他可以要求 Peggy 再次进行 IZKP，但这一次 Peggy 需要使用 G 的哈密顿回路作为 G' 的哈密顿回路。如果 Peggy 仍然能够通过验证，那么 Victor 可以确认 Peggy 确实知道 G 的哈密顿回路的存在。

需要注意的是，IZKP 并不能证明 G 一定存在哈密顿回路，只能证明 Peggy 知道 G 的哈密顿回路的存在。如果 G 本身没有哈密顿回路，那么 Peggy 也无法找到一个哈密顿回路来进行 IZKP。