图论模型
2001-9-25 大榕树
强烈推荐IOI2000集训队徐静的论文《图论模型的建立与转化》!!!内容比较多，我会一点一点的写，请大家耐心等待...
1 图论基础：这里有几篇英文文章(pdf)，很基础的，大家认真看啊！
Graph Theory
1)图周游
2)最短路问题
3)最小生成树
4)欧拉回路/道路
5)网络流
等大家把这些内容吃透了，在看下面的内容，就会觉得轻松很多。下面，我准备不拘泥于形式，先随便讲，再系统化，如何？
2 知识点回顾下面是一些图论知识点。大家可以看看自己哪些方面还不熟悉。因为大部分书都要讲，这里我就不说了。
1.图的概念。图的定义，图的阶，图的边数，邻接，关联。有向图，加权图。简单图，多重图，广义图。平行边，环(loop)。点度，出度，入度零图，平凡图，正则图，完全图Kn,竞赛图，二分图子图，补图图的同构
2.图的代数表示和计算机表示邻接矩阵/关联矩阵/邻接表/边列表
3.树树的几种等价定义基本关联矩阵,回路矩阵，割集矩阵及其关系。内向树，外向树生成树,最小生成树与生成树计数Huffman树
3.道路与回路道路，回路，简单道路，圈(cycle)道路图Pn, 圈图Cn欧拉道路，回路哈密顿道路，回路旅行商问题中国邮路
4.平面图平面图的定义欧拉公式d=m-n+2,极大平面图极其性质简单平面图的性质，m<=3n-6, d<=2n-4K5,K3,3是非平面图的证明Kuratowski定理对偶图,D过程,五色定理
5.图的着色色数，边色数色数多项式
6.连通性割点，割边和块的几个等价性质断集，断量，边断集，边断量Menger定理，边连通度的判定和其基于网络流的算法DFS算法
7.匹配二分图：最大匹配，完全匹配，最佳匹配, 一般图的最大匹配
8.网络流概念，最小切割-最大流定理ford-fulkerson算法, Edmonds-Karp算法最小费用/最大收益流点容量，流量下界，多源多汇等变形问题
9.最短路dijkstra算法/bellman-ford算法/floyd-warshall算法*johnson算法第k最短路，最短路算法的变形3 INTERNET资源有两个词典，
在：
http://www.utm.edu/cgi-bin/caldwell/tutor/departments/math/graph/glossaryhttp://www.math.fau.edu/locke/graphthe.htm#Index4 一些可能比较陌生的内容和它们的算法思想其中下面的东西可能需要说一下。可能内容难一点，但是我们的目的不是记住这些算法，而是理解算法思想，打开我们的思路。
1.平面性检测:预处理：
a.如果G非连通，应检测每一个连通支
b.如果G存在割点v,应把G从v处分离。G可平面当且仅当每一块是可平面的。
c.移去自环(loop)d.如果v的度为2，且v与v1,v2邻接，删去v,加边(v1,v2)DMP算法(Demoucron, Malgrange, Pertuiset, 1964) P75DMP算法不是最好的，但是比较容易理解，所以就说一下。
* 片的概念设H是G的可平面子图，如果在G-H中存在另一个G的平面子图B，且B和H有2个以上的共同节点，则称B是G中的片，片B与H的公共点称为片B的附着点。 ~记H为G的子图H的一个平面嵌入。算法基本思想就是：先找一个回路C，初始的H<-C每次取一个片B，试图画在已有的图中。只有当B的所有附着点都在H的某一个面f(这样的面的集合叫F(B,H))的边界上，B才能"嵌"在这个面中（自己画一画就会明白）.如果最后把每个B都画完了，就找到了G的一个平面嵌入，如果B画不进去，G就不是可平面图。
* 算法描述1.找G的一个回路C2.i<-1 ~3.G1<-C, G1<-C4.f<-25.EMBEDDABLE<-true6.while f<>m-2+2 and EMBEDDABLE do begin7 找G关于Gi的每一个片B ~8 对每一个片B，求F(B,Gi) ~9 若对于某一个B，F(B,Gi)为空，G为非可平面图，结束。10 if EMBEDDABLE then begin ~ ~11 if 对于某个B，|F(B,Gi)|=1 then F<-F(B,Gi) ~ else 令B是任何一个片，F是集合F(B,Gi)中的任何一个面12 找一条路径PiB, Pi的两个端点是Gi的结点。13 Gi+1<-Gi+P ~ ~14 将Pi画到Gi的面F内，得到Gi+1的平面嵌入Gi+115 i<-i+116 f<-f+117 若f=m-n+2 then G可平面，结束。 end end如果G是可平面的，算法在Gm-n+1时结束。 ~算法递推Gi, f记录Gi的面的数目算法复杂度是O(n^2)如果没有看懂，可以与我联系。有一个更好的O(n)算法，很长，是Hopcroft和Tarjan给出的。
文章是：J. Hopcroft and R. Tarjan. Efficient planarity testing. Journal of the ACM, 21:549--569, 1974. 2.色数多项式定理:f(G,t)代表用t种颜色给G着色的不同方案总数,则f(G,t)是t的多项式，且： _ .记：Gij为加上一条边(vi,vj)得到的图，Gij表示把vi,vj变成一点得到的图。 _ .f(G,t)=f(Gij,t)+f(Gij,t) (vi,vj不相邻)证明很简单。用加法原理，第一种为vi,vj顶点不同色,一种是同色。剩下的不用我说了吧^_^两种特殊的图G为完全图：f(G,t)=t(t-1)(t-2)..(t-n+1)G为树f(G,t)=t(t-1)^(n-1)结论是显然的，自己证明吧。这个证明的思想可以用来求色数，即： _ .X(G)=min{X(Gij),X(Gij)} (vi,vj不相邻)证明需要得到左边>=右边和左边<=右边即可。算法终止于完全图。X(Kr)=r3.逻辑算法逻辑运算的法则是：X+Y=Y+X XY=YX(X+Y)+Z=X+(Y+Z) (XY)Z=X(YZ)X(Y+Z)=XY+XZ (Y+Z)X=XY+XZ(吸收律)X+X=X XX=X X+XY=X有的数用V和^,其中X^Y就是XY,XVY就是X+Y极小支配集的公式： n __ ||(Vi + sum(u))i =1 u与vi相邻 最后展开成积之和的形式，每一项是一个极小支配集。例如图的邻接矩阵是 v1 v2 v3 v4 v5 v6v1 0 1 1 1 0 0v2 1 0 0 1 0 0v3 1 0 0 1 0 0v4 1 1 1 0 1 1v5 0 0 0 1 0 0v6 0 0 0 1 0 0计算方法是：(v1+v2+v3+V4)(v2+v1+V4)(v3+v1+v4)(v4+v1+v2+v3+v5+v6)(v5+v4+v6)(v6+v4+v5)(懒得写v了)=15+16+4+235+236极小覆盖集：n__ __||(Vi + ||u)i=1 u与vi相邻从G中去掉极小覆盖集，得到极大独立集。请大家自己证明这两个公式和定律。5 对一些问题的探讨1.dijkstra算法: 局限性，推广和其他算法。首先，我们来证明dijkstra算法的正确性。引理1（Lemma 1）正权图中P(i)为v1到vi的最短路，vj属于P(i),则P(j)是v1到vj的一条最短路。引理2 正权图中任意一条最短路的长度大于其局部路径的长度。这两个结论是显然的。假设已经得到从v1到其余各点的最短路P(ik)(k=1,2,3..n)，并且满足：d[1]=d[i1]<=d[i2]<=..<=d[in]由引理2知道，若k > l(l>=1),则P(ik)不可能是P(il)的一部分。再由引理1可得d[il]= min { d[ij] + W[ij,il] } 1<=j < l这样，逐步确定d[i1],d[i2],d[i3]直到全部。从证明中大家可能注意到了，只要满足引理1,2,“最短路”的确切定义是无关紧要的。正如IOI99第二试的第一题《交通信号灯》，“最短路”是权和加上等待时间，但是因为仍然满足引理1和2，故仍然可以用dijkstra算法。显然，这种dijkstra算法已经是推广了的。对于引理2，如果G有负权，dijkstra算法可能失效。这里推荐采用bellman-ford算法:a. d[1]:=1 d
:=maxint i=2,3,..nb.for i:=2 to n do d:=min{ d, min{d[j]+w[j,i]} } j到i有通路c. 若全部d都没有变化，结束，否则转b.b也叫做松弛操作。由于d在减小且有下界（真实的最短路）,算法必将收敛。当然，如果有负权回路，就不行了，呵呵。幸亏可以证明，没有负权回路时，算法最多迭代n-1次。如果在第n次迭代的时候仍有边发生变化，只能说明...在最坏情况下Ford算法的的时间复杂度是O(mn)Ford主要取决于松弛操作的次数。这样当负权边少时，可以忽略负权边，用dijkstra算法得到一个最短路的上界，取代初始化步骤a,可以加快速度。[ 此贴被李逍遥在2005-11-10 22:53重新编辑 ]
