Graph Isomorphism(Under Construction!)
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
Graph Enumeration(Under Construction!)
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(Under Construction!)
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(Under Construction!)
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
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(Under Construction!)
Graph Stream
《Graph Stream Algorithms: A Survey》
Graph Sketch
《Graph Sketches: Sparsification, Spanners, and Subgraphs》
Graph Sampling(Under Construction!)
Random Graph
Graph Theory
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
以代數描述一張圖、分析一張圖。