图论模型的建立与转化.doc

图论模型的建立与转化1 图论基础：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资源有两个词典，在：/cgi-bin/caldwell/tutor/departments/math/graph/glossary/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-13.G1-C, G1-C4.f-25.EMBEDDABLE-true6.while fm-2+2 and EMBEDDABLE do begin7 找G关于Gi的每一个片B8 对每一个片B，求F(B,Gi)9 若对于某一个B，F(B,Gi)为空，G为非可平面图，结束。10 if EMBEDDABLE then begin11 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+P14 将Pi画到Gi的面F内，得到Gi+1的平面嵌入Gi+115 i-i+116 f=右边和左边=右边即可。算法终止于完全图。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和,其中XY就是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)，并且满足：d1=di1=di2=. l(l=1),则P(ik)不可能是P(il)的一部分。再由引理1可得dil= min dij + Wij,il 1=j l这样，逐步确定di1,di2,di3直到全部。从证明中大家可能注意到了，只要满足引理1,2,“最短路”的确切定义是无关紧要的。正如IOI99第二试的第一题交通信号灯，“最短路”是权和加上等待时间，但是因为仍然满足引理1和2，故仍然可以用dijkstra算法。显然，这种dijkstra算法已经是推广了的。对于引理2，如果G有负权，dijkstra算法可能失效。这里推荐采用bellman-ford算