圖數(shù)據(jù)管理與挖掘-第四講（子）圖匹配算法（涵蓋近似圖匹配） 北京大學(xué)2021暑期
四、子圖匹配
=======
PART 1: 子圖同態(tài)
?
4-上 P1 - 00:04
??
4-上 P1 - 08:32
?Graphs to Adjacent matrices
找這樣的相當(dāng)于f變換的M'
怎么找？basic idea：初始化一個矩陣，然后展開樹搜索逐行修正矩陣，中間如得到不符合要求的矩陣則回溯。
Neighborhood Connection Pruning：如果鄰居不匹配，則該節(jié)點(diǎn)不可能匹配
?
4-上 P1 - 27:19
?找同態(tài)的過程==狀態(tài)轉(zhuǎn)換的過程
?
4-上 P1 - 35:44
?多個中間狀態(tài)可能由不同的路徑到達(dá)，合適的順序選擇也是一種優(yōu)化
?
4-上 P1 - 37:23
?以上都可以總結(jié)為帶有回溯的DFS
?
4-上 P1 - 38:56
?邊表joint
- binary join做法（自然連接）
- 不止一個pair同時進(jìn)行匹配，預(yù)先計算N(v)（worst case optimal join）
=========================
標(biāo)簽：
