图论总结(超强大)

..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...............................................关联矩阵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.拓扑排序Topologicalsort..1.5.路径与回路Pathsandcircuits1.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.基本算法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.................................基本算法Basicalgorithms..1.6.2.1.1.1.............................................Dijkstra1.6.2.1.1.2.........................................Bellman-Ford1.6.2.1.1.2.1........Shortestpathfasteralgorithm(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......................................................网络流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...................................Push-relabel1.6.3.1.1.2.2..............................Relabel-to-front1.6.3.1.1.3.........................................Dinicmethod1.6.3.1.2..................................扩展模型Extendedmodels..1.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.二分图BipartiteGraph1.6.4.1.1.无权图-匈牙利算法Unweighted-HopcroftandKarpalgorithm1.6.4.1.2...带权图-KM算法Weighted–Kuhn-Munkres(KM)algorithm1.6.4.2.一般图GeneralGraph1.6.4.2.1.......无权图-带花树算法Unweighted-Blossom(Edmonds)1.图论GraphTheory1.1.定义与术语DefinitionandGlossary1.1.1.图与网络GraphandNetwork二元组,VE称为图(graph)。V为结点(node)或顶点(vertex)集。E为V中结点之间的边的集合。点对,uv称为边(edge)或称弧(arc)，其中,uvV，称,uv是相邻的(adjacent)，称u,v与边,uv相关联(incident)或相邻。若边的点对,uv有序则称为有向(directed)边，其中u称为头(head)，v称为尾(tail)。..所形成的图称有向图(directedgraph)。为对于u来说,uv是出边(outgoingarc)；对于v来说,uv是入边(incomingarc)。反之，若边的点对无序则称为无向(undirected)边，所形成的图称无向图(undirectedgraph)。若图的边有一个权值(weight)，则称为赋权边，所形成的图称赋权图(weightedgraph)或网络(network)。用三元组G(V,E,W)表示网络。其中W表示权集，它的元素与边集E一一对应。满足||||log||EVV的图，称为稀疏(sparse)图；反之，称为稠密(dense)图。1.1.2.图的术语GlossaryofGraph阶(order)：图G中顶点集V的大小称作图G的阶。环(loop)：若一条边的两个顶点为同一顶点，则此边称作环。简单图(simplegraph)：没有环、且没有多重弧的图称作简单图。定向图：对无向图G的每条无向边指定一个方向得到的有向图。底图：把一个有向图的每一条有向边的方向都去掉得到的无向图。逆图：把一个有向图的每条边都反向由此得到的有向图。竞赛图(tournament)：有向图的底图是无向完全图，则此有向图是竞赛图。邻域(neighborhood)：在图中与u相邻的点的集合{|,(,)}vvVuvE，称为u的邻域，记为()Nu。度：度(degree)：一个顶点的度是指与该边相关联的边的条数，顶点v的度记作deg(v)。握手定理：无向图：deg()2||vVvE；有向图：deg()deg()vVvVvv。..入度(indegree)：在有向图中，一个顶点v的入度是指与该边相关联的入边(即边的尾是v)的条数，记作deg()v。出度