免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

乌拉姆猜想的证明

乌拉姆猜想的证明
作者:周崭
(西安市城开城源物业公司,陕西 西安 710068)
关键词:同构;一一对应;顶点;边;弧
中图分类号:O157.5  
摘  要:在图论中,论文采用初等的方法(“四项直接连接复制操作”、 “直接连接缩小变换”等),对任意有限图(无向图、有向图、简单图、复杂图等),证明了“乌拉姆猜想”
乌拉姆猜想:设G和H为两个图,|V(G)|=|V(H)|,记V(G)={u1,u2,u3,…,un}, V(H)={v1,v2,v3,…,vn},n>2,且G-ui≌H-vi(i=1,2,3,…,n),则G≌H。
(注:在下面的证明中,为叙述方便,除非特别声明,凡涉及到变量i和j,我们设定i=1,2,3,…,n。j=1,2,3,…,n且j≠i;另外,凡是针对弧的描述或操作,都是按照弧的两种方向分别进行考虑的)
证明:
我们分别建立两个各自有n个孤立顶点的图G′和H′,|V(G′)|=|V(H′)|=|V(G)|=|V(H)|,V(G′)={u1′,u2′,u3′,…,un′}, V(H′)={v1′,v2′,v3′,…,vn′},根据同构的定义,显然  G′≌ H′。
    规定:ui′与ui、vi′与vi分别建立一一对应的关系。
     我们将按i=1、i=2、i=3、…、i=n的顺序依次(每一个i值算一次,共n次)同时对G-ui和G′、H-vi和H′每次执行下面的“四项直接连接复制操作”:
第一项:将G-ui中每个含有环的顶点uj 所有的环全部复制到G′中按“规定”一一对应的顶点uj′上。
第二项:将G-ui中含有直接连接的每对顶点uj和uk(j=1,2,3,…,n。k=1,2,3,…,n。j≠k≠i。)之间所有的边(无向图)或弧(有向图)全部复制到G′中按“规定”一一对应的每对顶点uj′和uk′(j=1,2,3,…,n。k=1,2,3,…,n。j≠k≠i。)上。(注:针对“弧”的复制操作,要求严格保证其方向的一致性)
第三项:将H-vi中每个含有环的顶点vj所有的环全部复制到H′中按“规定”一一对应的顶点vj′上。
第四项:将H-vi中含有直接连接的每对顶点vj和vk(j=1,2,3,…,n。k=1,2,3,…,n。j≠k≠i。) 之间所有的边(无向图)或弧(有向图)全部复制到H′中按“规定”一一对应的每对顶点vj′和vk′(j=1,2,3,…,n。k=1,2,3,…,n。j≠k≠i。)上。(注:针对“弧”的复制操作,要求严格保证其方向的一致性)
显然,根据前面我们对G′和 H′的初始建立状态和同构的定义,知:初始的G′≌初始的 H′,又因为: G-ui≌H-vi ,所以每执行完成一次上述“四项直接连接复制操作”后,所生成的新的G′和新的 H′也同构。以此类推,当执行完成全部共n次“四项直接连接复制操作”后,最终生成的的G′和 H′也同构。
首先,当执行完成全部共n次“四项直接连接复制操作”后,我们先针对G和G′进行分析、总结如下:
分析一:对于G中任意一个顶点ui,当执行G-ui和G′之间的“四项直接连接复制操作”时,我们来分析ui自己及ui与其它所有不同顶点之间直接连接的复制情况。
当执行G-ui和G′之间的“四项直接连接复制操作”时,因为ui被清除,所以G中ui 自己所有的环(若有的话)没有复制到G′中按“规定”一一对应的ui′上,在这里记为“ui缺少一次环复制”。同时,G中ui与G中其它每一个uj之间直接连接的所有的边(无向图)或弧(有向图)也同样没有复制到G′中按“规定”一一对应的ui′和uj′上,所以,在这里记录一次“ui缺少一次边(无向图)或弧(有向图)复制”。
分析二:对于G中任意一个顶点ui,当执行G-uj和G′之间的“四项直接连接复制操作”时,我们来分析ui自己及ui与uj之间直接连接的复制情况。
当执行G-uj和G′之间的“四项直接连接复制操作”时,G中ui 所含有的环正常复制到G′中按“规定”一一对应的ui′上,但是,因为uj被清除,所以G中ui与G中uj这两个顶点之间直接连接的所有的边(无向图)或弧(有向图)没有复制到G′中按“规定”一一对应的ui′和uj′上。以此类推,当完成所有的共n-1次‘G-uj和G′的“四项直接连接复制操作”’后(不含G-ui),也相当于“G中ui与G中其它每一个uj之间直接连接的所有的边(无向图)或弧(有向图)总体上有一次没有复制到G′中按“规定”一一对应的ui′和uj′上”,所以,在这里再记录一次“ui缺少一次边(无向图)或弧(有向图)复制”。
分析三:在G中,如果某个顶点不含环,在G′中其按“规定”一一对应的顶点也就不含环。在G中,如果某两个顶点之间没有边(无向图)或弧(有向图)的直接连接,在G′中其按“规定”一一对应的某两个顶点之间也就没有边(无向图)或弧(有向图)的直接连接。
总结:综合上面针对“G-ui和G′”的分析,由于ui和uj的任意性,我们发现:当按序完成全部共n次“四项直接连接复制操作”后,最终生成的G′中含有环的每一个顶点所含有的环数分别是G中按“规定”一一对应顶点所含有的环数的n-1倍(注:总体上,G中含有环的每个顶点的环缺少一次向G′中按“规定”一一对应顶点复制)。另外,最终生成的G′中含有直接连接的任意两个不同顶点之间直接连接的所有的边(无向图)或弧(有向图)数是G中按“规定”一一对应顶点直接连接的所有的边(无向图)或弧(有向图)数的n-2倍(注:因为,对于邻接的两个顶点ui和uj来说,交错共享它们之间缺少的两次直接连接复制,所以,总体上,G中含有直接连接的两个不同顶点之间直接连接的所有的边(无向图)或弧(有向图)缺少二次向G′中按“规定”一一对应顶点复制)。
其次,当全部完成n次“四项直接连接复制操作”后,我们对H和H′进行分析、总结如下:(注:类似于上面对G和G′的分析)
分析一:对于H中任意一个顶点vi,当执行H-vi和H′之间的“四项直接连接复制操作”时,我们来分析vi自己及vi与其它所有不同顶点之间直接连接的复制情况。
当执行H-vi和H′之间的“四项直接连接复制操作”时,因为vi被清除,所以H中vi 自己所有的环(若有的话)没有复制到H′中按“规定”一一对应的vi′上,在这里记为“vi缺少一次环复制”。同时,H中vi与H中其它每一个vj之间直接连接的所有的边(无向图)或弧(有向图)也同样没有复制到H′中按“规定”一一对应的vi′和vj′上,所以,在这里记录一次“vi缺少一次边(无向图)或弧(有向图)复制”。
分析二:对于H中任意一个顶点vi,当执行H-vj和H′之间的“四项直接连接复制操作”时,我们来分析vi自己及vi与vj之间直接连接的复制情况。
当执行H-vj和H′之间的“四项直接连接复制操作”时,H中vi 所含有的环正常复制到H′中按“规定”一一对应的vi′上,但是,因为vj被清除,所以H中vi与H中vj这两个顶点之间直接连接的所有的边(无向图)或弧(有向图)没有复制到H′中按“规定”一一对应的vi′和vj′上。以此类推,当完成所有的共n-1次‘H-vj和H′的“四项直接连接复制操作”’后(不含H-vi),也相当于“H中vi与H中其它每一个vj之间直接连接的所有的边(无向图)或弧(有向图)总体上有一次没有复制到H′中按“规定”一一对应的vi′和vj′上”,所以,在这里再记录一次“vi缺少一次边(无向图)或弧(有向图)复制”。
分析三:在H中,如果某个顶点不含环,在H′中其按“规定”一一对应的顶点也就不含环。在H中,如果某两个顶点之间没有边(无向图)或弧(有向图)的直接连接,在H′中其按“规定”一一对应的某两个顶点之间也就没有边(无向图)或弧(有向图)的直接连接。
总结:综合上面针对“H-vi和H′”的分析,由于vi和vj的任意性,我们发现:当按序完成全部共n次“四项直接连接复制操作”后,最终生成的H′中含有环的每一个顶点所含有的环数分别是H中按“规定”一一对应顶点所含有的环数的n-1倍(注:总体上,H中含有环的每个顶点的环缺少一次向H′中按“规定”一一对应顶点复制)。另外,最终生成的H′中含有直接连接的任意两个不同顶点之间直接连接的所有的边(无向图)或弧(有向图)数是H中按“规定”一一对应顶点直接连接的所有的边(无向图)或弧(有向图)数的n-2倍(注:因为,对于邻接的两个顶点vi和vj来说,交错共享它们之间缺少的两次直接连接复制,所以,总体上,H中含有直接连接的两个不同顶点之间直接连接的所有的边(无向图)或弧(有向图)缺少二次向H′中按“规定”一一对应顶点复制)。
综合上述,当完成全部共n次“四项直接连接复制操作”后,最终生成的的G′和 H′也同构,令:G″= 最终生成的G′ ,H″=最终生成的 H′,即得:G″≌H″。
下面进行同构分析与变换:(注:因为,同构的两个图可能有数种一一对应模式,所以,在下面分析两个同构图的特性时,针对任意一种一一对应同构模式都适用)。
显然,按同构的定义,同构的两个图中,一个图中某个顶点所含有的环只能与另一个图中因同构而一一对应的顶点所含有的环一一对应,所以,一个图中某个顶点所含有的环数等于另一个图中因同构而一一对应的顶点所含有的环数。同样,按同构的定义,同构的两个图中,一个图中某两个不同顶点之间直接连接的边(无向图)或弧(有向图)只能与另一个图中因同构而一一对应的两个不同顶点之间直接连接的边(无向图)或弧(有向图)一一对应,所以,一个图中某两个不同顶点之间直接连接的边(无向图)或弧(有向图)数等于另一个图中因同构而一一对应的两个不同顶点之间直接连接的边(无向图)或弧(有向图)数。显然,同构的两个图中,一个图中某个含环顶点的环数与另一个图中因同构而一一对应的含环顶点的环数同时缩小相同的倍数(注:缩小后,保证环数为大于零的整数),则这两个图还同构。同样,同构的两个图中,一个图中某两个不同顶点之间直接连接的边(无向图)或弧(有向图)数与另一个图中因同构而一一对应的两个不同顶点之间直接连接的边(无向图)或弧(有向图)数,同时缩小相同的倍数(注:缩小后,保证边或弧数为大于零的整数),则这两个图还同构。
现在,已知G″≌H″,我们对G″和H″进行“直接连接缩小变换”:我们分别将G″和H″中所有含环顶点的环数同时缩小n-1倍,再分别将G″和H″中所有两个不同顶点之间直接连接的边(无向图)或弧(有向图)数同时缩小n-2倍,“直接连接缩小变换”完成。显然, G″中任意一个含环顶点的环数与H″中因同构而一一对应的某个含环顶点的环数,经过“直接连接缩小变换”后,保证了同时缩小相同的n-1倍, 并且,G″中这个顶点缩小后的环数等于G中按“规定”一一对应的某个顶点的环数,H″中这个顶点缩小后的环数等于H中按“规定”一一对应的某个顶点的环数;另外,G″中任意两个不同顶点之间直接连接的边(无向图)或弧(有向图)数与H″中因同构而一一对应的两个不同顶点之间直接连接的边(无向图)或弧(有向图)数,经过“直接连接缩小变换”后,保证了同时缩小相同的n-2倍, 并且,G″中这任意两个不同顶点之间直接连接的边(无向图)或弧(有向图)数等于G中按“规定”一一对应的某两个不同顶点之间的直接连接的边(无向图)或弧(有向图)数,H″中这任意两个不同顶点之间直接连接的边(无向图)或弧(有向图)数等于H中按“规定”一一对应的某两个不同顶点之间的直接连接的边(无向图)或弧(有向图)数。所以,经过“直接连接缩小变换”后,最终所生成的G″和最终所生成的H″也同构,由前面的叙述知:G=最终所生成的G″ ,H=最终所生成的H″,所以:G≌H  ,证毕。


[参考文献]
[1]徐保根.图的控制理论[M].北京:科学出版社,2008.
[2]李明哲,金俊,石端银.图论及其算法[M].北京:机械工业出版社,2010.10.
[3]谢政,戴丽.组合图论[M].长沙:国防科技大学出版社,2003.5.


Proof of the Ulam conjecture
Key words: isomorphism; one-to-one correspondence; vertex, edge, arc


Abstract:  In the graph theory, the paper uses the elementary method (“Four direct connection duplication operations ”,“Direct connection reduction transformation”, ect),On any finite graph(Undirected graphs, directed graphs, simple graphs, complex graphs ,ect),Uram's conjecture is proved.
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

返回列表 回复 发帖