6. 有向图 [ 有向图 ] 设 V 是一个非空有限集， E 是 V 上的元素有序对的集合。二元组 G=(V,E) 称为（有向）图， V 中元素称为顶点， E 中元素 e=<u,v> 称为弧（有向边）。 u 称为边 <u,v> 的始点， v 称为终点。称 u,v 与边 e=<u,v> 关联， u,v 是邻接点。
7. 无向图 [ 无向图 ] 设 V 是一个非空有限集， E 是 V 上的元素无序对的集合，称 G=(V, E) 是一个无向图 图解中既有无向边，又有有向边的图，称为混合图。混合图可以化为有向图求解。 < = >
9. [ 零图 ] E = ? 或 |E|=0 时，称 G 为零图。 [ 平凡图 ] 只有一个结点的零图称为平凡图。 [ 完全图 ] 任何两个顶点之间都有弧相连的图称为完全图。顶点集为 V 的完全图 G V =(V,V ? V) 。 n 阶无向完全图记作 K n ，其边数 = n ( n ? 1)/2
10. 子图 [ 子图 ] 图 G ? =(V ? , E ? ) 是 图 G=(V, E) 的一个子图当且仅当 : （ 1 ） V ? ? V （ 2 ） E ? ? E 上述定义中，若对 u , v ? V ? ， < u,v > ? E 必有 < u,v > ? E ? ，则称 G ? 是 G 的一个极大子图。 G 是 G 的子图； 若 G ? 是 G 的子图，则 G ? 的任何子图也是 G 的子图； 平凡图是任何图的子图
11. 生成子图 [ 生成子图 ] G ? =(V ? , E ? ) 是 G=(V, E) 的一个子图且 V ? = V ，则称 G ? 是 G 的一个生成子图或支撑子图。 [ 导出子图 ] G=(V, E) ， S ? V 且 S ? ? ，则 G 中以 S 为顶点集的极大子图称为 G 中由 S 导出的子图。 [ 补图 ] 设图 G=(V, E) ，则 ~G = (V, V ? V ? E) 称为 G=(V, E) 的 补图。
12. 顶点度 图 G 中顶点 v 的度，记为 d(v), 是关联到 v 的边的条数（ v 上的自环在计算度时要计算两次）。最大的顶点度记为 Δ(G) ，最小顶点度 δ(G) 。 [ 定理 ] 如果 G 是一个图，则 Σd(v)=2e(G) [ 推论 1] 图中度为奇数的顶点必为偶数个。 [ 定义 ] 对无向图 G=(V, E) ，若其任一顶点的度都为 r ，则称 G 为一个 r ? 度正则图。即 Δ(G)=δ(G) 。 [ 例 ] n 阶完全图是 n ? 1 度正则图。 [ 推论 2] 3 ? 度正则图中有偶数个顶点。
13. 图的表示 [ 邻接矩阵 ] 对有向图 G=(V, R) ， n =|V| ，构造矩阵 A=( a ij ) n ? n ，其中 称 A 为图 G 的邻接矩阵。 [ 邻接矩阵的特点 ] 无向图邻接矩阵式对称的；节点度数是对应行 1 的个数。对于有向图，结点的入度是对应行的 1 的个数，出度是对应列上 1 的个数。
14. 带权图的权矩阵 [ 权矩阵 ] 对带权图 G=(V, R) ， n =|V| ，构造矩阵 A=( a ij ) n ? n ，其中 称为图 G 的权矩阵。
17. 同构 [ 同构 ] 图 G=(V,E) 和 G ? =(V ? ,E ? ) ，若存在一一对应映射 g : V ? V ? ，使得对 v 1 , v 2 ? V ， ? v 1 , v 2 ? ? E 当且仅当 ? g( v 1 ), g( v 2 ) ? ? E ? ，则称 G 和 G ? 同构。记为 : G ? G ?
18. 自补图 [ 自补图 ] 图 G=(V,E) ， ~G 是 G 的补图。若 G ? ~G ，则称图 G 是自补的（或自补图）。
20. 道路与回路 [ 有向道路 ] 有向图 G=(V, A) 中，一条有向道路指的是一个首尾相接的弧的有限非空序列。道路、回路的长度是指其中的边的数目。 P = a 1 a 2 …… a k ( k ? 1) 其中 v i ? V ( i =0.. k ), a j ? A ( j =1.. k ) 且 a j = < v j ? 1 , v j > ( j =1.. k ) [ 简单道路 ] 若对任意的 i ? j 有 a i ? a j ，称之为简单有向道路。 ( 没有重复边的路径 ) [ 回路 ] 若 v 0 = v n ，称之为封闭的。简单封闭有向道路（闭迹）称为有向回路。 [ 初级道路 ] 若对任意的 i ? j 有 v i ? v j ，称之为初级道路 / 基本道路。 [ 圈 ] 若对任意的 i ? j 有 v i ? v j 而例外地 v 0 = v n ，称之为初级回路 / 圈。 无向图具有完全类似的定义。
21. [ 定理 ] （ 1 ）基本道路是简单道路； （ 2 ）如果存在 u 到 v 的道路，则存在 u 到 v 的基本道路； (3) n 阶图的基本道路长度不超过 n-1; (4) n 阶图的圈的长度不超过 n. （ 5 ）无向图 G=(V, E) ， u, v ? V 且 u ? v 。若 u,v 之间存在两条不同的路，则 G 中存在一条回路。 （ 6 ） 无向图 G=(V, E) 中每个顶点的度均为偶数，且至少有一个顶点不是孤立点，则 G 中存在一条回路。
22. 连通性 [ 可达性 ] 对于有向图 G=(V, A) 中，若从 v i 到 v j 存在一条路，则称从 v i 到 v j 是可达的，或称 v i 可达 v j 。 对无向图 G=(V, E) ，结点间的可达性是对称的。 [ 连通性 ] 对于无向图 G=(V, E) ，任意两点之间可达时，称 G 为连通的（连通图）。 G 中的一个极大连通子图称为 G 的一个连通分支 ( 连通分量 ) 。 一个图总是由一些连通分支构成的。 G 的连通分支数，记为 W (G) 。
23. 有向图的连通性 [ 强连通性 ] 对于有向图 G=(V, A) ，如果任意两点之间相互可达，则称 G 为强连通的 . [ 弱 连通性 ] 对于有向图 G=(V, A), 若不考虑弧的方向后得到的无向图是连通的，则称有向图 G 是弱连通的。 注意：未加特别声明时，我们讨论的都是简单图。 有向图的连通性的判定及矩阵在图论中的应用留到图论进阶中讲解。
24. 图上的搜索 可以使用搜索的方法判断从一个顶点 u 到另一个顶点 v 是否有路径。 [ 深度优先 DFS] 从顶点 u 出发检查其后继 u 1 是否ｖ，如果不是，则从 u 1 开始进行深度优先搜索；如果没有后继 , 则回溯，直至找到ｖ或者没有可搜索的顶点。 [ 广度优先 BFS] 从 u 出发，首先检查其所有的直接后继是否等于ｖ；然后依次检查这些后继的直接后继，直到找到ｖ或者没有可遍历顶点。 由于大家都应该具有一定的经验了，所以具体搜索方法就不进行详细的描述了。
25. Euler 回路 [Euler 回路 ] 若连通图 G=(V, E) 中存在一条简单回路（无重复边）经过 G 的所有边，则称该回路为 G 中的一条 Euler 回路。存在 Euler 回路的图称为 Euler 图。 [ 定理 ] 设有连通图 G=(V, E) ，则下述命题等价： (1) G 是一个 Euler 图； (2) G 的每一个顶点的度是偶数；
27. 有向图的 Euler 回路 [ 有向图的 Euler 回路 ] 若有向连通图 G=(V, A) 中存在一条简单有向回路经过 G 的所有弧，则称该回路为 G 中的一条 Euler 回路，称该图为 Euler 有向图。 [ 定理 ] 设连通有向图 G=(V, A) ，则下述命题等价： (1) G 是一个 Euler 有向图； (2) G 的每一个顶点的入度等于出度；
28. Hamilton 道路 [Hamilton 路 ] 若连通图 G=(V, E) 中存在一条初级道路（无重复顶点）经过 G 中每个顶点一次，则称该道路为 G 中的一条 Hamilton 路。存在 Hamilton 回路（圈）的图称 为 Hamilton 图。 Hamilton 路经过图的所有顶点一次且仅仅一次。 引入记号： G =(V, E) ， S ? V 。从 G 中去除 S 中的顶点及其关联边得到的 G 的子图记为 G ? S 。
29. [ 定理 ] 若 G=(V, E) 是一个 Hamilton 图， S ? V 且 S ?? ，则 G 的子图 G ? S 的连通分支数 W (G ? S) ? |S|
30. [ 定理 ] 简单图 G=(V, E) ， n =|V| ，若对任一对不相邻顶点 u, v ? V, u ? v, 有 d ( u) + d ( v ) ? n ? 1 ，则 G 中存在一条 Hamilton 路。 [ 推论 ] 上述有 deg ( u) + deg ( v ) ? n 时， G 为 Hamilton 图。
31. Hamilton 图 定理及其推论 给出了 Hamilton 图成立的充分条件，可用于对 Hamilton 图的肯定性判定。 Hamilton 图成立的充要条件尚未得到解决，是图论求解的课题之一。 Hamilton 图成立的充要条件是 NP 完全问题
32. 最短路径 [ 网络 ] 有向图 G=(V, A) 中，给每条边 a =< v i , v j > 赋予一个非负实数权 w ij ，得到一个有向网络。 [ 距离矩阵 ] 对上述网络，定义 D=( d ij ) n ? n ， n =|V| w ij 当 < v i , v j > ? A d ij = ? 其它 [ 带权路径长度 ] 对上述网络，路径 v 1 , v 2 , … , v k 的带权路径长度定义为
33. [ 两点间的最短距离 ] 对上述网络，结点 v i 到 v j 可达时， v i 到 v j 的所有路径中具有最小带权路径长度者称为 v i 到 v j 的最短路径，其带权路径长度称为 v i 到 v j 的最短距离。 [ 引理 ] 在有向网络中，若路径 v 1 , v 2 , … , v k-1 , v k 是 v 1 到 v k 的最短路，则路径 v 1 , v 2 , … , v k-1 是 v 1 到 v k-1 的最短路。
34. Dijkstra 算法 [ Dijkstra 算法 基本思想 ] : 如果 v 0 至 u 的最短路经经过 v 1 , 那么 v 0 到 v 1 的路径也是 v 0 至 v 1 的最短路经。 按路径长度的递增次序，逐步产生最短路径 . 设源点为 v 0 首先求出 v 0 为源点长度最短的一条最短路径， 即具有最小权的边 <v 0 ,v>; 求出源点到各个顶点下一个最短路径：设其终点是 u ，则 v 0 到 u 的最短路径或者是边 <v 0 ,u> ，或者由一条已求得的最短路径（ v 0 … v) 和边 <v,u> 构成； 重复 2 直到从顶点 v 0 到其它各顶点的最短路径全部求出为止 。 Dijkstra 算法的本质是贪心。
35. //dijkstra // the nodes numbered from 1 to n , s is start point // map[i] [j]==-1 means no direct path from i to j // dis==-1 means no path to get i from s void dijkstra () { int i,k, p,min ; static bool cov[ MAXN+1 ]; memset( dis, 255, sizeof(dis) ); memset( cov, ???? 0 , sizeof(cov) ); dis[s]=0; ???? path[s]=0; for( k=1; k<n; k++ ) { ??? for( min=maxint, i=1; ???? i<=n; ???? i++ ) ???? if( !cov[i] && dis[i]>=0 && dis[i]<min ) p=i,min = dis[ i ]; ???? if( min >= maxint ) break; ?? ??? for( cov[p]=1, i=1; ???? i<=n; ???? i++ ) ???? if( !cov [i]&& map[p][i]>=0 ) ?????? if( min+map[p][i] < dis[i] ) dis[i]=min+map[p][i], path[i]=p ; }// for k }// work
48. [AOV 网络 ] 有向连通网络 G=(V, A) ： ① 每一结点表示一个作业，有向边 <v i ,v j > 表示作业 v j 必须在 v i 完成之后开始； ② 边 <v i ,v j > 所带的非负实数权为完成作业 v i 所需时间； ③ 作业开始条件：该作业的所有前驱作业全部完成； ④ 无回路假设 (DAG: Directed Acyclic Graph 有向无环图 ) ； ⑤ 网络中有且只有一点入度为 0 ，称为源点，表示工程开始；有且只有一点出度为 0 ，称为汇点，表示工程结束。 关键路径
49. 关键路径 [ 关键路径 ] AOV 网络 G=(V,A) 中从源点 v 1 到汇点 v n 的最长路径。 关键路径不一定是唯一的。 关键路径的长度为完成任务所需的必要时间 T 。 [ 关键作业 ] 处于关键路径上的作业。 记 ? (v i , v j ) 为 v i 到 v j 的最长距离。 特别地， ? (v i ) = ? (v 1 , v i ). 则有
50. 根据以上关系，可以按照拓扑排序顺序求 ? (v i ) 。 [ 定理 ] 将 AOE 网 G=(V,A) 的结点按照拓扑序列排序为 v 1 , v 2 , …, v n , 则 ? ( v 1 )=0, ? ( v j )= max{ ? ( v i )+w ij | 1 ? i <j} 。 w ij 为 < v i , v j > ? A 时的边的非负实权，规定 < v i , v j > ? A 时 w ij = ? 。 则 u j 为 v 1 到 v j 的最长路径长度。 关键路径
51. 关键路径 [ 作业最早开始时间 ] 从源点到该作业 v k 的最长路径长度 ? ( v k ) [ 作业最晚开始时间 ] 设作业 v k 最晚可开始于 ? ( v k ) 时刻而不会影响任务完成的预期时间 T= ? ( v n ) , 则有 [ 缓冲时间 ] 不影响任务完成的预期时间 T 的前提下， v k 的作业的缓冲时间为 ? ( v k ) ? ? ( v k ) 。
52. 树的基本概念 [ 树 ] 连通图 G=(V,E) ，若 G 中不含任何回路，则称 G 为树。 |V|=1 时称之为平凡树。 [ 有向树 ] 一个弱连通有向图，若去掉方向后得到一棵树，则称此有向图为一棵有向树，记为 T 。 [ 割边 ] 图 G=(V,E) 中， e ? E 。设 G ? =(V,E ? { e }) ，若 G ? 的连通分支数目比 G 多 1 ，则称 e 为 G 的一条割边。 [ 定理 ] 上述 e 、 G 中， e 是 G 的一条割边当且仅当 e 不属于 G 中任何回路。
53. 树的基本概念 [ 定理 ] T=(V, E) 是结点数 n =|V| ? 1 的树，则下述命题等价： T 是无回路的连通图； T 是连通的，且有 n ? 1 条边； T 有 n ? 1 条边，且 T 中无回路； T 是连通的，且 T 中的每一条边都是割边； T 的任意两点间有且只有唯一的通路； T 中无回路，但若在 T 的任一对不相邻的顶点之间增加一条边，则构成 T 中的唯一回路。 上述定理内容也可作为树的等价定义。 [ 推论 1] 任一非平凡树至少有两个结点的度为 1 。 [ 推论 2] G 是一棵树当且仅当 G 是最小连通的（从 G 中去除任意一边即破坏了 G 的连通性）。
54. [ 生成树 ] G= （ V ， E ），若 G 的一个生成子图是一棵树，则称之为 G 的一棵生成树（记为 T ），或者支撑树。 G 中在 T 中的边称为（对于 T 的）树枝， G 中不在 T 中的边称为（对于 T 的）弦。 G 中的所有结点和弦构成的子图称为（对于 T 的）余树。 余树不一定是树。 [ 定理 ] 任何连通图至少有一棵生成树。 [ 推论 1] 设 G= （ V ， E ）连通，则 |E| ? |V| ? 1 。
55. [ 有向树 ] 一个弱连通有向图，若去掉方向后得到一棵树，则称此有向图为一棵有向树，记为 T 。 [ 有根树 ] 一棵有向树 T ，若其中有且仅有一个结点 v 0 的入度为 0 ，其余结点的入度为 1 ，则称 T 是一棵以 v 0 为根的有根树或外向树。其中出度为 0 的结点称为有根树的叶子。 [ 定义 ] 对有向树 T= ( V, A ) ，若 u ,v ? V 且 < u,v > ? A ，则称 u 为 v 的父亲， v 为 u 的儿子。若从 u 到 v 存在有向道路，则称 u 是 v 的祖先， v 是 u 的后代（子孙）。
56. 最小生成树 [ 最小生成树 ] 无向连通网络 G 的所有生成树中，树枝的权值总和最小的称为 G 的最小生成树，或最短树。 构造最小生成树的方法：每次选择一条最小权边，直至构成一个生成树。 [Kruskal 算法 ] 设 G 为无向连通网络。 1. 排序：将 G 的所有边按权值从小到大构成排列 L ； T ? ? 。 2. 当 |T|<n-1 时重复下列操作 (1) 选 L 中的最小权边 e ； (2) 若 T ? { e } 中不存在回路，将 e 加入 T: T ? T ? { e } 。 (3) 从 L 中删除 e : L ? L-{e} 3. STOP
58. typedef struct _node { int x; int y; int distance; }Node; void kruskal(int i){ qsort(graph, (size_t)N*N, sizeof(Node), compare); int shortest = 0; for (int i = 0; i < N*N; ++i){ int t, k; t = findset(graph[i].x); k = findset(graph[i].y); if (t != k){ shortest = shortest + graph[i].distance; unio(t, k); } } }
59. 最小生成树 求生成树的另一种方法：从一个结点的子图开始构造生成树：选择连接当前子图和子图外结点的最小权边，将相应结点和边加入子图，直至将所有结点加入子图。 [ 定理 ] 设 G=(V,E) 是一个带权连通图， V’ 是 V 的真子集， e 是连接 V’ 和 V-V’ 的最小权边，则 e 必定包含在 G 的一个最小生成树中。 [Prim 算法 ] 设 G=(V , E) 为无向连通网络。 1. U ? { u 0 } ， TE ? ? 。 2. 比较所有 u ? U ， v ? V ? U ， ( u , v ) ? E ，找到代价最小的 ( u , v ) ： U ? U ? {v} ， TE ? TE ? {( u , v )} 3. 若 U=V ，结束；否则转 2 。
61. 独立集、支配集和覆盖集 [ 独立集 ] 图 G=(V, E) ， B ? V ，若 B 中任意两个顶点都不相邻，则称 B 为 G 的一个点独立集（独立集）。 [ 极大独立集 ] B 为 G 的一个极大独立集 ? B 为 G 的一个独立集 ? ( ? u )( u ? V - B ? B ? { u } 不是 G 的独立集 )
62. [ 独立数 ] 设 G 的所有独立集为 B 1 、 B 2 、… 、 B k ，记 称为 G 的独立数。 [ 最大独立集 ] G 的一个独立集 B i 称为 G 的一个最大独立集若 |B i | = ? 0 。 求最大独立集问题是 NP 完全的。
63. 独立集、支配集和覆盖集 [ 支配集 ] 图 G=(V,E) ， K ? V ，若 G 的任何顶点或属于 K ，或至少与 K 中一点邻接，则称 K 为 G 的一个支配集。
64. 独立集、支配集和覆盖集 [ 极小支配集 ] K 为 G 的一个极小支配集 ? K 为 G 的一个支配集 ? ( ? K 1 )(K 1 ? K ? K 1 不是 G 的支配集 ). [ 支配数 ] 设 G 的所有支配集为 A 1 、 A 2 、… 、 A k ，记 称为 G 的支配数。 [ 最小支配集 ] G 的一个支配集 A i 称为 G 的一个最小支配集若 |A i | = ? 0 。
65. 独立集、支配集和覆盖集 [ 定理 ] 设 G=(V,E) 无孤立点，则： ① G 的一个极大独立集必也是 G 的一个极小支配集； ② ? 0 ? ? 0 ； ③ 若 S 为 G 的一个独立集，则 V - S 为 G 的一个支配集；
66. 独立集、支配集和覆盖集 [ 点覆盖 ] 图 G=(V,E) ， K ? V ，若 G 的任何一条边都与 K 中顶点关联，则称 K 为 G 的一个点覆盖（集）。 K 为 G 的一个点覆盖 ? K ? V ? ( ? e )( e =( u,v ) ? E ? u ? K ? v ? K)
67. [ 极小点覆盖 ] K 是 G 的一个极小点覆盖 ? K 为 G 的一个点覆盖 ? ( ? K 1 )(K 1 ? K ? K 1 不是 G 的点覆盖 ) [ 点覆盖数 ] 设 G 的所有点覆盖为 C 1 、 C 2 、… 、 C k ，记 称为 G 的点覆盖数。 [ 最小点覆盖 ] G 的一个点覆盖 C i 称为 G 的一个最小点覆盖若 |C i | = ? 0 。
68. [ 定理 ] 设图 G=(V,E) 无孤立点， C ? V ，则： C 为 G 的一个点覆盖 ? V - C 为 G 的一个独立集。 [ 推论 1] G 如上所述， C ? V ，则： C 为 G 的一个极小点覆盖 ? V - C 是 G 的一个极大独立集。 [ 推论 2] G 如上所述， n=|V| ，则 ? 0 + ? 0 = n 。 极小点覆盖数 + 极大独立集数 = 顶点数
72. 匹配的基本概念 [ 匹配 ] G 的一个任意两边不相邻的边集合 M 称为 G 的一个边独立集或匹配。 [ 极大匹配 ] M 是 G 的一个极大匹配 ? M 为 G 的一个匹配 ? ( ? e )( e ? E ? M ? M ? { e } 不是 G 的匹配 ) [ 匹配数 ] 设 G 的所有匹配为 M 1 、 M 2 、… 、 M k ，记 为 G 的匹配数。 [ 最大匹配 ] M i 称为 G 的一个最大匹配若 |M i | = ? 1 。
73. [ 定义 ] 设 M 是 G 的一个匹配 ，若有 e =( vi,vj ) ? M ，则称 vi 和 vj 在 M 中饱和或 M ? 饱和。若 G 中的每一个顶点都为 M ? 饱和，则称 M 为 G 的一个完美匹配。
74. [ 边覆盖 ] 一个图 G=(V, E) ， E? ? E ，若 G 的任一个顶点都与 E? 中的边关联，则称 E? 覆盖 G ，或称 E? 为 G 的一个边覆盖（集）。 E? 为 G 的一个边覆盖 ? E? ? E ? ( ? u )( u ? V ? ( ? e )( e =( v,w ) ? E? ? ( v = u ? w = u ))) [ 极小边覆盖 ] E? 是 G 的一个极小边覆盖 ? E? 为 G 的一个边覆盖 ? ( ? E 1 )(E 1 ? E? ? E 1 不是 G 的边覆盖 ) [ 边覆盖数 ] 设 G 的所有边覆盖为 E 1 、 E 2 、… 、 E k ，记 为 G 的边覆盖数。 [ 最小边覆盖 ] E i 称为 G 的一个最小边覆盖若 |E i | = ? 1 。 匹配的基本概念
76. 最大匹配的基本定理 [M ? 交互道 ] 设 G 和 M 如上所述， G 的一条 M ? 交互道指 G 中一条路，其中的边在 M 和 E ? M 中交错出现。 [M ? 可增广道 ] 设 G 和 M 如上所述，若 G 的一条 M ? 交互道的始点和终点都是 M ? 不饱和的，则称该 M ? 交互道为一条 M ? 可增广道。 [ 定理 ] 设 G=(V,E) ， M 为 G 中匹配，则 M 为 G 的最大匹配当且仅当 G 中不存在 M ? 可增广道。
77. 最大匹配算法 寻求二分图 G=(X,Y) 最大匹配的匈牙利算法 (Edmonds) 基本思想：从一个初始匹配 M 开始，系统地寻找 M 的可增广道路 P ，然后扩展为更大的匹配 M’=P ? M(P 所有 M 可增广道路 P) ，直至不存在可增广道路。 基本步骤： (1) 置 M 为空 (2) 找出一条增广路径 P ，通过取反操作获得更大的匹配 M’ 代替 M (3) 重复 (2) 操作直到找不出增广路径为止
78. int g[SIZE][SIZE]; // 注意是二分图两个定点划分间边的情况而非图的邻接矩阵 int n,m; // 二分图两个集合的顶点数 int linker[SIZE]; // 标记 与 Y 部集关联的 X 部集的顶点编号 bool used[SIZE]; // 在每次增广时标记部集 Y 中的点是否已经在匹配中 bool dfs(int a){ // 寻找交替路径 for (int i = 0;i < m;i++) if (g[a][i] && !used[i]){ used[i] = true; if (linker[i] == -1 || dfs(linker[i])){ linker[i] = a; return true; } } return false; } int hungary(){// 返回最大匹配数 int result = 0; memset(linker,-1,sizeof(linker)); for (int i = 0;i < n;i++){ memset(used,0,sizeof(used)); if (dfs(i)) result++; } return result; }
![有向图 [ 有向图 ] 设 V 是一个非空有限集， E 是 V 上的元素有序对的集合。二元组 G=(V,E) 称为（有向）图， V 中元素称为顶点， E 中元素 e=<u,v> 称为弧（有向边）。 u 称为边 <u,v> 的始点， v 称为终点。称 u,v 与边 e=<u,v> 关联， u,v 是邻接点。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-6-320.jpg)
![无向图 [ 无向图 ] 设 V 是一个非空有限集， E 是 V 上的元素无序对的集合，称 G=(V, E) 是一个无向图 图解中既有无向边，又有有向边的图，称为混合图。混合图可以化为有向图求解。 < = >](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-7-320.jpg)
![[ 多重边 ] 在表达实际问题的图解中， E 可以是多重集合，即两个结点可以有多个边相连，称为多重边（平行边）。 [ 自环 ] E 中的自反性图解为环形，称为自环。 [ 简单图 ] 不出现自环或多重边图解形状的图称为简单图。 一般未加特别声明时，讨论的是简单图 。 [ 图的阶 ] |V| 称为图的阶。即点的个数。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-8-320.jpg)
![[ 零图 ] E = ? 或 |E|=0 时，称 G 为零图。 [ 平凡图 ] 只有一个结点的零图称为平凡图。 [ 完全图 ] 任何两个顶点之间都有弧相连的图称为完全图。顶点集为 V 的完全图 G V =(V,V ? V) 。 n 阶无向完全图记作 K n ，其边数 = n ( n ? 1)/2](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-9-320.jpg)
![子图 [ 子图 ] 图 G ? =(V ? , E ? ) 是 图 G=(V, E) 的一个子图当且仅当 : （ 1 ） V ? ? V （ 2 ） E ? ? E 上述定义中，若对 u , v ? V ? ， < u,v > ? E 必有 < u,v > ? E ? ，则称 G ? 是 G 的一个极大子图。 G 是 G 的子图； 若 G ? 是 G 的子图，则 G ? 的任何子图也是 G 的子图； 平凡图是任何图的子图](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-10-320.jpg)
![生成子图 [ 生成子图 ] G ? =(V ? , E ? ) 是 G=(V, E) 的一个子图且 V ? = V ，则称 G ? 是 G 的一个生成子图或支撑子图。 [ 导出子图 ] G=(V, E) ， S ? V 且 S ? ? ，则 G 中以 S 为顶点集的极大子图称为 G 中由 S 导出的子图。 [ 补图 ] 设图 G=(V, E) ，则 ~G = (V, V ? V ? E) 称为 G=(V, E) 的 补图。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-11-320.jpg)
![顶点度 图 G 中顶点 v 的度，记为 d(v), 是关联到 v 的边的条数（ v 上的自环在计算度时要计算两次）。最大的顶点度记为 Δ(G) ，最小顶点度 δ(G) 。 [ 定理 ] 如果 G 是一个图，则 Σd(v)=2e(G) [ 推论 1] 图中度为奇数的顶点必为偶数个。 [ 定义 ] 对无向图 G=(V, E) ，若其任一顶点的度都为 r ，则称 G 为一个 r ? 度正则图。即 Δ(G)=δ(G) 。 [ 例 ] n 阶完全图是 n ? 1 度正则图。 [ 推论 2] 3 ? 度正则图中有偶数个顶点。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-12-320.jpg)
![图的表示 [ 邻接矩阵 ] 对有向图 G=(V, R) ， n =|V| ，构造矩阵 A=( a ij ) n ? n ，其中 称 A 为图 G 的邻接矩阵。 [ 邻接矩阵的特点 ] 无向图邻接矩阵式对称的；节点度数是对应行 1 的个数。对于有向图，结点的入度是对应行的 1 的个数，出度是对应列上 1 的个数。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-13-320.jpg)
![带权图的权矩阵 [ 权矩阵 ] 对带权图 G=(V, R) ， n =|V| ，构造矩阵 A=( a ij ) n ? n ，其中 称为图 G 的权矩阵。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-14-320.jpg)
![同构 [ 同构 ] 图 G=(V,E) 和 G ? =(V ? ,E ? ) ，若存在一一对应映射 g : V ? V ? ，使得对 v 1 , v 2 ? V ， ? v 1 , v 2 ? ? E 当且仅当 ? g( v 1 ), g( v 2 ) ? ? E ? ，则称 G 和 G ? 同构。记为 : G ? G ?](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-17-320.jpg)
![自补图 [ 自补图 ] 图 G=(V,E) ， ~G 是 G 的补图。若 G ? ~G ，则称图 G 是自补的（或自补图）。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-18-320.jpg)
![道路与回路 [ 有向道路 ] 有向图 G=(V, A) 中，一条有向道路指的是一个首尾相接的弧的有限非空序列。道路、回路的长度是指其中的边的数目。 P = a 1 a 2 …… a k ( k ? 1) 其中 v i ? V ( i =0.. k ), a j ? A ( j =1.. k ) 且 a j = < v j ? 1 , v j > ( j =1.. k ) [ 简单道路 ] 若对任意的 i ? j 有 a i ? a j ，称之为简单有向道路。 ( 没有重复边的路径 ) [ 回路 ] 若 v 0 = v n ，称之为封闭的。简单封闭有向道路（闭迹）称为有向回路。 [ 初级道路 ] 若对任意的 i ? j 有 v i ? v j ，称之为初级道路 / 基本道路。 [ 圈 ] 若对任意的 i ? j 有 v i ? v j 而例外地 v 0 = v n ，称之为初级回路 / 圈。 无向图具有完全类似的定义。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-20-320.jpg)
![[ 定理 ] （ 1 ）基本道路是简单道路； （ 2 ）如果存在 u 到 v 的道路，则存在 u 到 v 的基本道路； (3) n 阶图的基本道路长度不超过 n-1; (4) n 阶图的圈的长度不超过 n. （ 5 ）无向图 G=(V, E) ， u, v ? V 且 u ? v 。若 u,v 之间存在两条不同的路，则 G 中存在一条回路。 （ 6 ） 无向图 G=(V, E) 中每个顶点的度均为偶数，且至少有一个顶点不是孤立点，则 G 中存在一条回路。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-21-320.jpg)
![连通性 [ 可达性 ] 对于有向图 G=(V, A) 中，若从 v i 到 v j 存在一条路，则称从 v i 到 v j 是可达的，或称 v i 可达 v j 。 对无向图 G=(V, E) ，结点间的可达性是对称的。 [ 连通性 ] 对于无向图 G=(V, E) ，任意两点之间可达时，称 G 为连通的（连通图）。 G 中的一个极大连通子图称为 G 的一个连通分支 ( 连通分量 ) 。 一个图总是由一些连通分支构成的。 G 的连通分支数，记为 W (G) 。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-22-320.jpg)
![有向图的连通性 [ 强连通性 ] 对于有向图 G=(V, A) ，如果任意两点之间相互可达，则称 G 为强连通的 . [ 弱 连通性 ] 对于有向图 G=(V, A), 若不考虑弧的方向后得到的无向图是连通的，则称有向图 G 是弱连通的。 注意：未加特别声明时，我们讨论的都是简单图。 有向图的连通性的判定及矩阵在图论中的应用留到图论进阶中讲解。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-23-320.jpg)
![图上的搜索 可以使用搜索的方法判断从一个顶点 u 到另一个顶点 v 是否有路径。 [ 深度优先 DFS] 从顶点 u 出发检查其后继 u 1 是否ｖ，如果不是，则从 u 1 开始进行深度优先搜索；如果没有后继 , 则回溯，直至找到ｖ或者没有可搜索的顶点。 [ 广度优先 BFS] 从 u 出发，首先检查其所有的直接后继是否等于ｖ；然后依次检查这些后继的直接后继，直到找到ｖ或者没有可遍历顶点。 由于大家都应该具有一定的经验了，所以具体搜索方法就不进行详细的描述了。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-24-320.jpg)
![Euler 回路 [Euler 回路 ] 若连通图 G=(V, E) 中存在一条简单回路（无重复边）经过 G 的所有边，则称该回路为 G 中的一条 Euler 回路。存在 Euler 回路的图称为 Euler 图。 [ 定理 ] 设有连通图 G=(V, E) ，则下述命题等价： (1) G 是一个 Euler 图； (2) G 的每一个顶点的度是偶数；](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-25-320.jpg)
![注意定理中对图的连通性的假定； Euler 回路经过图的所有边一次且仅仅一次。 定理对非简单图也成立； [ 定理 ] 设连通图 G=(V, E) 中恰有 2 个顶点度为奇数，则 G 存在 Euler 道路 。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-26-320.jpg)
![有向图的 Euler 回路 [ 有向图的 Euler 回路 ] 若有向连通图 G=(V, A) 中存在一条简单有向回路经过 G 的所有弧，则称该回路为 G 中的一条 Euler 回路，称该图为 Euler 有向图。 [ 定理 ] 设连通有向图 G=(V, A) ，则下述命题等价： (1) G 是一个 Euler 有向图； (2) G 的每一个顶点的入度等于出度；](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-27-320.jpg)
![Hamilton 道路 [Hamilton 路 ] 若连通图 G=(V, E) 中存在一条初级道路（无重复顶点）经过 G 中每个顶点一次，则称该道路为 G 中的一条 Hamilton 路。存在 Hamilton 回路（圈）的图称 为 Hamilton 图。 Hamilton 路经过图的所有顶点一次且仅仅一次。 引入记号： G =(V, E) ， S ? V 。从 G 中去除 S 中的顶点及其关联边得到的 G 的子图记为 G ? S 。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-28-320.jpg)
![[ 定理 ] 若 G=(V, E) 是一个 Hamilton 图， S ? V 且 S ?? ，则 G 的子图 G ? S 的连通分支数 W (G ? S) ? |S|](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-29-320.jpg)
![[ 定理 ] 简单图 G=(V, E) ， n =|V| ，若对任一对不相邻顶点 u, v ? V, u ? v, 有 d ( u) + d ( v ) ? n ? 1 ，则 G 中存在一条 Hamilton 路。 [ 推论 ] 上述有 deg ( u) + deg ( v ) ? n 时， G 为 Hamilton 图。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-30-320.jpg)
![最短路径 [ 网络 ] 有向图 G=(V, A) 中，给每条边 a =< v i , v j > 赋予一个非负实数权 w ij ，得到一个有向网络。 [ 距离矩阵 ] 对上述网络，定义 D=( d ij ) n ? n ， n =|V| w ij 当 < v i , v j > ? A d ij = ? 其它 [ 带权路径长度 ] 对上述网络，路径 v 1 , v 2 , … , v k 的带权路径长度定义为](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-32-320.jpg)
![[ 两点间的最短距离 ] 对上述网络，结点 v i 到 v j 可达时， v i 到 v j 的所有路径中具有最小带权路径长度者称为 v i 到 v j 的最短路径，其带权路径长度称为 v i 到 v j 的最短距离。 [ 引理 ] 在有向网络中，若路径 v 1 , v 2 , … , v k-1 , v k 是 v 1 到 v k 的最短路，则路径 v 1 , v 2 , … , v k-1 是 v 1 到 v k-1 的最短路。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-33-320.jpg)
![Dijkstra 算法 [ Dijkstra 算法 基本思想 ] : 如果 v 0 至 u 的最短路经经过 v 1 , 那么 v 0 到 v 1 的路径也是 v 0 至 v 1 的最短路经。 按路径长度的递增次序，逐步产生最短路径 . 设源点为 v 0 首先求出 v 0 为源点长度最短的一条最短路径， 即具有最小权的边 <v 0 ,v>; 求出源点到各个顶点下一个最短路径：设其终点是 u ，则 v 0 到 u 的最短路径或者是边 <v 0 ,u> ，或者由一条已求得的最短路径（ v 0 … v) 和边 <v,u> 构成； 重复 2 直到从顶点 v 0 到其它各顶点的最短路径全部求出为止 。 Dijkstra 算法的本质是贪心。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-34-320.jpg)
![//dijkstra // the nodes numbered from 1 to n , s is start point // map[i] [j]==-1 means no direct path from i to j // dis==-1 means no path to get i from s void dijkstra () { int i,k, p,min ; static bool cov[ MAXN+1 ]; memset( dis, 255, sizeof(dis) ); memset( cov, ???? 0 , sizeof(cov) ); dis[s]=0; ???? path[s]=0; for( k=1; k<n; k++ ) { ??? for( min=maxint, i=1; ???? i<=n; ???? i++ ) ???? if( !cov[i] && dis[i]>=0 && dis[i]<min ) p=i,min = dis[ i ]; ???? if( min >= maxint ) break; ?? ??? for( cov[p]=1, i=1; ???? i<=n; ???? i++ ) ???? if( !cov [i]&& map[p][i]>=0 ) ?????? if( min+map[p][i] < dis[i] ) dis[i]=min+map[p][i], path[i]=p ; }// for k }// work](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-35-320.jpg)
![Floyed 算法 弗洛耶德算法（ Floyed 算法）： 基本思想：求解所有点间的路径需要进行 n 次试探。对于顶点 i 到顶点 j 的路径长度，首先考虑让路径经过顶点 1 ，比较路径（ i ， j ）和（ i ， 1 ， j ）的长度取其短者为当前求得的最短路径长度。 floyed 算法的本质是动态规划。递归方程： dp[i][j][k]=min{dp[i][j][k - 1],dp[i][k][k]+dp[k][j][k]} 特殊的，有：当 k=0 时， dp[i][j][0]=w(i,j) 。 其中 dp[i][j][k] 表示从 i 到 j 经过 k 的最短路径](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-37-320.jpg)
![//floyed void floyed() { for(int i = 0; i < sz; i++) { for(int j = 0; j < sz; j++) for(int k = 0; k < sz; k++){ int t_dis = distances[j][i] + distances[i][k]; if(distances[j][k] > t_dis) distances[j][k] = t_dis; } }](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-38-320.jpg)
![Bellman-Ford 算法 基本思想： 它是最优性原理的直接应用，算法基于以下事实： l 如果最短路存在，则每个顶点最多经过一次，因此不超过 n-1 条边； 2 长度为 k 的路由长度为 k-1 的路加一条边得到； 3 由最优性原理，只需依次考虑长度为 1 ， 2 ，…， k-1 的最短路。 算法描述 对每条边进行 |V|-1 次 Relax( 松弛 ) 操作 ; 如果存在 (u,v)∈E 使得 dis[u]+w<dis[v], 则存在负权回路 ; 否则 dis[v] 即为 s 到 v 的最短距离 ,pre[v] 为前驱。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-40-320.jpg)
![//Bellman-Ford map[i] [j]==MaxInt means no direct path from i to j bool bellman_ford(){ bool not finish=false; memset( checked , 0, sizeof( checked ) ); checked[ s ]=true; for(k=0;k<n &&!notfinish ;k++) { not finish=true; for(i=0;i<n;i++){ if(checked[i]){ checked[i]=false; for(j=0;j<n;j++){ if(dis[i]+map [i] [j] < dis[j){ dis[j]=dis[i]+map [i] [j] ; checked[j]=true, not finish=false; } } } } } return true; }](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-41-320.jpg)
![关键路径 [ 作业网络 ] 一项工程通常包括多个工序，这些工序间存在次序的约束：一个工序的开始的前提是某些工序已经结束。每个工序有预计的完成时间。 编号 课程号 先修课 时间 1 CS101 3 2 CS102 1 3 CS201 CS101 CS102 2 4 CS302 CS201 1 5 CS305 CS302 1 6 CS405 CS302 1](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-43-320.jpg)
![拓扑排序 [ 拓扑排序 ] 将一个 n 阶有向图 G=(V,A) 的所有顶点排列成一个线性序 v 1 ,v 2 ,…,v n ，使得如果 <v i ,v j > ? A, 则 i<j. 称这样的序列为Ｇ的一个拓扑排序。 例如，左图的一个拓扑排序是： 1,2,3,4,6,5](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-46-320.jpg)
![拓扑排序 [ 定理 ] 若有向图 G=(V,A) 不存在有向回路，则Ｇ存在拓扑排序。 [ 引理 ] 若有向图 G=(V,A) 不存在有向回路，则Ｇ存在入度为零和出度为零的结点。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-47-320.jpg)
![[AOV 网络 ] 有向连通网络 G=(V, A) ： ① 每一结点表示一个作业，有向边 <v i ,v j > 表示作业 v j 必须在 v i 完成之后开始； ② 边 <v i ,v j > 所带的非负实数权为完成作业 v i 所需时间； ③ 作业开始条件：该作业的所有前驱作业全部完成； ④ 无回路假设 (DAG: Directed Acyclic Graph 有向无环图 ) ； ⑤ 网络中有且只有一点入度为 0 ，称为源点，表示工程开始；有且只有一点出度为 0 ，称为汇点，表示工程结束。 关键路径](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-48-320.jpg)
![关键路径 [ 关键路径 ] AOV 网络 G=(V,A) 中从源点 v 1 到汇点 v n 的最长路径。 关键路径不一定是唯一的。 关键路径的长度为完成任务所需的必要时间 T 。 [ 关键作业 ] 处于关键路径上的作业。 记 ? (v i , v j ) 为 v i 到 v j 的最长距离。 特别地， ? (v i ) = ? (v 1 , v i ). 则有](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-49-320.jpg)
![根据以上关系，可以按照拓扑排序顺序求 ? (v i ) 。 [ 定理 ] 将 AOE 网 G=(V,A) 的结点按照拓扑序列排序为 v 1 , v 2 , …, v n , 则 ? ( v 1 )=0, ? ( v j )= max{ ? ( v i )+w ij | 1 ? i <j} 。 w ij 为 < v i , v j > ? A 时的边的非负实权，规定 < v i , v j > ? A 时 w ij = ? 。 则 u j 为 v 1 到 v j 的最长路径长度。 关键路径](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-50-320.jpg)
![关键路径 [ 作业最早开始时间 ] 从源点到该作业 v k 的最长路径长度 ? ( v k ) [ 作业最晚开始时间 ] 设作业 v k 最晚可开始于 ? ( v k ) 时刻而不会影响任务完成的预期时间 T= ? ( v n ) , 则有 [ 缓冲时间 ] 不影响任务完成的预期时间 T 的前提下， v k 的作业的缓冲时间为 ? ( v k ) ? ? ( v k ) 。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-51-320.jpg)
![树的基本概念 [ 树 ] 连通图 G=(V,E) ，若 G 中不含任何回路，则称 G 为树。 |V|=1 时称之为平凡树。 [ 有向树 ] 一个弱连通有向图，若去掉方向后得到一棵树，则称此有向图为一棵有向树，记为 T 。 [ 割边 ] 图 G=(V,E) 中， e ? E 。设 G ? =(V,E ? { e }) ，若 G ? 的连通分支数目比 G 多 1 ，则称 e 为 G 的一条割边。 [ 定理 ] 上述 e 、 G 中， e 是 G 的一条割边当且仅当 e 不属于 G 中任何回路。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-52-320.jpg)
![树的基本概念 [ 定理 ] T=(V, E) 是结点数 n =|V| ? 1 的树，则下述命题等价： T 是无回路的连通图； T 是连通的，且有 n ? 1 条边； T 有 n ? 1 条边，且 T 中无回路； T 是连通的，且 T 中的每一条边都是割边； T 的任意两点间有且只有唯一的通路； T 中无回路，但若在 T 的任一对不相邻的顶点之间增加一条边，则构成 T 中的唯一回路。 上述定理内容也可作为树的等价定义。 [ 推论 1] 任一非平凡树至少有两个结点的度为 1 。 [ 推论 2] G 是一棵树当且仅当 G 是最小连通的（从 G 中去除任意一边即破坏了 G 的连通性）。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-53-320.jpg)
![[ 生成树 ] G= （ V ， E ），若 G 的一个生成子图是一棵树，则称之为 G 的一棵生成树（记为 T ），或者支撑树。 G 中在 T 中的边称为（对于 T 的）树枝， G 中不在 T 中的边称为（对于 T 的）弦。 G 中的所有结点和弦构成的子图称为（对于 T 的）余树。 余树不一定是树。 [ 定理 ] 任何连通图至少有一棵生成树。 [ 推论 1] 设 G= （ V ， E ）连通，则 |E| ? |V| ? 1 。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-54-320.jpg)
![[ 有向树 ] 一个弱连通有向图，若去掉方向后得到一棵树，则称此有向图为一棵有向树，记为 T 。 [ 有根树 ] 一棵有向树 T ，若其中有且仅有一个结点 v 0 的入度为 0 ，其余结点的入度为 1 ，则称 T 是一棵以 v 0 为根的有根树或外向树。其中出度为 0 的结点称为有根树的叶子。 [ 定义 ] 对有向树 T= ( V, A ) ，若 u ,v ? V 且 < u,v > ? A ，则称 u 为 v 的父亲， v 为 u 的儿子。若从 u 到 v 存在有向道路，则称 u 是 v 的祖先， v 是 u 的后代（子孙）。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-55-320.jpg)
![最小生成树 [ 最小生成树 ] 无向连通网络 G 的所有生成树中，树枝的权值总和最小的称为 G 的最小生成树，或最短树。 构造最小生成树的方法：每次选择一条最小权边，直至构成一个生成树。 [Kruskal 算法 ] 设 G 为无向连通网络。 1. 排序：将 G 的所有边按权值从小到大构成排列 L ； T ? ? 。 2. 当 |T|<n-1 时重复下列操作 (1) 选 L 中的最小权边 e ； (2) 若 T ? { e } 中不存在回路，将 e 加入 T: T ? T ? { e } 。 (3) 从 L 中删除 e : L ? L-{e} 3. STOP](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-56-320.jpg)
![// 并查集操作 int findset(int i) { if (root[i] != i) root[i] = findset(root[i]); return root[i]; } void makeset(int i) { root[i] = i; heavy[i] = 1; } void unio(int i, int j) { if (heavy[i] > heavy[j]) { root[j] = i; heavy[i] = heavy[i] + heavy[j]; } else if (heavy[i] < heavy[j]) { root[i] = j; heavy[j] = heavy[i] + heavy[j]; } else { root[j] = i; heavy[i] = heavy[i] + heavy[j]; } }](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-57-320.jpg)
![typedef struct _node { int x; int y; int distance; }Node; void kruskal(int i){ qsort(graph, (size_t)N*N, sizeof(Node), compare); int shortest = 0; for (int i = 0; i < N*N; ++i){ int t, k; t = findset(graph[i].x); k = findset(graph[i].y); if (t != k){ shortest = shortest + graph[i].distance; unio(t, k); } } }](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-58-320.jpg)
![最小生成树 求生成树的另一种方法：从一个结点的子图开始构造生成树：选择连接当前子图和子图外结点的最小权边，将相应结点和边加入子图，直至将所有结点加入子图。 [ 定理 ] 设 G=(V,E) 是一个带权连通图， V’ 是 V 的真子集， e 是连接 V’ 和 V-V’ 的最小权边，则 e 必定包含在 G 的一个最小生成树中。 [Prim 算法 ] 设 G=(V , E) 为无向连通网络。 1. U ? { u 0 } ， TE ? ? 。 2. 比较所有 u ? U ， v ? V ? U ， ( u , v ) ? E ，找到代价最小的 ( u , v ) ： U ? U ? {v} ， TE ? TE ? {( u , v )} 3. 若 U=V ，结束；否则转 2 。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-59-320.jpg)
![void prim(){ for(int i=1;i<now;i++){ low[i]=map[s][i]; pre[i]=s; notused[i]=s; } notused[s]=0; for(int i=2;i<now;i++) { int min=MAX_INT,sign_node=i; for(int j=1;j<now;j++){ if(low[j]<min&¬used[j]!=0){ min=low[j]; sign_node=j; } } notused[sign_node]=0; for(int j=1;j<now;j++){ if(low[j]>map[sign_node][j]&¬used[j]!=0){ low[j]=map[sign_node][j]; pre[j]=sign_node; } } } }](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-60-320.jpg)
![独立集、支配集和覆盖集 [ 独立集 ] 图 G=(V, E) ， B ? V ，若 B 中任意两个顶点都不相邻，则称 B 为 G 的一个点独立集（独立集）。 [ 极大独立集 ] B 为 G 的一个极大独立集 ? B 为 G 的一个独立集 ? ( ? u )( u ? V - B ? B ? { u } 不是 G 的独立集 )](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-61-320.jpg)
![[ 独立数 ] 设 G 的所有独立集为 B 1 、 B 2 、… 、 B k ，记 称为 G 的独立数。 [ 最大独立集 ] G 的一个独立集 B i 称为 G 的一个最大独立集若 |B i | = ? 0 。 求最大独立集问题是 NP 完全的。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-62-320.jpg)
![独立集、支配集和覆盖集 [ 支配集 ] 图 G=(V,E) ， K ? V ，若 G 的任何顶点或属于 K ，或至少与 K 中一点邻接，则称 K 为 G 的一个支配集。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-63-320.jpg)
![独立集、支配集和覆盖集 [ 极小支配集 ] K 为 G 的一个极小支配集 ? K 为 G 的一个支配集 ? ( ? K 1 )(K 1 ? K ? K 1 不是 G 的支配集 ). [ 支配数 ] 设 G 的所有支配集为 A 1 、 A 2 、… 、 A k ，记 称为 G 的支配数。 [ 最小支配集 ] G 的一个支配集 A i 称为 G 的一个最小支配集若 |A i | = ? 0 。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-64-320.jpg)
![独立集、支配集和覆盖集 [ 定理 ] 设 G=(V,E) 无孤立点，则： ① G 的一个极大独立集必也是 G 的一个极小支配集； ② ? 0 ? ? 0 ； ③ 若 S 为 G 的一个独立集，则 V - S 为 G 的一个支配集；](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-65-320.jpg)
![独立集、支配集和覆盖集 [ 点覆盖 ] 图 G=(V,E) ， K ? V ，若 G 的任何一条边都与 K 中顶点关联，则称 K 为 G 的一个点覆盖（集）。 K 为 G 的一个点覆盖 ? K ? V ? ( ? e )( e =( u,v ) ? E ? u ? K ? v ? K)](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-66-320.jpg)
![[ 极小点覆盖 ] K 是 G 的一个极小点覆盖 ? K 为 G 的一个点覆盖 ? ( ? K 1 )(K 1 ? K ? K 1 不是 G 的点覆盖 ) [ 点覆盖数 ] 设 G 的所有点覆盖为 C 1 、 C 2 、… 、 C k ，记 称为 G 的点覆盖数。 [ 最小点覆盖 ] G 的一个点覆盖 C i 称为 G 的一个最小点覆盖若 |C i | = ? 0 。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-67-320.jpg)
![[ 定理 ] 设图 G=(V,E) 无孤立点， C ? V ，则： C 为 G 的一个点覆盖 ? V - C 为 G 的一个独立集。 [ 推论 1] G 如上所述， C ? V ，则： C 为 G 的一个极小点覆盖 ? V - C 是 G 的一个极大独立集。 [ 推论 2] G 如上所述， n=|V| ，则 ? 0 + ? 0 = n 。 极小点覆盖数 + 极大独立集数 = 顶点数](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-68-320.jpg)
![二部图（二分图） 图 G 称为二部图，如果 V(G) 是两个互不相交的独立集（可以是空集）的并集。 [ 定理 ] ：一个图是二部当且仅当它不包含奇环。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-69-320.jpg)
![配偶问题 [ 配偶问题 ] 假定有一个男生有穷集合，其中每个男生认识一些女生，为了构建和谐社会在什么条件下每个男生都可以和他认识的女生结婚？ 类似的工作分配问题：现有 n 个人， m 份工作，每个人有其擅长的工作。在什么条件下每个人都可以得到一份他擅长的工作？如何分配？](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-70-320.jpg)
![匹配的基本概念 [ 匹配 ] G 的一个任意两边不相邻的边集合 M 称为 G 的一个边独立集或匹配。 [ 极大匹配 ] M 是 G 的一个极大匹配 ? M 为 G 的一个匹配 ? ( ? e )( e ? E ? M ? M ? { e } 不是 G 的匹配 ) [ 匹配数 ] 设 G 的所有匹配为 M 1 、 M 2 、… 、 M k ，记 为 G 的匹配数。 [ 最大匹配 ] M i 称为 G 的一个最大匹配若 |M i | = ? 1 。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-72-320.jpg)
![[ 定义 ] 设 M 是 G 的一个匹配 ，若有 e =( vi,vj ) ? M ，则称 vi 和 vj 在 M 中饱和或 M ? 饱和。若 G 中的每一个顶点都为 M ? 饱和，则称 M 为 G 的一个完美匹配。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-73-320.jpg)
![[ 边覆盖 ] 一个图 G=(V, E) ， E? ? E ，若 G 的任一个顶点都与 E? 中的边关联，则称 E? 覆盖 G ，或称 E? 为 G 的一个边覆盖（集）。 E? 为 G 的一个边覆盖 ? E? ? E ? ( ? u )( u ? V ? ( ? e )( e =( v,w ) ? E? ? ( v = u ? w = u ))) [ 极小边覆盖 ] E? 是 G 的一个极小边覆盖 ? E? 为 G 的一个边覆盖 ? ( ? E 1 )(E 1 ? E? ? E 1 不是 G 的边覆盖 ) [ 边覆盖数 ] 设 G 的所有边覆盖为 E 1 、 E 2 、… 、 E k ，记 为 G 的边覆盖数。 [ 最小边覆盖 ] E i 称为 G 的一个最小边覆盖若 |E i | = ? 1 。 匹配的基本概念](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-74-320.jpg)
![最大匹配的基本定理 [M ? 交互道 ] 设 G 和 M 如上所述， G 的一条 M ? 交互道指 G 中一条路，其中的边在 M 和 E ? M 中交错出现。 [M ? 可增广道 ] 设 G 和 M 如上所述，若 G 的一条 M ? 交互道的始点和终点都是 M ? 不饱和的，则称该 M ? 交互道为一条 M ? 可增广道。 [ 定理 ] 设 G=(V,E) ， M 为 G 中匹配，则 M 为 G 的最大匹配当且仅当 G 中不存在 M ? 可增广道。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-76-320.jpg)
![int g[SIZE][SIZE]; // 注意是二分图两个定点划分间边的情况而非图的邻接矩阵 int n,m; // 二分图两个集合的顶点数 int linker[SIZE]; // 标记 与 Y 部集关联的 X 部集的顶点编号 bool used[SIZE]; // 在每次增广时标记部集 Y 中的点是否已经在匹配中 bool dfs(int a){ // 寻找交替路径 for (int i = 0;i < m;i++) if (g[a][i] && !used[i]){ used[i] = true; if (linker[i] == -1 || dfs(linker[i])){ linker[i] = a; return true; } } return false; } int hungary(){// 返回最大匹配数 int result = 0; memset(linker,-1,sizeof(linker)); for (int i = 0;i < n;i++){ memset(used,0,sizeof(used)); if (dfs(i)) result++; } return result; }](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-78-320.jpg)
![最优匹配 [ 带权二分图 ] 二分图的每条边 (i,j) 均带有一个权 w(i,j). 一个匹配的权是匹配各边权的和。 [ 最优匹配问题 ] 给定带权二分图，求具有最大权的匹配。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-79-320.jpg)
![最优权匹配问题 加权覆盖：给定所有边上的权值，一个加权覆盖就是对标记 u1,u2,u3,…..,un( 二部图中一个部集中的点权标记 ) 和 v1,v2,v3,….vn （另一个部集中的点权标记 ) 的适当选择使得 ui+vj>=wi,j 。对任意 i,j 成立。覆盖 (u,v) 的代价 c(u,v) 指的是： Σui+Σvj. 最小加权问就是找出代价最小的一个加权覆盖。 [ 定理 ] : 对于加权二部图 G 的一个完美匹配 M 和加权覆盖 (u,v) ，有 c(u,v)>=w(M) ，且 c(u,v)=w(M) 当且仅当 M 是由满足 ui+vj=wij 的边组 xiyj 组成的，这种情况下 M 和（ u,v ）都是最优的。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-80-320.jpg)
![最大权二分匹配问题就是给二分图的每条边一个权值，选择若干不相交的边，得到的总权值最大。解决这个问题可以用 KM 算法。理解 KM 算法需要首先理解“可行顶标”的概念。参考以上定义及定理，可行顶标是指对于二分图两边的每个点的一个值 lx 或 ly[j] ，保证对于每条边 w[j] 都有 lx+ly[j]-w[j]>=0 。如果所有满足 lx+ly[j]==w[j] 的边组成的导出子图中存在一个完美匹配，那么这个完美匹配肯定就是原图中的最大权匹配。理由很简单：这个匹配的权值之和恰等于所有顶标的和，由于上面的那个不等式，另外的任何匹配方案的权值和都不会大于所有顶标的和。 但问题是，对于当前的顶标的导出子图并不一定存在完美匹配。这时，可以用某种方法对顶标进行调整。调整的方法是：根据最后一次不成功的寻找交错路的 DFS ，取所有 i 被访问到而 j 没被访问到的边 (i,j) 的 lx+ly[j]-w[j] 的最小值 d 。将交错树中的所有左端点的顶标减小 d ，右端点的顶标增加 d 。经过这样的调整以后：原本在导出子图里面的边，两边的顶标都变了，不等式的等号仍然成立，仍然在导出子图里面；原本不在导出子图里面的边，它的左端点的顶标减小了，右端点的顶标没有变，而且由于 d 的定义，不等式仍然成立，所以他就可能进入了导出子图里。 初始时随便指定一个可行顶标，比如说 lx=max{w[j]|j 是右边的点 } ， ly=0 。然后对每个顶点进行类似 Hungary 算法的 find 过程，如果某次 find 没有成功，则按照这次 find 访问到的点对可行顶标进行上述调整。这样就可以逐步找到完美匹配了。](https://image.slidesharecdn.com/acm-110531201257-phpapp01/85/Acm-81-320.jpg)
