Graph Theory 01 - Basic Concept
# 前置知识
在阅读本文档前,请先阅读图论的整体介绍文档,详见 Graph Theory 知识板块中的 00 - Introduction 文档。
# 图的定义
通俗地讲, 图 (Graph) 就是由若干个 顶点 (vertex) 和若干条连接两个节点的 边 (edge) 组成的一种非线性数据结构。顶点有时也被称为 节点 (node) 。
定义一个图 ,其中点集 ,边集 。有时也将图 的点集记为 ,边集记为 。
通常我们用 或 的形式来表示节点,用 或 、 或 、 或 的形式来表示边。
记图 的节点数为 ,图 的边数为 ,在只有一个图时可简记为 和 。亦可称 的节点数为 的 阶 。
这里给出了一个 个点、 条边的有向图作为示例,以便于理解图的概念。
对于该图而言,点集 ,边集 。
图的概念非常繁多,但大多数都容易理解和记忆,初学者无需死记硬背,只需先心中有数即可,熟练后自然就能记住。
# 图的基本概念
# 图的基本分类法
如果在图 中 和 表示的是同一条边,则称 为 无向图 (undirected graph) 、称 为无向边,否则称 为 有向图 (directed graph) 、称 为有向边。在实际代码实现中,常用一对反向的有向边来表示一条无向边。
若 中的每条边 都有一个权值 ,则称 是 带权图 (weighted graph) ,否则称 为无权图。
# 节点和边
设 是无向图 上的一条边,则称 和 互为对方的 邻接节点 (adjacent node) ,亦可称 在 中相邻。
设 是有向图 上的一条边,则称 是 的 前继节点 ,称 是 的 后继节点 或 邻接节点 。
设 是一条边,则称 和 是边 的端点。
设 是一条有向边,则称 和 分别是边 的起点 (source) 和终点 (destination) 。
设 和 是无向图上的两条边,则称这两条边互为邻边。
设 和 是有向图上的两条边,则称边 是边 的前继边,称边 是边 的后继边。
若存在两条端点完全相同的无向边,或存在两条起点和终点互相相同的有向边,则称这两条边互为 重边 (multiple edges) 。
# 度
设 是无向图 上的一点,则定义 的 度 (degree) 为 中以 为端点的边 的个数,记为 或 。
设 是有向图 上的一点,则定义 的 入度 (in-degree) 为 中以 为终点的边 的个数,记为 ;定义 的 出度 (out-degree) 为 中以 为起点的边 的个数,记为 。
记无向图 的 最大度 为 , 最小度 为 。
对任意的无向图 有 恒成立。
对任意的有向图 有 恒成立。
# 路径和环
如果图中存在一组边 ,那么我们称这组边构成了一条 路径 (path) ,亦可称这组边中的这些点 构成了一条路径,可简记为 。如果是有向边的话,这些边的方向必须是相同的。
如果一条路径上的任意两个节点均不相同,即构成路径的这些边不构成任何一个环,则称该路径为一条 简单路径 (simple path) 。
设 和 是无向图 上的两点,如果 上存在一条路径 ,则称 和 是 连通 (connected) 的。
设 和 是有向图 上的两点,如果 上存在一条路径 ,则称 从 出发是 可达 的。
如果一条路径的起点和终点相同,即 ,则称该路径为一个 环 (cycle or loop) ,或称为 回路 或 圈 。
如果一个环上所有边的边权之和为负,则称该环为一个 负环 。负环的概念常用于最短路径问题中,因为当图上存在负环时,某些节点之间的最短路径可能会不存在,因为可以无限次地通过负环使距离值下降。相对地,正环会使得最长路径可能不存在。
如果一条简单路径上的起点和终点相同,即 且 则称该路径为一个 简单环 (simple cycle) ,亦可称之为简单回路。对于一个简单环,如果是无向图则必有 ,如果是有向图则必有 。
设 是一条边,若 ,则称该边为一个 自环 (self-loop) 。自环是环,但不是简单环。
# 特殊的图
若图 满足 ,则称 为 空图 (empty graph) 。
若图 满足 ,则称 为 平凡图 (trivial graph) 。显然平凡图一定是空图。
若图 满足 ,则称 为 零图 (null graph) 。显然零图一定是空图。
若图 上不含任何重边和自环,则称 为 简单图 (simple graph) 。在大多数情况下,重边和自环对正在求解的问题的影响都可以被处理掉,将非简单图转化为简单图。
设 是一个简单无向图,若 ,则称 为 完全图 (complete graph) 。若 ,则称 为 阶完全图,记为 。
若图 上不含任何回路,则称 为 无环图 (acyclic graph) 。
设 是一个有向图,若 上不含任何回路,则称 为 有向无环图 (directed acyclic graph, DAG) 。类似地可以组合定义出各种图,而我们将该定义单独提出的理由是,DAG具有许多特殊的性质。
若无向图 满足 ,则称 为 正则图 (regular graph) 。若 ,则称 为 正则图。
# 图的特殊概念
# 树的概念
如果一个无向图 上的任意两点 和 之间都有且仅有一条简单路径,那么称 是一棵树,记为 。显然,一棵有 个节点的树一定有恰好 条边。
通常我们研究的树都是无向树,对于有向树此处不予赘述。
从本质上讲,树其实也只不过是一个图,但它往往会被从图中剥离开来,并且极为重要。其本质原因正是上述定义中说到的,树上任意两点之间有且仅有一条简单路径。不要小看这个特征,正是因为其存在,树才具备了许多一般图所不具备的特质。许多问题在树上可以利用树的特征来解决,如果搬到一般图上,难度会大幅增加、甚至变得在多项式时间内不可解。
设 是无向图 的一个子图,如果 ,且 是一棵树,则称 为 的一棵 生成树 (spanning tree) ,记为 。显然 不一定存在,如果图 不连通,则 上不存在生成树。
设 为带权无向图 的一棵生成树,如果在 的所有生成树中, 的边权和最小,则称 为 的 最小生成树 (minimum spanning tree, MST) 。显然一个图的最小生成树不一定是唯一的,可能存在若干棵边权相等的生成树。
# 连通图的概念
如果一个有向图 上,将所有的有向边都变成无向边后,图上任意两点 和 都是连通的,那么称图 是一个弱连通图。
如果一个有向图 上的任意两点 和 都是连通的,那么称图 是一个 强连通图 (strong connected graph) 。
设 是有向图 的一个子图,若 是一个强连通图,则称 是 的一个强连通子图。
设 是有向图 的一个强连通子图,若向 中增加任意数量的 中的其他点和边,都将使 不满足强连通的性质,则称 是 的一个极大强连通子图,又称为 强连通分量 (strongly connected component, SCC) 。通常我们只研究强连通分量,因为非极大的强连通子图通常没有实用价值。
如果一个无向图 上的任意两点 和 都是连通的,那么称图 是一个 连通图 (connected graph) 。
设 是无向图 上的一个点,如果将 从图中删去会改变图的连通性,那么称 是 上的一个 割点 (cut vertex) 。
设 是无向图 上的一条边,如果将 从图中删去会改变图的连通性,那么称 是 上的一条割边,又称为 桥 (bridge) 。
如果一个无向图 上删去任意一个点都不会改变图的连通性,那么称图 是一个点双连通图。类似于有向图,可以定义 点双连通分量 (vertex-biconnected component) ,因为类同故省略描述。
如果一个无向图 上删去任意一条边都不会改变图的连通性,那么称图 是一个边双连通图。类似于有向图,可以定义 边双连通分量 (edge-biconnected component) ,因为类同故省略描述。
# 拓扑图的概念
设 是一个DAG,把 上的所有节点排成一个线性序列 ,如果对于 中的任意一条边 ,满足 在 中的下标比 的要小,或者说 中的任意一条边 都满足 ,那么称 是 的一个 拓扑序列 。
拓扑序列是针对有向图的概念,与无向图无关。
显然,一个有向图的拓扑序列既不一定存在,也不一定唯一。当且仅当图 是一个DAG时, 的拓扑序列存在。
# 平面图的概念
待补。
# 图的存储及表示方式
图的表示方式有很多种,但竞赛中一般常用的只有三种:邻接矩阵、邻接表、链式前向星。为便于描述,设 和 表示图的最大点数和最大边数,设 和 表示图的点数和边数,设点的编号为 。下面给的例子均为有向图的情形,如果是无向图,只需对每条边建一个权值相同的反相边即可。
# 邻接矩阵
定义一个 的二维矩阵,用 表示边 的边权。可以用 这类值来表示边 不存在,具体选用哪种可根据个人喜好以及实际情况。邻接矩阵适用于稠密图,空间复杂度为 ,如果 太大则不适合使用邻接矩阵,通常适用于 左右的规模。
另外,如果是无权图,直接用bool型的二维矩阵来表示边是否存在即可。
// 邻接矩阵
const int MAXN = N + 5;
int graph[MAXN][MAXN];
// 初始化
for (int i = 0; i < MAXN; i ++) for (int j = 0; j < MAXN; j ++) {
graph[i][j] = INF;
}
// 加入新边
inline void add_edge(int u, int v, int w) {
graph[u][v] = w;
}
// 遍历u的邻接节点
for (int v = 1; v <= n; v ++) {
if (graph[u][v] != INF) {
// ... do something
}
}
当然,根据常识,这些代码并不能全都写在全局区,只是这里为了看起来清爽才这么写,我希望你具备这种常识。下同。
# 邻接表
定义一个长为 的一维的vector数组,用 保存所有以 为起点的边的信息。注意“一维”指的是以vector为基本单位的。邻接表适用于稀疏图,空间复杂度为 。
// 类的定义
class Edge {
public:
int to;
int cost;
Edge(int v, int w) : to(v), cost(w) {}
Edge() {}
}
// 邻接表
const int MAXN = N + 5;
vector<Edge> graph[MAXN];
// 初始化
for (int i = 0; i < MAXN; i ++) {
graph[i].clear();
}
// 加入新边
inline void add_edge(int u, int v, int w) {
graph[u].push_back(Edge(v, w));
}
// 遍历u的邻接节点
for (int i = 0; i < graph[u].size(); i ++) {
Edge & e = graph[u][i];
int v = e.to;
// ... do something
}
// C++11可以用:for (auto & e : graph[u]) { int v = e.to;
另外,如果是无权图,直接用int型的vector数组存储邻接节点的编号即可,无需定义Edge结构来记录边权。
// 邻接表
const int MAXN = N + 5;
vector<int> graph[MAXN];
// 初始化
for (int i = 0; i < MAXN; i ++) {
graph[i].clear();
}
// 加入新边
inline void add_edge(int u, int v) {
graph[u].push_back(v);
}
// 遍历u的邻接节点
for (int i = 0; i < graph[u].size(); i ++) {
int v = graph[u][i];
// ... do something
}
// C++11可以用:for (auto v : graph[u]) {
# 链式前向星
定义一个长为 的一维数组 和一个长为 的一维数组 ,用 保存第 条边的信息,用 保存以 为起点的最后一条边在 中下标的位置。链式前向星也适用于稀疏图,空间复杂度为 。
邻接矩阵和邻接表都很容易理解,链式前向星的原理相对而言稍微有些复杂。事实上,链式前向星本质上就是一个静态链表,详见 Data Structure 知识板块中的 01 - Linear List 文档。
需要注意的是,链式前向星是倒序存储的,也就是说与输入顺序是相反的,最后输入的边反而会最先被遍历到,当然这样显然不会影响结果的正确性。
我们以下面这个简单的有向无权图为例:
输入顺序: 。
对应的邻接表:
$\begin{aligned} graph[1] &= {2,\ 3,\ 4} \ graph[2] &= {4,\ 3} \ graph[3] &= {} \ graph[4] &= {1} \end{aligned}$
对应的链式前向星的构造过程:
每当加入一条新的以 为起点的边时,设该边在 中的下标为,那么我们将 指向原本的 ,然后设 ,可见这样是倒序存储,并且我们可以通过 和每条边的来遍历所有以 为起点的边。实际上链式前向星的结构就是把条链表存在了同一个线性区域上,然后用 个指针实现跳跃遍历,而不像邻接表是直接使用了 块不同的动态区域,因此链式前向星显得不那么直观。
此外,对于上面的例子,直到最后仍有 ,表示不存在以为起点的边。
// 类的定义
class Edge {
public:
int to;
int cost;
int next;
};
// 链式前向星
const int MAXN = N + 5, MAXM = M + 5;
Edge edges[MAXM];
int head[MAXN];
int esize;
// 初始化
memset(head, -1, sizeof(head));
esize = 0;
// 加入新边
inline void add_edge(int u, int v, int w) {
edges[esize].to = v;
edges[esize].cost = w;
edges[esize].next = head[u];
head[u] = esize;
esize ++;
}
// 遍历u的邻接节点
for (int i = head[u]; i != -1; i = edges[i].next) {
Edge & e = edges[i];
int v = e.to;
// ... do something
}
# 二分图的概念
初学者可以先仅了解二分图的概念,等具备一定的图论知识基础后再来学习二分匹配的相关概念。
设 是无向图,如果点集 可以被分割为两个子集 和 满足 且 ,并且对于任意一条边 ,要么 ,要么 ,则称 为 二分图 (bi-partite graph) 。也就是说,图 中的点可以被划分为两个部分,且图上任意一条边的两个端点不属于同一个部分。
当且仅当 是无环图或 上的每个环的大小均为偶数时, 是一个二分图。
设 是二分图, ,如果 中的任意两条边都没有公共端点,则称 是 的一个 匹配 (match) 。
匹配点/未匹配点、匹配边/非匹配边:这些定义的含义非常显然,取决于点、边是否和 相关,不予赘述。
交替路:如果一条路径上的边依次为匹配边、非匹配边、匹配边、非匹配边、……、非匹配边,则称该路径为交替路。
增广路:如果一条交替路的起点和终点是未匹配点,其他点都是匹配点,则称该路径为增广路。增广路上的非匹配边比匹配边要多一条。
最大匹配:设是二分图的一个匹配,如果在的所有匹配中,中的匹配边数最大,则称是的一个最大匹配。
完美匹配:设是二分图的一个匹配,如果中的所有点都是中的匹配点,则称是的一个完美匹配。显然完美匹配一定是最大匹配。一个二分图的完美匹配不一定存在。
完备匹配:设是二分图的一个匹配,如果中的所有点都是中的匹配点,或者中的所有点都是中的匹配点,则称M是G的一个完备匹配。
最大权匹配:设是带权二分图的一个匹配,如果在的所有匹配中,的匹配边边权之和最大,则称是的一个最大权匹配。
最佳匹配:设是带权二分图的一个完备匹配,如果在的所有完备匹配中,的匹配边边权之和最大,则称是的一个最佳匹配。二分图的最佳匹配不一定是二分图的最大权匹配,但可以添加一些权值为的边,使得最佳匹配和最大权匹配统一起来。
# 图的其它概念(理论性质)
# 补图和子图
设 是一个无向图,称以 为点集、以 为边集的图为 的 补图 (complement) ,记为 。
设 和 是两个图,如果 且 ,则称 是 的 子图 (subgraph) ,记为 。
若 是 的子图且 ,则称 是 的 生成子图 (spanning subgraph) 。
设 是一个图,称以 为点集、以 为边集的图为 的由点集 导出的子图,简称为 点导出子图 (induced subgraph) ,记为 。
设 是一个图,称以 为边集、以 为点集的图为 的由边集 导出的子图,简称为 边导出子图 (edge-induced subgraph) ,记为 。
# 图的并、联和对称差
设 和 是两个图,则:
称 为 和 的 并 (union) 。
若 ,则称 为 和 的 不交并 (disjoint union) 或 和 (addition) ,记为 。
若 ,则称 为 和 的 联 (join) 或 连接 。
若 ,称 为 和 的 对称差 (symmetric difference) 。
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01