601 图的基本概念

图的基本概念

图的基本定义与分类

图的数学定义

图 $G$ 是一个二元组 $G=(V,E)$，其中：

• $V$ 是非空的顶点集合（Vertex Set）
• $E$ 是边集合（Edge Set），连接顶点对

图的分类体系

无向图、有向图

• 无向图：边无方向，表示为无序对 $(u,v)$
• 有向图：边有方向（称为弧），表示为有序对 $⟨u,v⟩$

简单图、多重图

• 简单图：无自环、无重边
• 多重图：允许自环或重边存在

完全图

• 无向完全图：$n$ 个顶点的无向图中，任意两个不同顶点之间都恰好有一条边

$$|E|=\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$$

• 有向完全图：$n$ 个顶点的有向图中，任意两个不同顶点 $u,v$ 之间都有两条弧：$⟨u,v⟩$ 和 $⟨v,u⟩$。

$$|E|=n(n-1)$$

带权图（网）、无权图

• 带权图（网络）：边具有权值
• 无权图：边无权值（可视为权值均为 1）

顶点的度数理论

度数的定义

图类型	度数类型	定义	记号
无向图	度	与顶点关联的边数	$\mathrm{deg}(v)$
有向图	入度	以该顶点为终点的边数	$ID(v)$
有向图	出度	以该顶点为起点的边数	$OD(v)$

重要定理

握手定理（无向图）

$$\sum _{v\in V}\mathrm{deg}(v)=2|E|$$

有向图度数定理

$$\sum _{v\in V}ID(v)=\sum _{v\in V}OD(v)=|E|$$ $$\mathrm{deg}(v)=ID(v)+OD(v)$$

路径与连通性

路径相关概念

基本定义

• 路径：顶点序列 $v_0,v_1,\dots ,v_k$，相邻顶点间存在边
• 路径长度：
  • 无权图：边的数量
  • 带权图：边权值之和
• 回路：起点与终点相同的路径（$v_0=v_k$）

特殊路径

• 简单路径：顶点不重复的序列
• 简单回路：除起终点外，其余顶点不重复

距离概念

从顶点 $u$ 到顶点 $v$ 的距离是最短路径的长度。

连通性理论

注意：和 完全图 区分开，连通图只要求任意两点存在路径，而不要求任意两点直接相连。

无向图连通性

连通图：无向图的任意两顶点间都存在路径

最少边数：

• $n$ 个顶点的连通图至少需要 $n-1$ 条边
• 当恰好有 $n-1$ 条边时，该连通图是一棵树

最多边数：

• $n$ 个顶点的连通图最多有 $\frac{n(n-1)}{2}$ 条边
• 达到最大边数时，该图是完全图

环的判定：

• 若连通图有超过 $n-1$ 条边，则必定包含环

连通分量：极大连通子图

• 连通图：1 个连通分量（自身）
• 非连通图：多个互不相交的连通分量

有向图强连通性

强连通图：有向图的任意两顶点间都存在双向路径

最少边数：

• $n$ 个顶点的强连通图至少需要 $n$ 条边
• 最少边数情况：所有顶点形成一个简单有向环

最多边数：

• $n$ 个顶点的强连通图最多有 $n(n-1)$ 条边
• 达到最大边数时，任意两个不同顶点间都有双向边（有向完全图） 强连通分量（SCC）：极大强连通子图
• 性质：SCC 缩点后形成有向无环图（DAG）
• 算法：Tarjan 算法、Kosaraju 算法

图的结构分析

子图概念

子图类型	定义	特点
子图	$V^{\prime }\subseteq V,E^{\prime }\subseteq E$	一般子图（前提是能构成图，即边的两个顶点存在）
生成子图	$V^{\prime }=V,E^{\prime }\subseteq E$	包含所有顶点
导出子图	顶点子集导出的完整边关系	保持原有连接关系

生成树与生成森林

生成树的定义与性质

生成树：连通图 (包含全部顶点) 的极小连通子图，包含所有顶点

关键性质：

• $n$ 个顶点的生成树恰有 $n-1$ 条边
• 添加任一非树边形成回路
• 删除任一树边使图不连通
• 生成树通常不唯一

生成森林

非连通图各连通分量的生成树集合

最小生成树（MST）

带权连通图中边权和最小的生成树

• Prim 算法：适用于稠密图
• Kruskal 算法：适用于稀疏图

图的密度分类与存储策略

图的密度分类

图类型	边数特征	空间复杂度	推荐存储结构
稠密图	$E\approx O(n^2)$	接近最大边数	邻接矩阵
稀疏图	$E\approx O(n)$	远小于最大边数	邻接表

存储结构选择原则

• 邻接矩阵：$O(n^2)$ 空间，适合稠密图，支持 $O(1)$ 查边
• 邻接表：$O(n+E)$ 空间，适合稀疏图，节省空间

特殊图结构

有向树

定义：特殊的有向图，满足以下等价条件：

1. 有且仅有一个入度为 0 的根节点，其余节点入度为 1
2. 从根到任意节点存在唯一路径
3. 对应无向图是树的有向无环图

性质：

• $n$ 个顶点，$n-1$ 条边
• 层次结构，无环
• 应用：文件系统、组织结构等

重要数量关系

边与顶点的约束关系

图类型	最小边数条件	环的存在条件
连通图	$E\ge n-1$	$E>n-1$
强连通图	$E\ge n$	必然存在
树	$E=n-1$	不存在