Graph Isomorphism(Under Construction!)

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(Under Construction!)

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(Under Construction!)

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(Under Construction!)

Subgraph Counting

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