基本算法
描述：遍历图$G$的所有节点，对每个$v$，递归的访问$v$的所有的没被访问过的子节点。递归的意思是
1. (Recursion)子节点的子节点。
2. (Base Case/boundary condition)当前节点没有子节点了(除了已经被访问过的)。
要维护节点是否被访问过每个节点需要有个标志位，也就是一个长度为$n$的数组。
算法附加给图的结构
首先节点被touch的顺序给出了一个节点的序。
对于边，在算法运行的过程中会遇到两种边，一种是发现指向的子节点被touch过；一种是指向子节点没被touch过。对子节点没被touch过的情况，这个边称为"tree edges"。
对子节点已经被touch过的情况，设$u$是当前节点，$v$是子节点。现在考虑进入访问$u$的这个递归堆栈，$v$可能在进入之前已经被touch过，或者是进入堆栈之后被touch的，现在又遇到了。
对于进入堆栈之后被touch的，$v$必然是$u$的后代，且不是直接后代(直接后代必然是第一次被touch)，这种边称为"forward edges"。
对于进入堆栈之前被touch的，又可以分成两种情况:
1.$u$是在访问$v$的递归堆栈里被访问的，也就是说$u$是$v$的后代，名分已定，这时候我们还在访问$v$的递归堆栈里(其实整个访问$u$的递归堆栈都在访问$v$的递归堆栈里)，这种边称为"back edges"。
2.访问$v$的递归堆栈早已结束，$v$是那时候被touch的，$u$，$v$代表的堆栈没有任何关系，这种边叫"cross edges"。
现在改变程序记录上面提到的节点和边的信息。
touched[n]已经记录了节点是不是被touch过了的信息，现在要增加记录什么时候被touch的，首先我们要记录每个节点的递归堆栈开始和结束的时间，这需要两个长度为n的数组，start[n]，end[n]。每次进入一个节点递归堆栈和出去的时候时间加1。
这两个数组含有的信息包含了touched[n]包含的信息，进入节点的递归堆栈的时候就是节点被touch的时候，当start[i]不为0的时候就是touched[i]不为0的时候，所以touched[i]可以去掉了。
按v的信息(start[v],end[v])来分类:
(0, 0)直接后代:tree edge. (白色)
(0, b)不可能
(a, 0)$\Leftrightarrow$ b = 0, v堆栈还未完成: back edge.(灰色)
(a, b)$\Leftrightarrow$ b != 0, v堆栈已经完成: forward edge(a > start[u])/cross edge(b < start[u]) (黑色)
另一种算法是节点染色，标在括号里了。
对无向图来说上面的第4中情况，遍历u的邻居的时候发现v的堆栈已经完成，说明v到u之间的连接已经考虑过了，只是因为我们使用矩阵表示的原因循环中又出现一遍，可以直接抛弃，所以无向图里没有forward edge/cross edge的说法。
2012/02/29
图论基本概念
1)子图：子图可以用构造的方式产生，一个图$G$，从其中拿出一些节点$V$，这些节点构成一个子图（只有节点的子图）；接着拿一些$G$的边，能拿的边都是必然是以$V$为端点的，还是子图；继续拿，拿到不能再拿得到induced by $V$的子图。
Euler path(cycle) $x_1, \cdots, x_n$最主要的性质是包括所有的边，并且只包含一次，长度是定的，边的个数。
Hamilton path(cycle) $y_1, \cdots, y_n$最主要的性质是包括所有的顶点，并且只包含一次，节点数是定的，顶点的个数。
Euler path：节点是可以经过两次的， Hamilton path：不必经过每条边。
"节点不重复"是比"边不重复"强的要求，前者可推出后者。
2) Cycle是很重要的一个刻画图的属性：
1) 连通无cycle是树
2) 节点数大于等于2的树必然有2个节点的degree是1，也就是叶子。反过来如果一个图的最小degree大于1，那么必然不是树，必然有cycle。
3) 如果一个图如果只有一个cycle，那么这个图就是这个cycle加上一些根植在其上的树，如果不是树那么和只有一个cycle矛盾。
4) 如果一个图没有没有长度为奇数的cycle，那么这个图是两部图。
首先注意到，对于一个tree来说，连接任何两叶子个节点，也就是加入一个边，必然得到一个Cycle。
Fundamental Cycle：设$T$是图$G$的一个span tree，加入任何一个$G$的边到$T$里，得到的Cycle称为Fundamental Cycle。注意Fundamental Cycle必须依赖于span tree的选择，但是他们的个数是定的。
性质：图$G(V,E)$的Fundamental Cycle的个数是图的边的数量减去span tree的边的数量，也就是$|E|-(n-1)$。
性质：图的任何Cycle都是Fundamental Cycle的组合。
3) 图的同构，定义为a)存在一组标签，两图的端点同用这一组标签，b)任意两个标签之间的边数是相等的。
Labelled Tree的意思是，考虑上面的同构的定义，如果同一个树，用一组标签，但是标注的顶点不一样，这样可以看成两个tree，如果这两个tree不满足同构的定义，那么认为是两个Labelled Tree。当然本身不同构的tree自然是不同的Labelled Tree
顶点个数为$n$的Labelled Tree的个数$T(n)=n^{n-2}$
5) 平面图
桥，平面图的桥只和一个face就是边界face接触，不是桥的边都和两个face接触。
平面图的欧拉公式：$$V-E+R=2$$ 平面图把平面分成不同的region，region的度是其接触的边的数量，如果一个region接触了一个边两次，计数region的度的时候算两次，则所有region的度的和是边的数量的2倍。
$K_{3,3}$不是平面图：region的边界显然是cycle，而$K_{3,3}$没有奇数边的cycle，所以它里面的cycle边的数量都大于等于4，也就是region的度大于等于4；通过欧拉公式可得如果$K_{3,3}$是平面图的话，region的个数是5，这给出了一个region度和的下界5*4=20，但是我们知道这个和其实是边数量的2倍，也就是18，矛盾。
圆和弦分的区域
$n$个点分布在圆上，任取两个点，画一个弦，假设没有三个弦交在同一点，求这些弦把圆内部分成的区域的数量。
去掉圆周的弧剩下的构成一个图， 弦的交点的数量${n\choose 4}$，且这些交点的degree是4。其他在圆周上的$n$个上顶点，他们的degree为$n-1$。
正多面体由两个参数决定，a) 顶点处相遇的面的个数，记为$m$，b) 面是正多边形，多边形的边数，记为$n$。
所有可能的正多面体$(m,n)$是$(3,3),(3,4),(4,3),(3,5),(5,3)$。
面只有正5边形和6边形的多面体：正5边形的内角，5边形可以分成3个三角形，所以内角的和是$3\pi$，每个内角为$\frac{3\pi}{5}$。正6边形的内角为$\frac{2\pi}{3}$。考虑多面体的顶点，最多有3个面可以相遇，因为不论如何组合，4个角的和都大于$2\pi$。
多面体的事实给出如下两个关系：a) 每个顶点的degree为3，所以整个图的degree为3p。 b)面的degree为$5x+6x$，$x,y$为两种正多边形的个数。
图论给出另外两个关系：a)欧拉公式。b)整个图的degree为边数的2倍。
上面的关系可以导出$x=12$，也就是这种多面体的正5边形的个数为12。
Euler path(cycle) $x_1, \cdots, x_n$最主要的性质是包括所有的边，并且只包含一次，长度是定的，边的个数。
Hamilton path(cycle) $y_1, \cdots, y_n$最主要的性质是包括所有的顶点，并且只包含一次，节点数是定的，顶点的个数。
Euler path：节点是可以经过两次的， Hamilton path：不必经过每条边。
"节点不重复"是比"边不重复"强的要求，前者可推出后者。
2) Cycle是很重要的一个刻画图的属性：
1) 连通无cycle是树
2) 节点数大于等于2的树必然有2个节点的degree是1，也就是叶子。反过来如果一个图的最小degree大于1，那么必然不是树，必然有cycle。
3) 如果一个图如果只有一个cycle，那么这个图就是这个cycle加上一些根植在其上的树，如果不是树那么和只有一个cycle矛盾。
4) 如果一个图没有没有长度为奇数的cycle，那么这个图是两部图。
首先注意到，对于一个tree来说，连接任何两叶子个节点，也就是加入一个边，必然得到一个Cycle。
Fundamental Cycle：设$T$是图$G$的一个span tree，加入任何一个$G$的边到$T$里，得到的Cycle称为Fundamental Cycle。注意Fundamental Cycle必须依赖于span tree的选择，但是他们的个数是定的。
性质：图$G(V,E)$的Fundamental Cycle的个数是图的边的数量减去span tree的边的数量，也就是$|E|-(n-1)$。
性质：图的任何Cycle都是Fundamental Cycle的组合。
3) 图的同构，定义为a)存在一组标签，两图的端点同用这一组标签，b)任意两个标签之间的边数是相等的。
Labelled Tree的意思是，考虑上面的同构的定义，如果同一个树，用一组标签，但是标注的顶点不一样，这样可以看成两个tree，如果这两个tree不满足同构的定义，那么认为是两个Labelled Tree。当然本身不同构的tree自然是不同的Labelled Tree
顶点个数为$n$的Labelled Tree的个数$T(n)=n^{n-2}$
5) 平面图
桥，平面图的桥只和一个face就是边界face接触，不是桥的边都和两个face接触。
平面图的欧拉公式：$$V-E+R=2$$ 平面图把平面分成不同的region，region的度是其接触的边的数量，如果一个region接触了一个边两次，计数region的度的时候算两次，则所有region的度的和是边的数量的2倍。
$K_{3,3}$不是平面图：region的边界显然是cycle，而$K_{3,3}$没有奇数边的cycle，所以它里面的cycle边的数量都大于等于4，也就是region的度大于等于4；通过欧拉公式可得如果$K_{3,3}$是平面图的话，region的个数是5，这给出了一个region度和的下界5*4=20，但是我们知道这个和其实是边数量的2倍，也就是18，矛盾。
圆和弦分的区域
$n$个点分布在圆上，任取两个点，画一个弦，假设没有三个弦交在同一点，求这些弦把圆内部分成的区域的数量。
去掉圆周的弧剩下的构成一个图， 弦的交点的数量${n\choose 4}$，且这些交点的degree是4。其他在圆周上的$n$个上顶点，他们的degree为$n-1$。
正多面体由两个参数决定，a) 顶点处相遇的面的个数，记为$m$，b) 面是正多边形，多边形的边数，记为$n$。
所有可能的正多面体$(m,n)$是$(3,3),(3,4),(4,3),(3,5),(5,3)$。
面只有正5边形和6边形的多面体：正5边形的内角，5边形可以分成3个三角形，所以内角的和是$3\pi$，每个内角为$\frac{3\pi}{5}$。正6边形的内角为$\frac{2\pi}{3}$。考虑多面体的顶点，最多有3个面可以相遇，因为不论如何组合，4个角的和都大于$2\pi$。
多面体的事实给出如下两个关系：a) 每个顶点的degree为3，所以整个图的degree为3p。 b)面的degree为$5x+6x$，$x,y$为两种正多边形的个数。
图论给出另外两个关系：a)欧拉公式。b)整个图的degree为边数的2倍。
上面的关系可以导出$x=12$，也就是这种多面体的正5边形的个数为12。
2012/02/27
离散化：差分
微分
定义函数的差分：
$$\Delta f(x)=f(x+1)-f(x)$$
类比指数函数的导数
$$\frac{d}{dx}x^m=mx^{m-1}$$
差分对falling power有类似的公式(对负的m<-1也成立)：
$$\Delta x^{\underline{m}}=mx^{\underline{m-1}}$$
其中falling power \(x^{\underline{m}}\)定义为：
$$x^{\underline{m}}=x(x-1)(x-2)\cdots (x-(m-1))$$
\(m=-1\)的时候，调和数列的差分是\(\frac{1}{x+1}\)
积分
如果\(\Delta F(x)=f(x)\)，显然\(F(x)\)是可以差一个常数\(C\).\(F(x)\)类似\(f(x)\)的积分。回忆对连续函数的定积分公式，公式的一边是积分在两个边界取值的差，一边实际是一个和式。
$$diff=F(b)-F(a)=\int_a^bf(x)dx=sum$$
对差分有类似的公式, \(\Delta F(x)=f(x)=F(x+1)-F(x)\)：
$$F(b)-F(a)=\sum_{x=a}^{b-1}f(x)$$
指数函数\(e^x\)
对差分来说，\(2^x\)有类似的导数性质：
$$\Delta 2^x=2^{x+1}-2^x=2^x$$
分部积分
在微积分里分部积分是从乘积的导数推出的方法，对差分来说，乘积的差分有下面公式：
$$\Delta(u(x)v(x))=v(x+1)\Delta u(x)+u(x)\Delta v(x)$$
定义函数的差分：
$$\Delta f(x)=f(x+1)-f(x)$$
类比指数函数的导数
$$\frac{d}{dx}x^m=mx^{m-1}$$
差分对falling power有类似的公式(对负的m<-1也成立)：
$$\Delta x^{\underline{m}}=mx^{\underline{m-1}}$$
其中falling power \(x^{\underline{m}}\)定义为：
$$x^{\underline{m}}=x(x-1)(x-2)\cdots (x-(m-1))$$
\(m=-1\)的时候，调和数列的差分是\(\frac{1}{x+1}\)
积分
如果\(\Delta F(x)=f(x)\)，显然\(F(x)\)是可以差一个常数\(C\).\(F(x)\)类似\(f(x)\)的积分。回忆对连续函数的定积分公式，公式的一边是积分在两个边界取值的差，一边实际是一个和式。
$$diff=F(b)-F(a)=\int_a^bf(x)dx=sum$$
对差分有类似的公式, \(\Delta F(x)=f(x)=F(x+1)-F(x)\)：
$$F(b)-F(a)=\sum_{x=a}^{b-1}f(x)$$
指数函数\(e^x\)
对差分来说，\(2^x\)有类似的导数性质：
$$\Delta 2^x=2^{x+1}-2^x=2^x$$
分部积分
在微积分里分部积分是从乘积的导数推出的方法，对差分来说，乘积的差分有下面公式：
$$\Delta(u(x)v(x))=v(x+1)\Delta u(x)+u(x)\Delta v(x)$$
离散化：一个数学期望的引理
引理：\(Y\)是一个非负的连续随机变量，那么\(Y\)的期望
$$E[Y]=\int_0^\infty P\{Y > y\}dy$$
证明的方法是利用交换积分的技巧。不过我们先考虑离散的情况。
\(X\)是一个离散的随机变量，\(P\{X = i\} = p_i\)，那么\(X\)的期望可以写成：
$$\begin{array}{lcr}
E[X] &=& 1p_1 + 2p_2 + 3p_3 + \cdots + np_n \\
&=& 1p_1 + 1p_2 + 1p_3 + \cdots + 1p_n \\
& & + 1p_2 + 1p_3 + \cdots + 1p_n \\
& & + 1p_3 + \cdots + 1p_n \\
& & + \cdots + 1p_n \\
& & + 1p_n \\
\end{array}$$
把三角形竖着求和得到期望的定义表达方式， 如果每行求和，然后再求和得另一种表达方式
$$\sum_{j=1}^n\sum_{i=j}^nP_i=\sum_{j=1}^nP\{X\geq j\}$$
$$E[Y]=\int_0^\infty P\{Y > y\}dy$$
证明的方法是利用交换积分的技巧。不过我们先考虑离散的情况。
\(X\)是一个离散的随机变量，\(P\{X = i\} = p_i\)，那么\(X\)的期望可以写成：
$$\begin{array}{lcr}
E[X] &=& 1p_1 + 2p_2 + 3p_3 + \cdots + np_n \\
&=& 1p_1 + 1p_2 + 1p_3 + \cdots + 1p_n \\
& & + 1p_2 + 1p_3 + \cdots + 1p_n \\
& & + 1p_3 + \cdots + 1p_n \\
& & + \cdots + 1p_n \\
& & + 1p_n \\
\end{array}$$
把三角形竖着求和得到期望的定义表达方式， 如果每行求和，然后再求和得另一种表达方式
$$\sum_{j=1}^n\sum_{i=j}^nP_i=\sum_{j=1}^nP\{X\geq j\}$$
Subscribe to:
Posts (Atom)