图论-离散数学

图的基本概念

• G = <V, E> 结点集 & 边集
• G的阶：结点数
• (n, m) 图 ⇒ n 个结点 m 条边
• 无向 有向
• 结点相互临接
• 孤立结点
• 自回路
• 平行边 ⇒ 多重图
• 平行边 & 自回路 ⇒ 广义图（伪图）
• 基图
  • 无向图：非简单图转化为对应的简单图形式
  • 有向图：去掉方向的无向图，可以有平行边 环
• 有向图 始点 终点 端点 出边 入边
• 混合图：有向边+无向边
• 赋权图 无权图
• 结点的度数
  • $\deg (u) \ or \ d(u)$
  • 最大点度$ \Delta_G$ 最小点度 \delta_G
  • $\deg (u) = \deg^+(u)+ \deg^-(u)$
  • 入度 出度
• 握手定理 $\sum_{v \in V} \deg(v) = 2m$ m是边！！！
• 零图：孤立结点
• 平凡图：一个孤立结点
• 完全图 无向 & 有向
• 二部图 完全二部图 两个点集合连接
• 子图 真子图 生成子图 平凡子图
• 删点子图 删边子图 点诱导子图 边诱导子图
• 补图 → 相对于完全图
• 同构 → 存在双射… → 形状全等 名称映射
• 通路 = 路径 = 道路 —— ”结点+边“交替表示 有起点终点 边数为长度
• 开道路 闭道路
• 简单道路：边不重复
• 回路：闭简单道路
• 基本道路：结点不相同
• 基本回路 = 圈：闭基本道路
• n 阶图
  • 存在道路 u → v ⇒ 长度不超过 n-1 的道路
  • 存在过 u 回路 ⇒ 长度不超过 n 回路
• “基本” 只经过一次
• 对结点
  • 无向图 ⇒ 有连通性 u ~ v
  • 有向图 ⇒ 有可达性 u → v，还有相互可达
• 连通图 连通分图 = 最大连通子图
• 连通分支数$ \omega(G)$ “多少块 块内连通”
• 点割集 = 割集 ⇒ 删去就不连通 可以多个点 可以有多余
• 基本割集 ⇒ 恰好能使图不连通
• 割点 ⇒ 单个点
• 边割集 基本边割集
• 割边 ⇒ 删去后两端结点不连通
• 点连通度 $\kappa(G)$ 边连通度 $\lambda(G)$ ⇒ 使 G 不连通删去的最少数量 ⇒ 完全图 = n-1，非连通图 = 0
• $\kappa(G) \geq k$ ⇒ k-连通图 边同理
• 单向连通，强连通 相互可达，弱连通 基图连通
• 单向分图，强分图，弱分图
• 邻接矩阵
• 可达性矩阵 ⇒ 相当于邻接矩阵的传递闭包 ⇒ Warshall
• 可达性矩阵可构造强分图：和其转置矩阵 对角线为1 其余位置“与”，圈出“1”的结点方块，再诱导生成
• 关联矩阵
  
• 图的闭包：将所有“间接连通”全部“直接连通”
• K_i 表示 i 个结点的完全图

树

无向树

• 树叶
• 分枝点 = 内点
• 森林 连通分图都是树
• 平凡树
• m = n – 1
• 连通无圈
• 结点之间仅有一条道路
• 树是边数最多的无圈图
• 树是边数最少的连通图
• 生成树：连通图的生成子图是树
  • 连通无向图都含有生成树
  • 树枝 树补边
  • 树补 G-T
  • G 边割集与 T 至少一个公共边
  • G 的圈和树补至少一个公共边
• 最小生成树 类似数据结构
  • 克鲁斯卡尔
  • 普里姆

有向树

• 基图是树 ⇒ 有向树
• 根树 = 外向树
• 树根
• 树叶
• 分枝点
• 内向树：“指向根” → 1个结点出度0 其他1
• 结点层数 道路长度
• 根数高度
• 父亲 儿子 兄弟 祖先 后裔
• 子树
• m 叉树：至多 m 出度
• 完全 m 叉树：分枝点都是 m，(m-1)i = t-1
• 正则 m 叉树：对应数据结构中 满 m 叉树，树叶在同一层
• 各叶子道路长度和 J = I + 2i，I分枝道路长度和
• 位置树
• 最优二叉树 叶加权二叉树 ⇒ Huffman
• 前缀码

平面图

• 任何两条边无交叉点 在一个平面
• 面 边界
• 有界面 = 内部面
• 无界面 = 外部面
• 面度 $\deg (F)$
  • 割边算2
  • 面度的和 是边数的2倍 $\sum \deg(F_i) = 2m$
  • $K_n,n \geq5$ 和 $K_{3,n}, n \geq 3$ 非平面图
• 欧拉公式
  • 面度 f，平面图 (n, m)，连通分支 k
  • $n- m+f =2$
  • $n – m + f = k + 1$
  • 阶数大于 2 的连通简单平面图
    • $m \leq 3n-6$ ⇒ 可用于判断非平面图
    • 存在一个 度不超过 5 的结点
  • 围长 ≥ 3 ⇒ $m \leq \frac {gn-2g}{g-2}$ ⇒ 可用于判断非平面图

欧拉图

• 欧拉道路 每边1次
• 欧拉回路 ⇒ 欧拉图
• 欧拉图连通图
• 平凡图是欧拉图
• 一笔画回到起点
• 充要条件：所有结点度数偶数
• 恰有两个奇数度结点 ⇒ 有欧拉道路无回路
• 有向欧拉回路 ⇒ 入度 = 出度
• 有向欧拉道路 ⇒ 除去2个结点 1个入度大1 & 1个出度大1
• Fleury算法 构造欧拉回路：走过一条边删除一条，有割边走割边
• 中国邮递员问题
  • 不是欧拉图必重复
  • 是欧拉图 任意欧拉回路即可
  • 不是欧拉图
    • 找出奇度数结点 2k个
    • 求两点之间的所有距离
    • k 个路径总和最小：2点一组 任意组合 一组路径k个组合 找出一组和最小的路径
    • 选出的这组路径 2点一组中 距离最短 可以途径其他偶度点
    • 复制这些条路径的边 ⇒ 得到欧拉图
    • 找欧拉回路

哈密顿图

• 哈密顿道路 哈密顿回路
• 含有哈密顿回路 → 哈密顿图
• 包括平凡图
• 判断不是 删点法 任选结点集$S \omega (G-S) > \left |S \right |$的情况存在
• 任意两结点
  u v d(u) + d(v) ≥ n-1 ⇒ 哈密顿道路
  ≥ n ⇒ 哈密顿图 ⇒ 这个条件可以通过加边来实现 ⇒ 这个是必要条件！！
• G是哈密顿图 当且仅当 G的闭包是哈密顿图
• 哈密顿图必是平面图

Tips

• 回路 要回到原点
• 图 是否连通 和“分支”这个概念高度相关 证明时 要提 要用
• 证明
  • 要去想握手定理 定量的定理不多 握手定理很多题都要用 也就是找度的关系
  • 图和树的结论证明 可以用归纳法 k=1时成立 假设k=n时成立 再k=n+1
• 欧拉回路 每条边经过一次
• 哈密顿回路 每个点经过一次

题型

• 同构
  • 证明不同构：结点 边 对应度数的结点数 对应不相同
• 几度 几度的分枝点各多少个 问树叶数 边=点-1 & 握手定理
• 完全 m 叉树问题 凑那个等式
• 树叶数 t，分枝数 i，结点数 n，边数 m，深度 h 之间各种关系
• 平面图的判断
• 写边界 面度
• 构造欧拉回路
• 中国邮递员问题
• 证什么传递性 对称性 和式子等价 尽量就用定义