铁书网

字:
关灯 护眼
铁书网 > 大国院士 > 第八百八十二章 :探索数学的第一期刊物

第八百八十二章 :探索数学的第一期刊物

_h)h=(Vh,Eh)。”

    “若存在一种从G到h的映射?:VG→Vh,满足:?(vi)=vi′,?(vj)=v′j......”

    “有点意思,没有走更广泛的p类问题方式,而是通过准多项式与映射函数来对同构模块进行切割。”

    “这种方法有点类似于弱黎曼猜想的研究方式?”

    看着手中的稿纸,徐川自言自语的念叨着。

    图同构问题,其实通俗一点来说,它就是给定两个图,问它们是否一模一样。

    而如何对给定的2个图检查它们是否同构,一模一样呢?

    一种最方法是:简单地去比较每一个点来匹配另一个图中可能对应的所有节点。

    但众所周知,图片是二维平面,一张图上具有‘无数’的点。

    如果说,假设一张具有N个节点的图,按照这种匹配的计算方法,其匹配数量就为N的阶乘(1*2*3*...*N),远远超过N的数量级。

    假如图里只有10个节点,也已经需要三百六十多万次可能的匹配检查。(1*2*3.....*10)

    而如果一张图有100个节点,可能的匹配数会远远的超过可见宇宙中的原子数。

    所以这种比蛮力的方法非常不切实际,只适用于极少节点的图。

    而从手上的稿纸来看,刘嘉欣在研究这个问题的时候,并没有将图同构问题全部带入进p=Np类问题中。

    她选择了通过准多项式与映射函数来对同构模块,对图像进行切割的同时,将这些‘对比点’看作是一块块的‘图像’。

    然后模拟四色定理的方式,从第一张图的一些小节点开始,给它们每一个点“画”上不同的颜色。

    然后再假设第二张图里有其-一对应的点,开始在其中寻找同构,并在找到后将这些对应节点标上相同的颜色。

    该算法循环往复直到最终验证完所有可能的猜测。

    这是一条比以往图同构难题更加高效率的算法,而其中的关键,就在于这些稿纸中的一项数学工具。

    “准多项式图形映射法。”

    这项工具是通过连接多项式和映射工具来完成图同构高效算法的。

    尽管它并没有解决图同构难题,甚至都没有将这个问题彻底的归纳到p类问题范畴还是Np类问题中。

    但不可否认的是,在图同构难题上,这是一次重大的突破。

&nb>> --
『加入书签,方便阅读』
内容有问题?点击>>>邮件反馈
热门推荐
日常系满级男神乱世情怨老实人逆袭2003随母下堂后,小福宝荣华一生杨柳坝刘家湾隔着一张大塘80年代剽悍土著女