Question

Graph Spectrum

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

Graph 资料结构（Under Construction!）

Incidence Matrix

先前介绍了三种平易近人的资料结构：edge list、adjacency matrix、adjacency lists。接著再介绍两个罕见的资料结构，适合已经熟悉图论、想要深入鑽研的人。

点有编号，边有编号。矩阵的第一个维度代表点，第二个维度代表边，元素(0,1) 记录著第 0 点与第 1 边是否碰触。

无向图当中，点碰触边就标上 1，否则标上 0。有向图当中，点碰触出边就标上+1，点碰触入边就标上-1，否则标上 0。

Incidence Matrix 的缺点是无法记录自己连向自己的边。

Incidence Matrix 可以看成是 Bipartite Graph。

Laplacian Matrix

L = D - A。L D A 分别代表 Laplacian Matrix、Degree Matrix、Adjacency Matrix。

【待补文字】

Graph Property（Under Construction!）

Reachability

矩阵相乘需时 O(N^3)。亦得採用更快的矩阵相乘演算法，例如 Strassen's Algorithm。

http://www.lab2.kuis.kyoto-u.ac.jp/keisan-genkai/reports/2006/nhc/Uri_Zwick.pdf

范例：Transitive Closure

请参考“ Transitive Closure: Matrix Multiplication ”。

矩阵元素改成 Boolean，矩阵加法改成 OR 运算，矩阵乘法改成 AND 运算即可！

Strassen's Algorithm 的过程包含了实数减法，在此对应到 OR 反元素，然而 OR 并没有反元素，所以不能直接套用 Strassen's Algorithm。

不过我们还是可以运用矩阵乘法解题。方法很简单：直接用实数下去算，计算完毕之后，把零当做 false，非零的数字当做是 true 就可以了。

范例：Shortest Path

矩阵元素依然是实数，矩阵加法改成最小值运算，矩阵乘法改成加法运算即可！

不过 min 运算没有反元素，所以必须用特殊的方式避开反元素的计算，例如 Seidel's Algorithm。

http://www.mpi-inf.mpg.de/departments/d1/teaching/ss12/AdvancedGraphAlgorithms/Slides14.pdf
http://theory.stanford.edu/~virgi/cs367/

范例：Matching

【待补文字】

Similarity（Graph Kernel）

相似程度。两张图的距离、差异。

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

Centrality

宽阔程度。

http://en.wikipedia.org/wiki/Centrality
http://en.wikipedia.org/wiki/Betweenness_centrality

Connectivity

连结强度。

http://en.wikipedia.org/wiki/Algebraic_connectivity
http://www.lix.polytechnique.fr/~schwander/resources/mig/slides/pati.pdf

范例：Clique

http://web.stanford.edu/class/ee378b/lect-7.pdf
matrix multiplication of adjacency matrix ---> transitive
当 clique 足够大，此时矩阵的无限大次方，很容易在 clique 裡面跑来跑去
(degree 总和特别多?  不巧遇到 degree 很多的点怎办? 像是星星图那种的)
找出 eigenvalue 绝对值最大的那一个 eigenvector
当中绝对值比较大的那几个元素，差不多是个 clique

Random Walk

UVa 12695

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
http://en.wikipedia.org/wiki/Graph_sandwich_problem

Graph Enumeration

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

Tree Isomorphism

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

UVa 10729 10904 12489 ICPC 2935

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 Partitioning（Under Construction!）

Graph Partitioning

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

Separator

规定两边的点数呈特定比例，就是 NP-complete 问题。

http://www.cs.cmu.edu/~guyb/realworld/slidesF07/separators1.pdf

Expander

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 Drawing（Under Construction!）

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

Graph Sampling（Under Construction!）

Graph Sampling

Graph Sparsification

Spanner

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

Graph Stream（Under Construction!）

Graph Stream

《Graph Stream Algorithms: A Survey》

Graph Sketch

《Graph Sketches: Sparsification, Spanners, and Subgraphs》

Graph Theory

Graph Theory

本站仅介绍最基础的图论知识。读者如果觉得不过瘾，可以自行研究下述这些进阶的图论领域。

Graph Theory 与 Linear Programming

组合最佳化的经典问题，路树流割配，通通可以套用线性规划。针对流割配这类複杂度较高的问题，线性规划的速度远比经典演算法还快！针对问题本身的性质，有著各种加速技巧，内容多到可以写成一本书。有兴趣的读者可以自行查询资料。

Minimum Ratio Spanning Tree: Dinkelbach's Algorithm

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

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

http://ocw.mit.edu/courses/mathematics/18-409-topics-in-theoretical-computer-science-an-algorithmists-toolkit-fall-2009/lecture-notes/

以代数描述一张图、分析一张图。