[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
[ADN.cn][library]summary 图论总结 2013-12-21
有向无环图(directed acyclic graph(DAG))：有向的无环的图。
完全图(complete graph)：完全图是指每一对不同顶点间都有边相连的的无向图，n阶完全图常记作Kn。
二分图（bipartite graph）：若图G的顶点集可划分为两个非空子集X和Y，即V?X?Y且X?Y??，且每一条边都有一个顶点在X中，而另一个顶点在Y中，那么这样的图称作二分图。
完全二分图(complete 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)：边不重复的途径。 路(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?max{dG(u,v)|?u,v?V(G)}。
简单图G中最短圈的长度称为图G的围长(girth)，最长圈的长度称为图G的周长(perimeter)。
1.1.4. 连通性 Connectivity
连通(connected)：在图G中，两个顶点间，至少存在一条路径，称两个顶点连通的
5/33