趣题:一个与Hamilton回路有关的问题

    今天在回访网站流量来源时看到了一个很牛B的东西,和大家分享一下。
    给定一个顶点数为100000的图G,问是否存在Hamilton回路。现在,A宣称自己已经找到了一个Hamilton回路,但B不信,要A证明给他看。你能否想出一个办法使得,A可以让B相信自己有了正确的答案,但B依然不知道答案是什么。这种方法既科学又有趣,整个过程不需要第三者参与,仅仅靠AB两人之间的交流即可。这种方法可以让B有充分的理由相信A找到了Hamilton回路,但能保证B仍然得不到任何与正确答案有关的线索。

    首先,A生成一个100000的全排列P,然后用这个排列P把原图G的顶点标号打乱(对标号进行置换),这样就得到了一个同构的图G'。然后A把图G'告诉给B。注意,目前判断两个图是否同构还没有有效的P算法,因此除非A把排列P也告诉了B,否则B不知道G'和G是不是真的同构。接下来B从下面这两个问题中随机抽一个问题让A作答:叫A证明G与G'同构(即叫A给出排列P,确保他没有作假),或者叫A指出G'中的一条Hamilton回路。反复进行“构造G'—抽问”的过程,每次A答对后B都会更加确信A确实找到了原图G的Hamilton回路,来个十几二十次后A作假的嫌疑基本上可以被排除了。这是因为,如果A不知道原图G中的Hamilton回路,这两个问题他是不可能同时答对的,既然B是抽查的,A不可能每次总能答对。同时,除非B同时知道了两个问题的答案,否则B永远不知道原图G的Hamilton回路是什么。仅仅知道G'的Hamilton回路是没有用的,因为此时B连G和G'是否同构都不知道,更别提找出它们之间的对应关系了。

来源:http://www.zju88.cn/cgi-bin/bbstcon?board=Algorithm&file=M.1200769543

发表评论

25  +    =  30