图论基础
图是怎么存的？¶
直接存边¶
什么意思呢？我们开一个数组，数组里每个元素是图的一条边。
这样做有个缺点，每次想要知道两个点之间是否有连边（或者说一条边是否存在），都需要在数组里进行一番查找。而且如果没有对边事先排序的话，就不能使用二分查找的方法（ O(\log n) ），而是每次只能按顺序找（ O(n) ），成本较高。
什么时候会用到这个方法呢？最简单的一个例子是使用 Kruskal 算法求 最小生成树 的时候。
邻接矩阵¶
邻接矩阵的英文名是 adjacency matrix。它的形式是 bool adj[n][n] ，这里面 n 是节点个数， adj[i][j] 表示 i 和 j 之间是否有边。
如果边有权值，也可以直接用 int adj[n][n] ，直接把边权存进去。
它的优点是可以在 O(1) 时间内得到一条边是否存在，缺点是需要占用 O(n^2) 的空间。对于一个稀疏的图（边相对于点数的平方比较少）来说，用邻接矩阵来存的话，成本偏高。
邻接表¶
邻接表英文名是 adjacency list。它的形式是 vector adj[n] ，用 adj[i] 存以 i 为起点的边。
用 vector 无法科学地删除，所以常用 list 实现。
它的特点是可以用来按顺序访问一个结点的出边（或者入边）。
前向星¶
为什么它搜不到英文名呢？因为是中国玩家乱搞出来的。
首先介绍一下链式前向星，本质上是用单向链表实现的邻接表。
形式上是一个结构体： struct edge {edge *pre, int to;} *head[N], edge[M]
这个结构广泛出现于算法竞赛选手的代码中，编写简洁而且对于大多数题目效率足够高。
其中 head[i] 用来存以 i 为起点的边， edge 数组是边表。
那么什么是前向星呢？事先把 edge 数组排个序即可。这里可以使用 基数排序 做到 O(m) 。
图的基本概念¶
路径¶
path，是指一个边的序列，其中的边首尾相连。
简单路径¶
simple path，是每条边只经过了一次的路径。
回路¶
cycle，也称为 环 ，是起点和终点相同的路径。
简单回路¶
图的定点序列中，除了起点和终点相同外，其余顶点不重复的回路。
可达¶
有向图中点 u 到 v 可达是指存在一条 u 到 v 的路径。
连通¶
两个点连通¶
图中点 u 和 v 连通是指两点互相可达。
图连通¶
如果无向图 G 中任意两个节点连通，称其为是连通的。
强连通¶
有向图 G 强连通是指， G 中任意两个节点连通。
弱连通¶
有向图 G 弱连通是指， G 中的所有边替换为无向边后， G 为连通图。
点连通度¶
一张图的点连通度的大小等于最小点割集的大小。
边连通度¶
一张图的边连通度的大小等于最小边割集的大小。
点割集¶
设图 G = <V, E> ，若存在 V' \subset V 且 V' \neq \emptyset ，使得 p(G-V') > p(G) ，而对于任意的 V'' \subset V' ，均有 p(G-V'')=p(G) ，则称 V' 是 G 的点割集。特别地，若 V' 是 G 的点割集，且 V' 是单元集，即 V'=\{v\} ，则称 v 为 割点 。
（ p(G) 表示图 G 的连通分支（连通块）的个数）
边割集¶
设图 G = <V, E> ，若存在 E' \subset E 且 E' \neq \emptyset ，使得 ps(G-E') > p(G) ，而对于任意的 E'' \subset E' ，均有 p(G-E'')=p(G) ，则称 E' 是 G 的边割集（或简称为割集）。特别地，若 E' 是 G 的边割集，且 E' 是单元集，即 E'=\{e\} ，则称 e 为 桥 。
（ p(G) 表示图 G 的连通分支（连通块）的个数）
子图¶
选取一个节点的子集和边的子集构成的图。
生成子图¶
选取的子图的节点和原图一样。
导出子图¶
选取一个节点的子集，再选取这些节点相关联的边的集合构成的图。
边导出子图¶
选取一个边的子集，再选取这些边相关联的节点的集合，构成的图。
连通子图¶
（一个无向图的）连通的子图。
连通分量¶
（一个无向图的）极大的连通子图。
【注】：极大是指添加任何节点或者边后都不再满足。
稀疏图¶
m = \Theta(n) 的图，或者指 m 相对较小的图。
稠密图¶
m = \Theta(n^2) 的图，或者指 m 相对较大的图。
完全图¶
设 D 为 n (n \geq 1) 阶无向简单图，弱 G 中每个顶点均与其余的 n-1 个顶点相邻，则称 D 为 n 阶无向完全图。
无向完全图的点数和边数满足这样的关系： m = \frac{n(n-1)}{2} 。
设 D 为 n (n \geq 1) 阶有向简单图，若对于任意的 v_i, v_j \in V(D)(v_i \neq v_j) ，有向边 <v_i, v_j> 和 <v_j, v_i> 均属于 E(D) ，则称 D 为 n 阶有向完全图。
竞赛图¶
设 D 为 n (n \geq 1) 阶有向简单图，若对于任意的 v_i, v_j \in V(D)(v_i \neq v_j) ，有向边 <v_i, v_j> 和 <v_j, v_i> 中有且仅有一个属于 E(D) ，则称 D 为 n 阶竞赛图。
正则图¶
各顶点的度均相同的无向简单图。
路径的长度¶
一般来说，路径的长度在数值上等于路径的边数，或者如果边是带权的，则是路径的边权和。
最短路径¶
两个节点之间，长度最小的路径。
【注】：不一定存在，不一定唯一。
图论基本定理¶
又称握手定理。设 G=<V, E> 为一个无向图， V= \{v_1, v_2, \cdots, v_n\}, |E| = m ，则 \sum_{i=1}^n{d(v_i)}=2m 。其中 d(v) 表示 v 的度数。
可图化¶
如果给定一个序列 a，可以找到一个图 G，以其为度数列，则称 a 是可图化的。
如果给定一个序列 a，可以找到一个简单图 G，以其为度数列，则称 a 是可简单图化的。
判别法¶
a=(a_1, a_2, \cdots, a_n) 可图化当且仅当 \sum_{i=1}^n{d_i} = 0 \pmod 2
a=(a_1, a_2, \cdots, a_n) 可简单图化当且仅当 a'=(a_2 - 1, a_3 - 1, \cdots, a_{a_1+1} - 1, a_{a_1+2} - 1, \cdots, a_n) 是可简单图化的。
Whitney 定理¶
对任意的图 G ，有 \kappa \leq \lambda \leq \delta 。其中 \kappa, \lambda, \delta 分别为 G 的点连通度，边连通度和最小度。
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用