图同构

✍ dations ◷ 2025-07-04 22:31:48 #图论,离散数学,机器学习,计算机科学中未解决的问题,数学中未解决的问题

图同构(Graph Isomorphism)描述的是图论中,两个图之间的完全等价关系。在图论的观点下,两个同构的图被当作同一个图来研究。

只有节点数目相同(即同阶)的两个图才有可能同构。两个简单图 G {\displaystyle G} H {\displaystyle H} 称为是同构的,当且仅当存在一个将 G {\displaystyle G} 的节点 1 , , n {\displaystyle 1,\ldots ,n} 映射到 H {\displaystyle H} 的节点 1 , , n {\displaystyle 1,\ldots ,n} 的一一对应 σ {\displaystyle \sigma } ,使得 G {\displaystyle G} 中任意两个节点 i {\displaystyle i} j {\displaystyle j} 相连接,当且仅当 H {\displaystyle H} 中对应的两个节点 σ ( i ) {\displaystyle \sigma (i)} σ ( j ) {\displaystyle \sigma (j)} 相连接。如果 G {\displaystyle G} H {\displaystyle H} 是有向图,那么同构的定义中还进一步要求对于 G {\displaystyle G} 中任意两个相连的节点 i {\displaystyle i} j {\displaystyle j} ,边 ( i , j ) {\displaystyle (i,j)} 与它在 H {\displaystyle H} 中对应的边 ( σ ( i ) , σ ( j ) ) {\displaystyle (\sigma (i),\sigma (j))} 方向相同。类似地可以定义两个多重图的同构关系。

一个具体的例子如下,为方便起见,两图中对应节点被染成了相同的颜色:

σ ( b ) = 6 {\displaystyle \sigma (b)=6}

σ ( c ) = 8 {\displaystyle \sigma (c)=8}

σ ( d ) = 3 {\displaystyle \sigma (d)=3}

σ ( g ) = 5 {\displaystyle \sigma (g)=5}

σ ( h ) = 2 {\displaystyle \sigma (h)=2}

σ ( i ) = 4 {\displaystyle \sigma (i)=4}

σ ( j ) = 7 {\displaystyle \sigma (j)=7}

要注意的一点是,在图论中,一幅图经常可以有多种不同的方式在纸上或屏幕上画出来,所以两个看起来很不同的图也可能是同构的。尤其当图的节点数比较大时,很难一眼从画出的图上判断它们是否同构。

在计算机科学、数学和统计学中,图同构问题是复杂度理论研究中经常讨论的热点话题之一。图同构问题容易和图匹配问题混淆:

严格地说,两个问题是不同的,显然后者是比前者更进一步的问题,但也有一些论文将两者混同并用Graph Isomorphism一词指代Graph Matching问题。迄今尚无人严格证明两者难度在P/NP意义下是相等的(要证明这一点,就必须证明第一个问题的答案可被多项式时间约化为第二个问题的答案,即:存在一个正常数 d > 0 {\displaystyle d>0} ,使得对于任何一个可以判定两个图是否同构的算法 J {\displaystyle {\cal {J}}} ,若 J {\displaystyle {\cal {J}}} 输出的判定为真,那么在参考 J {\displaystyle {\cal {J}}} 输出的结果的基础上再花费至多 O ( n d ) {\displaystyle O(n^{d})} 时间就可找出至少一个做成图同构的一一对应)。

判定图同构(Graph Isomorphism)的计算复杂度是未知的,因此现在仅能被粗略地归类为NP;图匹配(Graph Matching)问题本身的复杂度同样是未知的,但在机器学习领域非常流行的一种约化版本将其视为NP困难的QAP(英语:Quadratic assignment problem)问题的特殊情形

其中 F {\displaystyle \|\cdot \|_{F}} 表示矩阵的Frobenius模。该QAP约化相当于问:要求找到从 G {\displaystyle G} H {\displaystyle H} 的一一映射,使得在此映射下两个图最相似。显然图匹配问题是该QAP问题的一种特殊情形,因为当两个图并不同构时,寻找两图间同构映射的尝试是没有意义的,但寻找两图间的一个最大化相似度的“最优映射”仍然是有意义的。尤其在当所给的数据并非图的精确观测而是被随机误差污染时,更常用该约化形式并予以近似求解。另有与两个问题相关的更进一步的问题:

子图同构已被证明是NP完全问题。

2015年,芝加哥大学教授、匈牙利裔计算机科学家László Babai(英语:László Babai)宣布证明了图同构问题可以在准多项式(Quasi-polynomial)时间内求解。哈洛德·贺欧夫各特指出了文中的一处错误,随后Babai宣布修正了该错误并更新了论文。

对于以下的特殊情形,图同构问题是可以多项式时间甚至快速求解的:

与理论研究主要关注计算复杂度不同,对实用解法的研究主要关注具体应用中的实践计算速度。P/NP问题只关注时间复杂度中 n {\displaystyle n} 的指数,而不关注其系数大小。即使一个算法是多项式时间的,它也可能因 n {\displaystyle n} 的系数过大导致的速度太慢及/或数值上不稳定,而在实践中根本没有用处;反之,一个优秀的实用解法,即使不能保证是多项式时间的,在很多应用上也可能比一些多项式时间的解法快得多。

在图同构问题上,目前处于领先性能的实用解法是由澳大利亚计算机科学家Brendan McKay(英语:Brendan McKay)在1980年代提出的NAUTY,其对每一个图 G {\displaystyle G} 估计其节点的一个标准索引排列(Canonical Indexing,或称Canonical Labeling)。标准索引可以非常耗时,而NAUTY算法通过探索图的自同构性群的性质,对索引步骤进行剪枝,大大加快了标准索引的计算速度。NAUTY自从提出以来,成为了几乎每一篇研究图同构和图匹配问题实用解法的论文必定要进行比较的竞争对手。

其它流行的方法包括:各色启发式算法;对QAP约化进行SDP(英语:Semidefinite programming)松弛;近似计算图之间的某种不依赖于节点顺序的距离,例如图之间的编辑距离和cut distance等,这些距离的精确计算通常是NP困难的。

相关

  • M13噬菌体M13噬菌体(M13 bacteriophage)为环状单链DNA丝状噬菌体。其核酸由6407个核苷酸组成,衣壳由2700个衣壳粒组成。M13噬菌体感染通常不是致命的,也为非溶菌病毒,但受感染的细菌其生长
  • 藜属藜属(学名:Chenopodium)是一种苋科藜亚科的植物,包含约150种一年生或多年生草本开花植物,几乎在全世界均有生长,而且是现时世上多个山区民族的主粮。较早分类方法归类为藜科,藜科在
  • 托法恩托法恩(威尔士语:Torfaen)是英国威尔士东部的一个郡级自治市,首府为庞蒂浦,面积共126平方公里,人口为91,100人,14.5%的人使用威尔士语。境内拥有世界遗产——工业革命遗址布莱纳文。
  • 巴勒斯坦总理巴勒斯坦总理是巴勒斯坦国的政府首脑。巴勒斯坦总理一职设立于2003年,其职责是管理巴勒斯坦政府的日常活动。政府的行政权力实际仍然由巴勒斯坦总统掌握。巴勒斯坦总理需要首
  • 金午时花金午时花(学名为Sida rhombifolia ssp. rhombifolia)。多年生直立半灌木;茎被星状毛。叶菱形或长椭圆状披针形,叶基圆形、钝或尖锐,两面被短星状毛。花瓣5枚,黄色至米黄色,花径可达
  • 四里河街道四里河街道,是中华人民共和国安徽省合肥市庐阳区下辖的一个乡镇级行政单位。四里河街道下辖以下地区:桃花园社区居委会、银河湾社区居委会、四河社区。
  • 伊豆小笠原海沟伊豆小笠原海沟(日语:伊豆小笠原海溝(いず・おがさわらかいこう),英语:Izu-Bonin Trench),是个位在西太平洋的海沟,北起日本海沟,南与马里亚纳海沟相接。伊豆小笠原海沟是日本海沟的延
  • 泥灰岩泥灰岩(英语:marl或marlstone)是一种富含碳酸钙或石灰的泥土或泥岩,其中包含不同数量的粘土矿物和淤泥。泥灰岩中大部分含碳矿物质通常为方解石,但也存在霰石、白云石、菱铁矿等
  • 点格棋点格棋(Dots and Boxes,又名Boxe、 Squares、Paddocks、Square-itDots and Dashes、Dots、Smart Dots、Dot Boxing、the Dot Game),或译围地盘,是法国数学家爱德华·卢卡斯在1891
  • 张东尹张东润(韩语:장동윤,英语:Dong-Yoon Jang,1992年7月12日-),韩国男演员。2015年时,因热心协助警方逮捕罪犯,受到警察局表彰,经过电视台的报导后,由于样貌清秀被经纪公司发掘,正式作为演员