图论总结-by-Amber

[ADN.cn][library]summary图论总结2020-6-291/331.图论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.拓扑排序Topologicalsort1.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[ADN.cn][library]summary图论总结2020-6-292/331.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.扩展模型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.二分图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)[ADN.cn][library]summary图论总结2020-6-293/331.图论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)。握手[ADN.cn][library]summary图论总结2020-6-294/33定理：无向图：deg()2||vVvE；有向图：deg()deg()vVvVvv。入度(indegree)：在有向图中，一个顶点v的入度是指与该边相关联的入边(即边的尾是v)的条数，记作deg()v。出度(outdegree)：在有向图中，一个顶点的出度是指与该边相关联的出边(即边的头是v)的条数，记作deg()v。孤立点(isolatedvertex)：度为0的点。叶(leaf)：度为1的点。源(source)：有向图中，deg()v=0的点。汇(sink)：有向图中，deg()v=0的点。奇点(oddvertex)：度为奇数的点。偶点(evenvertex)：度为偶数的点。子图：子图(sub-graph)：G'称作图G的子图如果(')()VGVG以及(')()EGEG。生成子图(spanningsub-graph)：即包含G的所有顶点的连通子图，即满足条件(')()VGVG的G的子图G’。生成树(spanningtree)：设T是图G的一个子图，如果T是一棵树，且()()VTVG，则称T是G的一个生成树。即G的生成子图，且子图为树。点导出子图(inducedsubgraph)：设)(GVV，以V为顶点集，以两端点均在V中的边的全体为边集所组成的子图，称为G的由顶点集V导出的子图，简称为G的点导出子图，记为[]GV。边导出子图(edge-inducedsubgraph)：设)(GEE，以E为顶点集，以两端点均在E中的边的全体为边集所组成的子图，称为G的由边集E导出的子图，简称为G的边导出子图，记为][EG。图的补图(complement)