离散数学: 图论基础
图
图的基本概念
- 图由结点集合V，边集合E，映射关系φ构成，其中φ : E → V × V/{V, V}为由边到结点序偶/两元素集合的函数
- 当φ映射到序偶时，称为有向图，反之为无向图
- 每条边关联的两个点相互点邻接，同一结点上的各条边相互边邻接
- 若e关联的两点是同一结点，称为自回路/环
- 若φ(e1) = φ(e2)，称这两条边互为平行边，在有向图中需注意方向
- 图的分类(侧重点不同的领域定义可能有所不同)：
- 简单图：既没有自回路也没有平行边
- 多重边图：没有自回路，有平行边
- 伪图：有自回路和平行边
- 图的同构：含双射函数f : V → V′, g : E → E′，新的映射关系φ′，满足φ(e) = {v1, v2} → φ′(g(e)) = {f(v1), f(v2)}
- 结点的度数及相关结论：
- 所有结点度数之和d(G)等于两倍的边数
- 一定含偶数个奇度节点
- d度正则图：所有结点度数为d度，若结点数为d + 1，则称其为d + 1阶完全无向图，记为kd + 1
- kn为同阶图中边数最多的图，且$\begin{align}|E|=\frac{n(n-1)}2=C_n^2\end{align}$
- 子图的定义：
- 若子图的三个构成部分都包含于母图，称为子图
- 在子图基础上，若边、映射关系真包含于母图，称为真子图
- 在子图基础上，若结点集合和母图一致，称为生成子图，即对母图只删除边(或不删除)
- 导出子图：分为由边导出和由结点导出
- 路径、回路：
- 路径由若干结点及连接它们的边组成，若起点和终点重合，称其为回路
- 若一条路径/回路中边互不相同，称为简单路径/回路
- 若一条路径结点互不相同/回路除起点外结点互不相同，称为基本路径/回路(圈)
- 若简单回路包含图中所有边，称为欧拉回路；若基本回路包含图中所有点，称为哈密尔顿回路
- 基本路径一定是简单路径，反之不成立；基本回路也不一定是简单回路
- n阶图中，基本路径长度小于等于n − 1
- 连通性：
- 若两结点间有路径，则称它们可达，称最短路径为测地线
- 定义图的直径为最长路径的长度
- 无向图：若任意两结点可达，称G是连通的
- 有向图：
- 若其对应的无向图(也叫基础图)连通，称为弱连通
- 若任意两结点有单向路径，称为单向连通
- 若任意两结点互相可达，称为强连通
- 无向图连通分支：由可达关系(是一个等价类)划分出的等价类导出的子图为连通分支
- 每个连通分支都是一个连通子图
- 若通过删去边/点能使一个连通分支变为两个或以上，称其为割边/割点
- e是割边 ⇔ e不在任何简单回路上
- 邻接矩阵：注意结点没有自回路，结点和自身不可达
- 邻接矩阵的转置：表示其逆图，所有边反向
- 邻接矩阵的幂An：aij表示由i到j的n度路径长度
- 可达性矩阵P：是布尔矩阵，表示可达性
- AAT：aij表示以i/j为起点，共同终于某些结点的边的个数
- ATA：aij表示以某些结点为起点，终于i/j的边的个数