图论
参考资料
- 电科大离散数学 - 标准离散数学 - 3
- 离散数学及其应用 - 翻译版, 包括 "离散数学" 和组合数学 / 初等数论 /... - 4
基本
- 边 / 弧, 顶点 / 弧头弧尾
- 以有向 / 无向, 是否多重边, 是否允许自环来区分图类型
- 度 / 出度入度
- 根据这些定义可以显然推得一些数量关系
- 带权 (指边 / 弧) 图亦称网
特殊的简单图
- 完全图, 每对顶点都有边 (表示为 \(K_n\))
- 圈图, 字面意思
- 轮图, 加一个与其它所有顶点有边的顶点的圈图
- n 立方体图, 字面意思
二分图
- 分俩集合, 仅与对方集合顶点存在边
- 完全二分图, 字面, 表示为 \(K_{n,m}\)
- 特别的, 若二分图的边集合的一个子集中没有两边关联同一顶点, 称之为匹配
- 霍尔婚配定律, 若二分图一个点集的任意非空子集的基都小于等于其邻接点集的基, 则有完全匹配
- \(\forall S \subseteq \mathcal{X},\ |N(S)| \geq |S| \Rightarrow \exists \mathcal{X}-\text{完全匹配}\)
子图
- 将两个邻接顶点变为一个顶点 (并删除相应的边), 称为收缩
图的表示
- 邻接表 / 邻接矩阵, 按图的疏密选择
- 关联矩阵, 描述边点是否关联
同构
连通性
无向图连通性
- 路径 / 环
- 无向图两顶点有路径为连通, 无向图任意两点连通为连通图
- 若能删除一个点, 使连通图不连通, 称为割点
- 有 k 个割点的图称为 k 联通图
- 极大 (最多顶点) 连通子图 (包含依附的边) 称为图的连通分量
有向图连通性
- 有向图强连通要求双向存在路径, 否则为弱联通
- 强连通分量
欧拉通路与哈密顿通路 (都是简单路径!!!)
- 欧拉通路 / 回路, 要求包含每一条边
- \(\forall v \in V,\ \deg(v) \equiv 0 \pmod{2} \Rightarrow \text{欧拉回路}\)
- \(\exists!\, u,v \in V,\ \deg(u) \equiv \deg(v) \equiv 1 \pmod{2} \Rightarrow \text{欧拉通路且不为回路}\)
- 哈密顿通路 / 回路, 要求包含每一个点
- \(n \geq 3 \ \land\ \forall v \in V,\ \deg(v) \geq \lceil n/2 \rceil \Rightarrow \text{哈密顿回路存在}\)
- \(n \geq 3 \ \land\ \forall u \nsim v,\ \deg(u)+\deg(v) \geq n \Rightarrow \text{哈密顿回路存在}\)
- 没找到可高效计算的哈密顿充要
平面图
- 画出来没交点
- 平面图分割的 \(面数 r = 边数 e - 点数 v + 2\)
- 可以推出, 联通平面简单图
- \(v \geq 3 \Rightarrow e \leq (3*v - 6)\)
- $\exists v \in V,\ \deg(v) \leq 5 $
- \(v \geq 3 \ \land \ \text{无长度为3的回路} \Rightarrow e \leq 2v - 4\)
- 可以检验平面图
- 若一个图可以通过初等细分 (~~把一条边掰断~~) 转换为另一个图, 则称同胚
- 平面图 \(\Leftrightarrow\) 不存在子图同胚于 \(K_5 / K_{3,3}\)
- 四色定理
树
- 没有简单回路的连通无向图
- 森林指不相交的树的集合 (不连通)
- \(树的边数 e = 节点数 v - 1\)
有根性
- 定义根, 使边具有远离根的方向
- 节点的子树数是节点的度, 度为 0 的节点是叶节点 / 终端节点, 反之是非终端节点 / 分支节点, 非根的分支节点也叫内部节点
- 具有 \(i\) 个内点的树有 \(m*i+1\) 个节点
- 树的度是树内各节点度的最大值
深度
- 树最大节点层次是树的深度
- 树最多有 \(h^m\) (深度\(h\), 叉数\(m\)) 个叶子
二叉树
- \(\mathcal{B} = {\emptyset} \cup { (v, L, R) \mid v \in V,\ L, R \in \mathcal{B} }\)
- 只有左 / 右的二叉树即斜树 (链表就是)
- 满二叉树: 所有叶节点都在同一层的二叉树 (\(2^n-1\) 个节点)
- 完全二叉树: 除了叶节点, 所有节点都有两个孩子的二叉树 (满二叉树的子集)
树的遍历
生成树
- 连通图的极小 (包含所有点与此情况的最少边 (\(n-1\))) 连通子图称为生成树
- 有向图中有一顶点入度为 0, 其余为 1 称有向树
- 有向图去掉一些弧至其仅由有向树构成称其为图的有向森林
网路流