如何通過鄰接矩陣判斷拓撲結構是等價的？

01-11

如下圖（畫圖渣，不要在意……）T1和T2兩個拓撲結構很顯然是一模一樣的。
但是由於編號的不同，導致鄰接矩陣的表示會不一樣。那麼，如何通過判定鄰接矩陣的等價關係，進而判定拓撲圖是等價的？

此問題是否等價於證明：T1在何種變換下能夠得到T2？
用MATLAB算了一下上面兩個矩陣的特徵值，以及其它編號情況，發現是相同的，不知道為什麼。說明相同它們都是合同的？
能否給出數學證明？

圖同構問題和子圖同構問題。

圖同構是不是NP完全的還不知道。子圖同構是NP完全的。

關於子圖同構現在有這些研究

最早的Ullmann的論文。這篇論文詳細的解答了題主的問題。

An Algorithm for Subgraph Isomorphism

裡面有詳細的矩陣和對應矩陣應用的描述：）

如果覺得太老了題主可以去看VF2

和我師兄寫的QuickSI。然後最近TurboISO。

格里菲斯大學的boostiso（我還一直沒看汗）

google一下就能google到啦。

然後關於圖同構的研究去看 Practical Graph Isomorphism。

和關注圖同構在P/NP問題上重大突破，計算機理論10年最重要成果 -- 新智元 -- 傳送門

這個比較新的成果。

這個問題其它人已經說清楚了

一個圖，頂點的編號不同，得到的兩個矩陣A和B ，用 $P_{k}(i,j)$ 表示交換i,j兩行的初等矩陣，那麼A和B的關係就是 $A=P_{1}P_{2}P_{3} ...P_{n} BP_{n}...P_{3}P_{2}P_{1}$ ,所以A和B是合同的.他們的特徵值自然是相同的.

另外一點就是如果兩個圖的鄰接矩陣有相同的特徵值，它們不一定是同構的。例如：

這兩個圖的特徵多項式均為： $lambda ^{6}-7lambda ^{4}-4lambda ^{3} +7lambda ^{2} +4lambda -1$

這樣的圖在數學上有個名詞：

Cospectral graphs:Two non-isomorphic graphs are said to be cospectral if they have the same eigenvalues with the same multiplicities.

在這本書里有很多例子Cvetkovic, D.M. (1971). Graphs and their spectra, Thesis, University of Belgrade.

這叫判斷圖的同構……NP問題……

如果對沒有其它限制條件的任意圖找到靠譜的多項式演算法，務必發個SCI讓大家瞻仰一下。

（子）圖同構領域，有哪些演算法，基於矢量和矩陣運算，求大神告知

前面已經有大神回答了圖同構的問題。我狗尾續個貂。

躺在床鋪臨時想了一下，特徵值相同是圖同構的必要非充分條件。任何兩個同構的圖，都可以通過左右各乘一個相同的初等矩陣變換為對方（此處描述不嚴謹，應該是多次從左右各乘一個相同且逆矩陣就是自己的初等矩陣）。這是不會改變特徵值的（因為兩矩陣相似）。

以上判斷需要仔細驗證，帶我午睡起來再說，題主切勿採納～

////////////////////睡醒的分割線//////////////////////////////

1) 兩個圖同構但鄰接矩陣(記為G1和G2)不同，可以表達為將圖的頂點序號進行若干次對換。

2) 對G1進行一次頂點序號(設序號為i和j)對換，可以表達為將G1的第i和第j行對換，將第i和第j列對換。相當於作如下變換G0=T*G1*T，T為將單位矩陣第i和第j行對換得到的初等矩陣，可知T=T逆。

3) 故，G2=T(n)*T(n-1)*...T(1) * G1 * T(1)...*T(n-1)*T(n)。可知 T(n)*T(n-1)*...T(1) 為 T(1)...*T(n-1)*T(n)的逆，故G1和G2相似，所以兩者特徵值相同。

////////////////////關於子圖同構搜索////////////////////////

按照題主在第一個答案下的評論，你遇到的問題是子圖同構搜索問題（subgraph isomorphism，或者叫exact subgraph matching）。注意這個問題和你在題目中描述的圖同構問題是兩個問題，研究者的重點完全不一樣！

具體來說，exact subgraph matching 又可分為兩類：

1）給定一個查詢圖（小圖），和一個目標圖集合，找出所有含有查詢圖的目標圖

2）給定一個查詢圖（小圖），和一個巨大的目標圖（大圖），找出大目標圖上所有與查詢圖同構的子圖。

對於第一個問題，最好的辦法是通過索引技術把大量不可能的目標圖濾除，然後在剩下的目標圖（候選集）上用ullmann演算法進行子圖同構搜索。

對於第二個問題，可以直接使用ullmann演算法進行搜索，對於幾萬條邊的目標圖，差不多也夠了。如果不行，對於ullmann演算法的優化在於：

1）使用一種有效的過濾技術，比如鄰域label向量，偽子圖同構搜索等等。但是根據韓國幾個學者的實驗，這些技術往往得不償失，性能不如QuickSI，也就是 @慶祝的師兄提出的演算法。我一直認為這個演算法在面對單張大圖的時候沒有任何過濾手段，不知是否如此。

2）尋找一個好的頂點搜索順序，好的搜索順序可以大大減少搜索時的中間結果。最簡單的例子還是QuickSI：假設你在搜索前知道了大圖上每條邊的label的頻率，你可以用這個頻率為權重，以prim演算法構造最小生成樹，然後按照頂點加入生成樹的順序為搜索順序。

目前最好的演算法應該是那幾個韓國學者提出的turbo-iso演算法，但是他們的演算法實現起來比較麻煩。

這個是拓撲唯一序的問題。在化學結構的唯一序判定中經常用到。

比如題主說的那個可以看成一個分子結構，每個節點都是碳原子，每條邊都是單鍵。

目前有多個演算法大體解決了分子結構中的這個問題，也就是任何一個分子結構有個演算法給每個節點標一個固定的標號的。不論怎麼排都會按照這個序號來排列。

用得最多的是MORGAN 演算法。其論文在下面：

The Generation of a Unique Machine Description for Chemical Structures—A Technique Developed

at Chemical Abstracts Service

而你的這個問題，跟子圖同構不一樣，只是判定唯一序的問題。

那麼從擴大一點來說。

判斷布爾矩陣是否同構，的方法發生了變化。

圖形，布爾矩陣1——&> 唯一序矩陣。

圖形，布爾矩陣2------&>唯一序矩陣.

兩者的唯一序矩陣一致則兩者的拓撲結構等價。