图论学习总结(超强大)

图论学习总结(超强大)

ID:45601465

大小:955.74 KB

页数:33页

时间:2019-11-15

图论学习总结(超强大)_第1页
图论学习总结(超强大)_第2页
图论学习总结(超强大)_第3页
图论学习总结(超强大)_第4页
图论学习总结(超强大)_第5页
资源描述:

《图论学习总结(超强大)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、'1.图论GraphTheory1.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、.2.关联矩阵Incidencematrix1.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.欧拉路径或

3、回路Eulerianpath1.5.1.1.无向图1.5.1.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.

4、基本算法Basicalgorithms1.6.1.1.1.Prim1.6.1.1.2.Kruskal1.6.1.1.3.Sollin(Boruvka)1.6.1.2.扩展模型Extendedmodels1.6.1.2.1.度限制生成树Minimumdegree-boundedspanningtrees1.6.1.2.2.k小生成树Thekminimumspanningtreeproblem(k-MST)1.6.2.最短路Shortestpaths1.6.2.1.单源最短路Single-sourceshortestpaths1.6.2.1.1.基本算法Basi

5、calgorithms'1.6.2.1.1.1.Dijkstra1.6.2.1.1.2.Bellman-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.基本算法Basicalgori

6、thms1.6.2.2.1.1.Floyd-Warshall1.6.2.2.1.2.Johnson1.6.3.网络流Flownetwork1.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.预流推进算法Preflow

7、pushmethod1.6.3.1.1.2.1.Push-relabel1.6.3.1.1.2.2.Relabel-to-front1.6.3.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.

8、匹配Matching1.6.4.1.二分图Bipar

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。