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》