图论 Graph Theory

《图论 Graph Theory》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、m图论总结2021-7-17(如果只能看到目录，请选择视图，然后选择普通视图)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.

2、1.邻接矩阵Adjacencymatrix1.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.路径与回路Pathsandcircuits

3、1.5.1.欧拉路径或回路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-sourceshortestpaths33/33m图论总结2021-7-171.6.2.1.1.基本算法

5、Basicalgorithms1.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.基本算法Basicalgorithms1.6.2.2

6、.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.预流推进算法Preflowpushmethod1.6.3.1.1.2.1.

7、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.网络单纯形N