图论总结(超强大)

《图论总结(超强大)》由会员分享，可在线阅读，更多相关《图论总结(超强大)（11页珍藏版）》请在装配图网上搜索。

1、图论总结(超强大) - ADNlibrarysummary 图论总结 2022-12-21 1. 图论 Graph Theory 1.1. 定义与术语 Definition and Glossary 1.1.1. 图与网络 Graph and work 1.1.2. 图的术语 Glossary of Graph 1.1.3. 途径与回路 Path and Cycle 1.1.4. 连通性 Connectivity 1.1.5. 图论中特殊的集合 Sets in graph 1.1.6. 匹配 Matching 1.1.7. 树 Tree 1.1.8. 组合优化 binatorial optim

2、ization 1.2. 图的表示 Expressions of graph 1.2.1. 邻接矩阵 Adjacency matrix 1.2.2. 关联矩阵 Incidence matrix 1.2.3. 邻接表 Adjacency list 1.2.4. 弧表 Arc list 1.2.5. 星形表示 Star 1.3. 图的遍历 Traveling in graph 1.3.1. 深度优先搜索 Depth first search (DFS) 1.3.1.1. 概念 1.3.1.2. 求无向连通图中的桥 Finding bridges in undirected graph 1.3.2.

3、 广度优先搜索 Breadth first search (BFS) 1.4. 拓扑排序 Topological sort 1.5. 途径与回路 Paths and circuits 1.5.1. 欧拉途径或回路 Eulerian path 1.5.1.1. 无向图 1.5.1.2. 有向图 1.5.1.3. 混合图 1.5.1.4. 无权图 Unweighted 1.5.1.5. 有权图 Weighed 中国邮路问题The Chinese post problem 1.5.2. Hamiltonian Cycle 哈氏途径与回路 1.5.2.1. 无权图 Unweighted 1.5.2.2

4、. 有权图 Weighed 旅行商问题The travelling salesman problem 1.6. 网络优化 work optimization 1.6.1. 最小生成树 Minimum spanning trees 1.6.1.1. 根本算法 Basic algorithms 1.6.1.1.1. Prim 1.6.1.1.2. Kruskal 1.6.1.1.3. SollinBoruvka 1.6.1.2.1. 度限制生成树 Minimum degree-bounded spanning trees 1.6.1.2.2. k小生成树 The k minimum spannin

5、g tree problem(k-MST) 1.6.2. 最短路Shortest paths 1.6.2.1. 单最短路 Single-source shortest paths 1.6.2.1.1. 根本算法 Basic algorithms 1/33 ADNlibrarysummary 图论总结 2022-12-21 1.6.2.1.1.1. . Dijkstra 1.6.2.1.1.2. . Bellman-Ford 1.6.2.1.1.2.1. .Shortest path faster algorithm(SPFA) 1.6.2.1.2. 应用Applications 1.6.2.1

6、.2.1. . 差分约束系统 System of difference constraints 1.6.2.1.2.2. . 有向无环图上的最短路 Shortest paths in DAG 1.6.2.2. 所有顶点对间最短路 All-pairs shortest paths 1.6.2.2.1. 根本算法 Basic algorithms 1.6.2.2.1.1. . Floyd-Warshall 1.6.2.2.1.2. . Johnson 1.6.3. 网络流 Flow work 1.6.3.1. 最大流 Maximum flow 1.6.3.1.1. 根本算法 Basic algor

7、ithms 1.6.3.1.1.1. . Ford-Fulkerson method 1.6.3.1.1.1.1. . Edmonds-Karp algorithm 1.6.3.1.1.1.1.1. . Minimum length path 1.6.3.1.1.1.1.2. . Maximum capability path 1.6.3.1.1.2. . 预流推进算法 Preflow push method 1.6.3.1.2.1. . 有上下界的流问题 1.6.3.2. 最小费用流 Minimum cost flow 1.6.3.2.1. 找最小费用路 Finding minimum co

8、st path 1.6.3.2.2. 找负权圈 Finding negative circle 1.6.3.2.3. 网络单纯形 work simplex algorithm 1.6.4. 匹配 Matching 1.6.4.1. 二分图 Bipartite Graph 1.6.4.1.1. 无权图-匈牙利算法 Unweighted - Hopcroft and Karp algorithm 1.6.4.1.2. 带权图-KM算法 Weighted Kuhn-Munkres(KM) algorithm 1.6.4.2. 一般图General Graph 1.6.4.2.1. 无权图-带花树算法

9、 Unweighted - Blossom (Edmonds) 2/33 ADNlibrarysummary 图论总结 2022-12-21 1. 图论 Graph Theory 1.1. 定义与术语 Definition and Glossary 1.1.1. 图与网络 Graph and work 二元组?V,E?称为图(graph)。V为结点(node)或顶点(vertex)集。E为V中结点之间的边的集合。 点对?u,v?称为边(edge)或称弧(arc)，其中u,v?V，称u,v是相邻的(adjacent)，称u,v与边?u,v?相关联(incident)或相邻。 假设边的点对?u,v

10、?有序那么称为有向(directed)边，其中u称为头(head)，v称为尾(tail)。所形成的图称有向图(directed graph)。为对于u来说?u,v?是出边(outgoing arc)；对于v来说?u,v?是入边(ining arc)。反之，假设边的点对无序那么称为无向(undirected)边，所形成的图称无向图(undirected graph)。 假设图的边有一个权值(weight)，那么称为赋权边，所形成的图称赋权图(weighted graph)或网络(work)。用三元组G(V,E,W)表示网络。其中W表示权集，它的元素与边集E一一对应。 满足|E|?|V|log|V

11、|的图，称为稀疏(sparse)图；反之，称为稠密(dense)图。 1.1.2. 图的术语 Glossary of Graph 阶(order)：图G中顶点集V的大小称作图G的阶。 环(loop)：假设一条边的两个顶点为同一顶点，那么此边称作环。 简单图(simple graph)：没有环、且没有多重弧的图称作简单图。 定向图：对无向图G的每条无向边指定一个方向得到的有向图。 底图：把一个有向图的每一条有向边的方向都去掉得到的无向图。 逆图：把一个有向图的每条边都反向由此得到的有向图。 竞赛图(tournament)：有向图的底图是无向完全图，那么此有向图是竞赛图。 邻域(neighborh

12、ood)：在图中与u相邻的点的集合v|v?V,(u,v)?E，称为u的邻域，记为N(u)。 度： 度(degree)：一个顶点的度是指与该边相关联的边的条数，顶点v的度记作deg(v)。握手3/33 ADNlibrarysummary 图论总结 2022-12-21 定理：无向图：?deg(v)?2|E|；有向图：?deg?(v)-deg?(v)。 v?Vv?Vv?V入度(indegree)：在有向图中，一个顶点v的入度是指与该边相关联的入边(即边的尾是v)的条数，记作deg?(v)。 出度(outdegree)：在有向图中，一个顶点的出度是指与该边相关联的出边(即边的头是v)的条数，记作de

13、g?(v)。 孤立点(isolated vertex)：度为0的点。叶(leaf)：度为1的点。 (source)：有向图中，deg?(v)=0 的点。汇(sink)：有向图中，deg?(v)=0的点。 奇点(odd vertex)：度为奇数的点。偶点(even vertex)：度为偶数的点。 子图： 子图(sub-graph)：G称作图G的子图假如V(G)?V(G)以及E(G)?E(G)。 生成子图(spanning sub-graph)：即包含G 的所有顶点的连通子图，即满足条件V(G)?V(G的)G的子图G。 生成树(spanning tree)：设T是图G的一个子图，假如T是一棵树，且

14、V(T)?V(G)，那么称T是G的一个生成树。即G的生成子图，且子图为树。 点导出子图(induced subgraph)：设V-V(G)，以V?为顶点集，以两端点均在V?中的边的全体为边集所组成的子图，称为G的由顶点集V?导出的子图，简称为G的点导出子图，记为GV?。 边导出子图(edge-induced subgraph)：设E-E(G)，以E?为顶点集，以两端点均在E?中的边的全体为边集所组成的子图，称为G的由边集E?导出的子图，简称为G的边导出子图，记为GE?。 图的补图(plement)：设G是一个图，以V(G)为顶点集，以(u,v)|(u,v)?E(G)为边集的图称为G的补图，记为

15、G。 点集的补集：记 V?V?V为点集V的补集。 特殊的图： 零图(null graph)：E-，即只有孤立点的图。n阶零图记为Nn。 平凡图(trivial graph)：一阶零图。 空图(empty graph)：V?E-的图。 4/33 ADNlibrarysummary 图论总结 2022-12-21 有向无环图(directed acyclic graph(DAG)：有向的无环的图。 完全图(plete graph)：完全图是指每一对不同顶点间都有边相连的的无向图，n阶完全图常记作Kn。 二分图bipartite graph：假设图G的顶点集可划分为两个非空子集X和Y，即V?X?Y且

16、X?Y-，且每一条边都有一个顶点在X中，而另一个顶点在Y中，那么这样的图称作二分图。 完全二分图(plete bipartite graph)：二分图G中假设任意两个X和Y中的顶点都有边相连，那么这样的图称作完全二分图。假设|X|?m,|Y|?n，那么完全二分图G记作Km,n。 正那么图(regular graph)：假如图中所有顶点的度皆相等，那么此图称为正那么图。 1.1.3. 途径与回路 Path and Cycle 途径(walk)：图G中一个点边交替出现的序列p?vi0ei1vi1ei2?eikvik，满足vij?V,eij?E，eij?(vij?1,vij)。 迹(trail)：边

17、不重复的途径。 路(path)：顶点不重复的迹。 简单图中的路可以完全用顶点来表示，P?vi0vi1?vik。 假设p1?pm，称闭的(closed)；反之，称为开的(open)。 闭途径(closed walk)：起点和终点一样的途径。 闭迹(closed trail)：起点和终点一样的迹，也称为回路(circuit)。 圈(cycle)：起点和终点一样的路。 途径闭途径、迹闭迹、路圈上所含的边的个数称为它的长度(length)。 简单图G中长度为奇数和偶数的圈分别称为奇圈(odd cycle)和偶圈(even cycle)。 对任意u,v?V(G)，从x到y的具有最小长度的路称为x到y的最短路(shortest path)，其长度称为x到y的间隔 (distance)，记为dG(u,v)。 图G的直径(diameter)：D?maxdG(u,v)|?u,v?V(G)。 简单图G中最短圈的长度称为图G的围长(girth)，最长圈的长度称为图G的周长(perimeter)。 1.1.4. 连通性 Connectivity 连通(connected)：在图G中，两个顶点间，至少存在一条途径，称两个顶点连通的5/33 第 11 页 共 11 页