而如果一张图有100个节点,可能的匹配数会远远的超过可见宇宙中的原子数。
所以这种比蛮力的方法非常不切实际,只适用于极少节点的图。
而从手上的稿纸来看,刘嘉欣在研究这个问题的时候,并没有将图同构问题全部带入进P=NP类问题中。
她选择了通过准多项式与映射函数来对同构模块,对图像进行切割的同时,将这些‘对比点’看作是一块块的‘图像’。
然后模拟四色定理的方式,从第一张图的一些小节点开始,给它们每一个点“画”上不同的颜色。
然后再假设第二张图里有其-一对应的点,开始在其中寻找同构,并在找到后将这些对应节点标上相同的颜色。
该算法循环往复直到最终验证完所有可能的猜测。
这是一条比以往图同构难题更加高效率的算法,而其中的关键,就在于这些稿纸中的一项数学工具。
“准多项式图形映射法。”
这项工具是通过连接多项式和映射工具来完成图同构高效算法的。
尽管它并没有解决图同构难题,甚至都没有将这个问题彻底的归纳到P类问题范畴还是NP类问题中。
内容未完,下一页继续阅读