您好,欢迎访问三七文档
[ADN.cn][library]summary图论总结2020-4-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-4-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-4-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-4-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)
本文标题:图论总结(超强大)
链接地址:https://www.777doc.com/doc-5121906 .html