Graph Isomorphism

http://en.wikipedia.org/wiki/Graph_canonization
http://en.wikipedia.org/wiki/Graph_isomorphism
http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem
http://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)

http://en.wikipedia.org/wiki/Graph_isomorphism_problem#Solved_special_cases

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

為什麼對？
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

Reconstruction Conjecture

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

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

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

Graph Enumeration

http://en.wikipedia.org/wiki/Graph_enumeration

Tree Enumeration

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

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

UVa 10843

Graph Distance（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

Graph Sparsification

《Graph Sparsifiers: A Survey》

http://www.cs.yale.edu/homes/spielman/

http://stellar.mit.edu/S/course/18/sp18/18.408/index.html

Spanner

http://tmtacm.blogspot.tw/2016/01/2.html

https://ithelp.ithome.com.tw/articles/10277832

Expander

https://people.eecs.berkeley.edu/~luca/expanders2016/

Definition 3.1
A graph G = (V,E) is called an (n, d, c)-expander
if it has n vertices, the maximum degree is d,
and for all S 屬於 V with |S| <= |V|/2,
we have |N(S)| >= c|S| and c is called the expansion of G.

http://en.wikipedia.org/wiki/Expander_graph
https://en.wikipedia.org/wiki/Zig-zag_product

Graph Stream

《Graph Stream Algorithms: A Survey》

Graph Sketch

《Graph Sketches: Sparsification, Spanners, and Subgraphs》

Random Graph

Graph Theory

本站僅介紹最基礎的圖論知識。讀者如果覺得不過癮，可以自行研究下述這些進階的圖論領域。

http://press.princeton.edu/titles/10314.html

Geometric Graph Theory

http://en.wikipedia.org/wiki/Geometric_graph_theory

http://www.math.harvard.edu/~knill/graphgeometry/

引入距離的概念。

Topological Graph Theory

http://en.wikipedia.org/wiki/Topological_graph_theory

著重於點與邊。發掘特殊的圖，建立從屬關係。

minor containment problem 問一張圖是不是有某個minor。至少是NP-complete。
http://en.wikipedia.org/wiki/Graph_minor
http://en.wikipedia.org/wiki/Robertson–Seymour_theorem
http://en.wikipedia.org/wiki/Graph_structure_theorem
http://en.wikipedia.org/wiki/Graph_sandwich_problem

Extremal Graph Theory

http://en.wikipedia.org/wiki/Extremal_graph_theory

著重屬性計量。

Structural Graph Theory

研究圖的各種架構方式、描述方式。

本站僅提到兩種方式：用點和邊架構出圖、用交集架構出圖。

Algebraic Graph Theory與Spectral Graph Theory

http://en.wikipedia.org/wiki/Algebraic_graph_theory

http://en.wikipedia.org/wiki/Spectral_graph_theory

以代數描述一張圖、分析一張圖。