资源描述：
《图论模型的建立与转化》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、图论模型的建立与转化1图论基础：1)图周游2)最短路问题3)最小生成树4)欧拉回路/道路5)网络流2知识点回顾1.图的概念。图的定义，图的阶，图的边数，邻接，关联。有向图，加权图。简单图，多重图，广义图。平行边，环(loop)。点度，出度，入度零图，平凡图，正则图，完全图Kn,竞赛图，二分图子图，补图图的同构2.图的代数表示和计算机表示邻接矩阵/关联矩阵/邻接表/边列表3.树树的几种等价定义基本关联矩阵,回路矩阵，割集矩阵及其关系。内向树，外向树生成树,最小生成树与生成树计数Huffman树3.道路与回路道路，回路，简单道路，圈(cyc
2、le)道路图Pn,圈图Cn欧拉道路，回路哈密顿道路，回路旅行商问题中国邮路4.平面图平面图的定义欧拉公式d=m-n+2,极大平面图极其性质简单平面图的性质，m<=3n-6,d<=2n-4K5,K3,3是非平面图的证明Kuratowski定理对偶图,D过程,五色定理5.图的着色色数，边色数色数多项式6.连通性割点，割边和块的几个等价性质断集，断量，边断集，边断量Menger定理，边连通度的判定和其基于网络流的算法DFS算法7.匹配二分图：最大匹配，完全匹配，最佳匹配,一般图的最大匹配8.网络流概念，最小切割-最大流定理ford-fulke
3、rson算法,Edmonds-Karp算法最小费用/最大收益流点容量，流量下界，多源多汇等变形问题9.最短路dijkstra算法/bellman-ford算法/floyd-warshall算法*johnson算法第k最短路，最短路算法的变形3INTERNET资源有两个词典，在：http://www.utm.edu/cgi-bin/caldwell/tutor/departments/math/graph/glossaryhttp://www.math.fau.edu/locke/graphthe.htm#Index4一些可能比较陌生的内
4、容和它们的算法思想其中下面的东西可能需要说一下。可能内容难一点，但是我们的目的不是记住这些算法，而是理解算法思想，打开我们的思路。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
5、中存在另一个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
6、<-true6.whilef<>m-2+2andEMBEDDABLEdobegin7找G关于Gi的每一个片B8对每一个片B，求F(B,Gi)9若对于某一个B，F(B,Gi)为空，G为非可平面图，结束。10ifEMBEDDABLEthenbegin11if对于某个B，
7、F(B,Gi)
8、=1thenF<-F(B,Gi)else令B是任何一个片，F是集合F(B,Gi)中的任何一个面12找一条路径PiB,Pi的两个端点是Gi的结点。13Gi+1<-Gi+P14将Pi画到Gi的面F内，得到Gi+1的平面嵌入Gi+115i<-i+116f<-f+1
9、17若f=m-n+2thenG可平面，结束。endend如果G是可平面的，算法在Gm-n+1时结束。算法递推Gi,f记录Gi的面的数目算法复杂度是O(n^2)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不相邻)两种特殊的图G为完全图：f(G,t)=t(t-1)(t-2)..(t-n+1)G为树f(G,t)=t(t-1)^(n-1)结论是显
10、然的这个证明的思想可以用来求色数，即：X(G)=min{X(Gij),X(Gij)}(vi,vj不相邻)证明需要得到左边>=右边和左边<=右边即可。算法终止于完全图。X(Kr)=r3.逻辑算法逻辑运算的法则
