【图论】基本概念与图的存储

图论中的一些基本概念和图的存储方法

基本概念

顶点&边

• 顶点 (Vertex or Node) 构成点集 (Vertex set)。

• 边(Edge) 构成边集 (Edge set)

  • 常记作$(u,v)$，$u,v$ 称为$e$ 的 端点 (Endpoint)。
  • 有向边 (Directed edge) 或 弧 (Arc)： $(u,v)$ 有序，有时也写作 $u \to v$ 。设 $e=u \to v$，则此时$u$ 称为$e$ 的 起点 (Tail)，$v$ 称为$e$ 的 终点 (Head)，并称$u$ 是$v$ 的直接前驱，$v$ 是$u$ 的直接后继。
  • 无向边 (Undirected edge) 或边 (Edge)：$(u,v)$ 无序。

图

图 (Graph) 是一个二元组$G=(V(G), E(G)) $ ，其中$V(G)$ 是非空点集 (Vertex set)，$E(G)$ 是边集 (Edge set)。

常记作$G=(V,E)$ ，图$G$ 的点数$|V(G)|$ 也被称作图$G$ 的阶 (Order)。

自环与重边

自环 (Loop)：$\exists e=(u,v)\in E,且u=v$，则$e$ 称作自环。

重边 (Multiple edge)：若$E$ 中存在两个完全相同的边，则它们被称作（一组）重边。

分类与相关概念

按有限性分类

当$V,E$ 都是有限集合时，称$G$ 为 有限图；当$V$ 或$E$ 是无限集合时，称$G$ 为无限图。

按边的性质分类

有向图 (Directed graph)：$E$ 中均为有向边。

无向图 (Undirected graph)：$E$ 中均为无向边。

混合图 (Mixed graph)：$E$ 中既有有向边也有无向边。

赋权图：每条边都有权值。其中边权全是正的为正权图。

稀疏图 (Sparse graph)：边很多，**稠密图 (Dense graph)**刚好相反。这个一般用于讨论时间复杂度为$O(|V|^2)$ 的算法与$O(|E|)$ 的算法的效率差异（稀疏图优先选择后者）。

补图：对于无向图

反图

简单图 (Simple graph)：若一个图中没有自环和重边，它被称为简单图。否则为多重图 (Multigraph)。

点的相邻和点的度

• 对于两顶点$u$ 和$v$ ，若存在边$(u,v)$ ，则称$u$ 和$v$ 是相邻的 (Adjacent)。

  一个顶点$v\in V$ 的**邻域 (Neighborhood)**是所有与之相邻的顶点所构成的集合，记作$N(v)$。

  一个点集$S$ 的邻域是所有与$S$ 中至少一个点相邻的点所构成的集合，记作$N(S)$ ，即$N(S)=\bigcup_{v\in S} N(v)$。

• 度 (Degree) ：与一个顶点$v$ 关联的边的条数，记作$d(v)$​ 。

  • 无向简单图，有$d(v)=|N(v)|$ 。

  • 握手定理（图论基本定理）：对于任何无向图$G(V,E)$ ，有$\sum_{v\in V}d(v)=2|E|$ 。

    推论：在任意图中，度数为奇数的点必然有偶数个。

  • 孤立点 (Isolated vertex)：$d(v)=0$

    叶节点 (Leaf vertex)/悬挂点 (Pendant vertex)：$d(v)=1$

    偶点 (Even vertex)：$2\mid d(v)$

    奇点 (Odd vertex)：$2\nmid d(v)$，其中一张图中奇点必有偶数个。

  • 对于一张图，所有节点的度数的最小值称为最小度 (Minimum degree)，记作$\delta(G)$ ，最大值称为最大度 (Maximum degree)，记作$\Delta(G)$ 。

  • 对于有向图，以一个顶点为起点的边的条数称为该顶点的出度 (Out-degree)，记作 $d^+(v)$ 或$out(v)$ 。以一个顶点为终点的边的条数称为该节点的入度 (In-degree)，记作$d^-(v)$ 或$in(v)$ 。对于任何有向图 ，有：$\sum_{v \in V} d^+(v)=\sum_{v \in V} d^-(v)=|E|$

  • 对于无向图 ，每个顶点的度数都是一个固定的常数的，称为 k - 正则图 (-Regular Graph)。

路径

将若干个点连接起来的边的集合。

边的数量被称作这条途径的长度，如果边是带权的，长度通常指路径上的边权之和。

• 简单路径 (Simple path)：路径连接的点两两不同。
• 回路 (Circuit)：路径头尾相接。
• 简单回路/简单环 (Simple circuit)：路径中仅头尾相接。

子图

对于图$G$ ，$\exists H=(V',E'),V'\in V,E'\in E$ ，则称$H$ 是$G$ 的子图 (Subgraph)，记作$H \subseteq G$ 。

连通性

存在一条$u$ 到$v$ 的路径则$u,v$ 连通 (Connected)。

无向图

• 图中任意两个顶点均连通的称连通图 (Connected graph)。

• 若$H$ 是$G$ 的一个连通子图，则$H$ 是$G$ 的一个连通块/连通分量 (Connected component)。若不存在$F$ 使$H\subsetneq F\subseteq G$ 则$H$ 是$G$ 的一个极大连通子图。

有向图

• 有向图的节点两两互相可达，则称这张图是强连通的 (Strongly connected)。
• 一张有向图的边替换为无向边后可以得到一张连通图，则称原来这张有向图是弱连通的 (Weakly connected)。
• 同无向图，有弱连通分量 (Weakly connected component)、极大弱连通子图、强连通分量 (Strongly Connected component)、极大强连通子图。

割

• 强连通图 $G=(V, E)$, 若 $V^{\prime} \subseteq V$ 且 $G\left[V \backslash V^{\prime}\right]$ 不是连通 图, 则 $V^{\prime}$ 是图 $G$ 的一个点割集 (Vertex cut/Separating set)。大小为一的点割集又被称作割点 (Cut vertex)
• 强连通图 $G=(V, E)$ 和整数 $k$, 若 $|V| \geq k+1$ 且 $G$ 不存在大小为 $k-1$ 的点割集, 则称 图 $G$ 是**$k$-点连通的 $(k$-vertex-connected)** ，使上式成立的最大的 $k$ 被称作图 $G$ 的点连通度 (Vertex connectivity)，记作 $\kappa(G)$ 。
  • 非完全图点连通度为最小点割集的大小, 完全图 $K_{n}$ 的点连通度为 $n-1$ 。
• 对于图 $G=(V, E)$ 以及 $u, v \in V$ 满足 $u \neq v, u$ 和 $v$ 不相邻, $u$ 可达 $v$, 若 $V^{\prime} \subseteq V_{\text {, }}$ $u, v \notin V^{\prime}$, 且在 $G\left[V \backslash V^{\prime}\right]$ 中 $u$ 和 $v$ 不连通, 则 $V^{\prime}$ 被称作 $u$ 到 $v$ 的点割集。 $u$ 到 $v$ 的最小点割集的大小被称作 $u$ 到 $v$ 的 局部点连通度 (Local connectivity), 记作 $\kappa(u, v)$ 。
• 对于连通图 $G=(V, E)$, 若 $E^{\prime} \subseteq E$ 且 $G^{\prime}=\left(V, E \backslash E^{\prime}\right)$ (即从 $G$ 中删去 $E^{\prime}$ 中的边) 不是连通图, 则 $E^{\prime}$ 是图 $G$ 的一个边割集(Edge cut)。大小为一的边割集又被称作桥 (Bridge)。
• 对于连通图 $G=(V, E)$ 和整数 $k$, 若 $G$ 不存在大小为 $k-1$ 的边割集, 则称图 $G$ 是 $k$ - 边连通的 $(k$-edge-connected)，使上式成立的最大的 $k$ 被称作图 $G$ 的边连通度 (Edge connectivity)，记作 $\lambda(G)$ 。边连通度为最小边割集的大小。
• 对于图 $G=(V, E)$ 以及 $u, v \in V$ 满足 $u \neq v, u$ 可达 $v$, 若 $E^{\prime} \subseteq E$, 且在 $G^{\prime}=\left(V, E \backslash E^{\prime}\right)$ 中 $u$ 和 $v$ 不连通, 则 $E^{\prime}$ 被称作 $u$ 到 $v$ 的边割集。 $u$ 到 $v$ 的最小边割集的大 小被称作 $u$ 到 $v$ 的 局部边连通度 (Local edge-connectivity), 记作 $\lambda(u, v)$ 。
• 点双连通 (Biconnected)：没有割点的强连通图是点双连通的。
  • 即对于任意两个点，无论删去图中哪个点（只能删去一个，且不能删自己），它们始终连通。
  • 点双连通没有传递性
• 边双连通 (2-edge-connected) ：没有桥的强连通图是边双连通的。
  • 即对于任意两个点，无论删去哪条边（只能删去一条），它们始终连通。
  • 边双连通有传递性

存图

邻接矩阵

邻接矩阵（二维数组）：空间$O(n^2)$ ，$G[i][j]$ 表示$i\rightarrow j$ 的边是否存在/权值大小

一般不用于稀疏图

遍历时先检查是否有边

邻接表

无边权

vector<int> G;
void add_edge(int from, int to) {
	G[from].push_back(to);
}

有边权

排序之后可以log复杂度查边

结构体写法：

struct edge {
  int v,val;
};
vector<edge> graph[N];
void add_edge(int from,int to,int value) {
    graph[from].push_back((edge){to,value});
}
//遍历在C++14后可以写作：
//for(auto it:graph[i])
//其中it相当于graph[i][j]

pair写法：

typedef pair<int, int> pii;
vector<pii> G[N];
void add_edge(int from, int to, int value) {
    graph[from].push_back(make_pair(to, value));
}

邻接链表

以链表储存每一个点的所有边

链式前向星：

struct Edge{
    int to,val,nxt; //一般不用存边的起点
}edge[M];//M看数据，未给就是N*N（N为节点数）
int head[N]; //初始化为-1
int tot;
void add_edge(int u, int v, int w)	//添加一条u->v的权为w的边
{
	++tot;
	edge[tot].to = v;
	edge[tot].val = w;
    edge[tot].nxt = head[u];
	head[u] = tot;
}
//遍历写作：
//for(int i=head[x];~i;i=edge[i].nxt)

无向边存邻接表的技巧：每条边的序号$i$ 为偶数，反边存在$i+1$，利用位运算$i$^$1$ 迅速找到反边