图论总结(超强大).doc

《图论总结(超强大).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图论总结(超强大)1.1.定义与术语DefinitionandGlossary1.1.1.图与网络GraphandNetwork1.1.2.图的术语GlossaryofGraph1.1.3.路径与回路PathandCycle1.1.4.连通性Connectivity1.1.5.图论中特殊的集合Setsingraph1.1.6.匹配Matching1.1.7.树Tree1.1.8.组合优化Combinatorialoptimization1.2.图的表示Expressionsofgraph1.2.1.邻接矩阵Adjacencymatrix1.2.2.关联矩阵Incidencemat

2、rix1.2.3.邻接表Adjacencylist1.2.4.弧表Arclist1.2.5.星形表示Star1.3.图的遍历Travelingingraph1.3.1.深度优先搜索Depthfirstsearch(DFS)1.3.1.1.概念1.3.1.2.求无向连通图中的桥Findingbridgesinundirectedgraph1.3.2.广度优先搜索Breadthfirstsearch(BFS)1.4.拓扑排序Topologicalsort1.5.路径与回路Pathsandcircuits1.5.1.欧拉路径或回路Eulerianpath1.5.1.1.无向图1.5.1

3、.2.有向图1.5.1.3.混合图1.5.1.4.无权图Unweighted1.5.1.5.有权图Weighed—中国邮路问题TheChinesepostproblem1.5.2.HamiltonianCycle哈氏路径与回路1.5.2.1.无权图Unweighted1.5.2.2.有权图Weighed—旅行商问题Thetravellingsalesmanproblem1.6.网络优化Networkoptimization1.6.1.最小生成树Minimumspanningtrees1.6.1.1.基本算法Basicalgorithms1.6.1.1.1.Prim1.6.1.1.

4、2.Kruskal1.6.1.1.3.Sollin（Boruvka）1.6.1.2.扩展模型Extendedmodels1.6.1.2.1.度限制生成树Minimumdegree-boundedspanning35/35trees1.6.1.2.2.k小生成树Thekminimumspanningtreeproblem(k-MST)1.6.2.最短路Shortestpaths1.6.2.1.单源最短路Single-sourceshortestpaths1.6.2.1.1.基本算法Basicalgorithms1.6.2.1.1.1.Dijkstra1.6.2.1.1.2.Bell

5、man-Ford1.6.2.1.1.2.1.Shortest path faster algorithm(SPFA)1.6.2.1.2.应用Applications1.6.2.1.2.1.差分约束系统Systemofdifferenceconstraints1.6.2.1.2.2.有向无环图上的最短路ShortestpathsinDAG1.6.2.2.所有顶点对间最短路All-pairsshortestpaths1.6.2.2.1.基本算法Basicalgorithms1.6.2.2.1.1.Floyd-Warshall1.6.2.2.1.2.Johnson1.6.3.网络流Fl

6、ownetwork1.6.3.1.最大流Maximumflow1.6.3.1.1.基本算法Basicalgorithms1.6.3.1.1.1.Ford-Fulkersonmethod1.6.3.1.1.1.1.Edmonds-Karpalgorithm1.6.3.1.1.1.1.1.Minimumlengthpath1.6.3.1.1.1.1.2.Maximumcapabilitypath1.6.3.1.1.2.预流推进算法Preflowpushmethod1.6.3.1.1.2.1.Push-relabel1.6.3.1.1.2.2.Relabel-to-front1.6.3

7、.1.1.3.Dinicmethod1.6.3.1.2.扩展模型Extendedmodels1.6.3.1.2.1.有上下界的流问题1.6.3.2.最小费用流Minimumcostflow1.6.3.2.1.找最小费用路Findingminimumcostpath1.6.3.2.2.找负权圈Findingnegativecircle1.6.3.2.3.网络单纯形Networksimplexalgorithm1.6.4.匹配Matching1.6.4.1.二分图BipartiteG