[ADN.cn][library]summary 图论总结 2013-12-21
1. 图论 Graph Theory
1.1. 定义与术语 Definition and Glossary
1.1.1. 图与网络 Graph and Network 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. 组合优化 Combinatorial optimization 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. 广度优先搜索 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. 有权图 Weighed — 旅行商问题The travelling salesman problem
1.6. 网络优化 Network 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. Sollin（Boruvka）
1.6.1.2. 扩展模型 Extended models
1.6.1.2.1. 度限制生成树 Minimum degree-bounded spanning trees 1.6.1.2.2. k小生成树 The k minimum spanning 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
[ADN.cn][library]summary 图论总结 2013-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.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 network
1.6.3.1. 最大流 Maximum flow
1.6.3.1.1. 基本算法 Basic algorithms
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.1.2.1. ................................................................................. Push-relabel 1.6.3.1.1.2.2. .......................................................................... Relabel-to-front 1.6.3.1.1.3. .......................................................................................... Dinic method 1.6.3.1.2. 扩展模型 Extended models
1.6.3.1.2.1. ............................................................................... 有上下界的流问题
1.6.3.2. 最小费用流 Minimum cost flow
1.6.3.2.1. 找最小费用路 Finding minimum cost path 1.6.3.2.2. 找负权圈 Finding negative circle
1.6.3.2.3. 网络单纯形 Network 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. 无权图-带花树算法 Unweighted - Blossom (Edmonds)
2/33
[ADN.cn][library]summary 图论总结 2013-12-21
1. 图论 Graph Theory
1.1. 定义与术语 Definition and Glossary 1.1.1. 图与网络 Graph and Network
二元组?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?有序则称为有向(directed)边，其中u称为头(head)，v称为尾(tail)。所形成的图称有向图(directed graph)。为对于u来说?u,v?是出边(outgoing arc)；对于v来说?u,v?是入边(incoming arc)。反之，若边的点对无序则称为无向(undirected)边，所形成的图称无向图(undirected graph)。
若图的边有一个权值(weight)，则称为赋权边，所形成的图称赋权图(weighted graph)或网络(network)。用三元组G(V,E,W)表示网络。其中W表示权集，它的元素与边集E一一对应。
满足|E|?|V|log|V|的图，称为稀疏(sparse)图；反之，称为稠密(dense)图。
1.1.2. 图的术语 Glossary of Graph
阶(order)：图G中顶点集V的大小称作图G的阶。
环(loop)：若一条边的两个顶点为同一顶点，则此边称作环。 简单图(simple graph)：没有环、且没有多重弧的图称作简单图。 定向图：对无向图G的每条无向边指定一个方向得到的有向图。 底图：把一个有向图的每一条有向边的方向都去掉得到的无向图。 逆图：把一个有向图的每条边都反向由此得到的有向图。
竞赛图(tournament)：有向图的底图是无向完全图，则此有向图是竞赛图。
邻域(neighborhood)：在图中与u相邻的点的集合{v|v?V,(u,v)?E}，称为u的邻域，记为N(u)。
度：
度(degree)：一个顶点的度是指与该边相关联的边的条数，顶点v的度记作deg(v)。握手
3/33
[ADN.cn][library]summary 图论总结 2013-12-21
定理：无向图：?deg(v)?2|E|；有向图：?deg?(v)??deg?(v)。
v?Vv?Vv?V入度(indegree)：在有向图中，一个顶点v的入度是指与该边相关联的入边(即边的尾是v)的条数，记作deg?(v)。
出度(outdegree)：在有向图中，一个顶点的出度是指与该边相关联的出边(即边的头是v)的条数，记作deg?(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是一棵树，且V(T)?V(G)，则称T是G的一个生成树。即G的生成子图，且子图为树。
点导出子图(induced subgraph)：设V??V(G)，以V?为顶点集，以两端点均在V?中的边的全体为边集所组成的子图，称为G的由顶点集V?导出的子图，简称为G的点导出子图，记为
G[V?]。
边导出子图(edge-induced subgraph)：设E??E(G)，以E?为顶点集，以两端点均在E?中的边的全体为边集所组成的子图，称为G的由边集E?导出的子图，简称为G的边导出子图，记为G[E?]。
图的补图(complement)：设G是一个图，以V(G)为顶点集，以{(u,v)|(u,v)?E(G)}为边集的图称为G的补图，记为G。
点集的补集：记 V'?V?V'为点集V'的补集。
特殊的图：
零图(null graph)：E??，即只有孤立点的图。n阶零图记为Nn。 平凡图(trivial graph)：一阶零图。 空图(empty graph)：V?E??的图。
4/33
