graph isomorphism

https://en.wikipedia.org/wiki/Graph_canonization
https://en.wikipedia.org/wiki/Graph_isomorphism
https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Solved_special_cases

subgraph isomorphism

https://en.wikipedia.org/wiki/Subgraph_isomorphism_problem
https://en.wikipedia.org/wiki/Maximum_common_subgraph_isomorphism_problem

https://adriann.github.io/Ullman subgraph isomorphism.html
Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism

tree isomorphism

http://www.cs.upc.edu/~valiente/graph-00-01-c.pdf
use radix sort O(nd) = O(#son + #grandson) = O(n + n) = O(n)

為什麼對？
https://github.com/juanplopes/icpc/blob/master/uva/12489.cpp

兩棵樹的子圖同構：刪掉G和H的根，變成很多子樹G1...Gp和H1....Hq。建立二分圖：當Gi和Hj同構，建立邊ij。求最大二分匹配。時間複雜度O(V²E)。

UVa 10729 10904 12489 ICPC 2935

subtree isomorphism

可以用DP + matching
https://code.google.com/codejam/contest/dashboard?c=32005#s=a&a=3
http://www.lsi.upc.edu/~valiente/riga-tre.pdf

reconstruction conjecture

https://en.wikipedia.org/wiki/Reconstruction_conjecture

刪掉一點之導出子圖，總共V張，合稱deck。

兩圖同構，顯然deck相同。兩圖deck相同，是否同構？

graph enumeration

tree enumeration

http://mathworld.wolfram.com/LabeledTree.html
https://en.wikipedia.org/wiki/Prüfer_sequence
http://www.matrix67.com/blog/archives/682

Prüfer code：把一棵樹轉換成獨特的編號。

UVa 10843

subgraph searching（subgraph matching）

https://www.cs.cmu.edu/~jingx/docs/DBreport.pdf

graph approximate isomorphism

https://arxiv.org/abs/1802.08509

graph distance（graph similarity）（graph kernel）

兩張圖的距離。

https://www.zhihu.com/question/57269332
http://www.raetschlab.org/lectures/amsa/5-borgwardt-graph.pdf
http://www.stat.purdue.edu/~vishy/talks/Graphs.pdf

tree distance（tree similarity）

兩棵樹的距離。

edit distance
rotation distance
chain rotation distance

Subgraph counting

《A Survey on Subgraph Counting: Concepts, Algorithms, and Applications to Network Motifs and Graphlets》