图论基础

图是怎么存的?

直接存边

什么意思呢?我们开一个数组,数组里每个元素是图的一条边。

这样做有个缺点,每次想要知道两个点之间是否有连边(或者说一条边是否存在),都需要在数组里进行一番查找。而且如果没有对边事先排序的话,就不能使用二分查找的方法( 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 的点连通度,边连通度和最小度。


评论