图论基础

• 图
  • 定义
    • 基本内容
      • 定义集合 $A,B$ 的无序积为 $A\operatorname{\&}B=\{ (a,b) \mid a \in A \land b \in B \}$。
      • 定义无向图 $G=\langle V,E \rangle$，满足
        • $V$ 为非空有穷集，称为点集，元素称为结点，记作 $V(G)$。
        • $E$ 为 $V\operatorname{\&}V$ 的有穷多重子集，称为边集，元素称为无向边，记作 $E(G)$。
      • 定义有向图 $D=\langle V,E \rangle$，满足
        • $V$ 与无向图定义相同。
        • $E$ 为 $V\times V$ 的有穷多重子集。
      • 定义图的结点数为图的阶，$n$ 个结点的图称为 $n$ 阶图，$|V(G)| = n$。
    • 关联和相邻
      • 关联：已知 $e_k=(v_i,v_j)$，则 $e_k$ 与 $v_i,v_j$ 关联。
        • 若 $v_i=v_j$，则 $e_k$ 与 $v_i,v_j$ 的关联次数为 $2$。
        • 若 $v_i\ne v_j$，则为 $1$。
        • 若 $v_l\ne v_i\land v_l\ne v_j$，则 $e_k$ 与 $v_l$ 的关联次数为 $0$。
      • 相邻：已知 $e_k=(v_i,v_j)$，则 $v_i$ 与 $v_j$ 相邻。
      • 对无向图 $G=\langle V,E\rangle$
        • 邻域：$N_G(v) = \{ u \mid u \in V \land u \ne v \land (u,v) \in E\}$
        • 闭邻域：$\overline N_G(v) = N_G \cap \{ v\}$
        • 关联集：$I_G(v) = \{ e \mid e \in E \land e$ 与 $v$ 关联 $\}$
      • 对有向图 $D=\langle V,E\rangle$
        • 后继元素：$\Gamma^+(v) = \{ u \mid u \in V \land \langle v, u \rangle \in E\}$
        • 前驱元素：$\Gamma^-(v) = \{ u \mid u \in V \land \langle u,v \rangle \in E\}$
        • 邻域：$N_D(v) = \Gamma^+(v) \cap \Gamma^-(v)$
        • 闭邻域：$\overline N_D(v) = N_D(v) \cap \{v\}$
      • 平行边：关联一对结点的边的个数大于 $1$ 的边。重复的次数称为重数。
      • 简单图：没有平行边的图。
    • 度数
      • 度数：
        • 对无向图，$v$ 作为边的端点的次数称为度数，记作 $d_G(v)$。
        • 对有向图，$v$ 作为边的终点的次数称为入度 $d^+_D(v)$，作为边的起点的次数称为出度 $d^-_D(v)$，度为 $d_D(v) = d^+_D(v)+d^-_D(v)$。
      • 对无向图，最大度 $\Delta(G)=\displaystyle\max_{v\in V} \{d_G(v)\}$，最小度 $\delta(G) = \displaystyle\min_{v\in V}\{d_G(v)\}$。对有向图的度有类似定义。
      • 悬挂结点：度数为 $1$ 的结点
      • 悬挂边：与悬挂结点关联的边
      • 奇 / 偶度结点：度数为奇 / 偶数的结点
    • 特殊图
      • 零图：边集为空的图，$n$ 阶零图记作 $N_n$，$N_1$ 称为平凡图。
      • 空图：点集为空的图，记作 $\varnothing$。
      • 标定图：图的结点和边都有编号的图，否则为非标定图。
      • 基图：将有向图的边都修改为无向后得到的图。
      • 完全图：$n$ 阶无向完全图记作 $K_n$。$n$ 阶有向完全图在每一对结点之间都有双向的边。若 $n$ 阶有向图的基图为 $K_n$，则其为 $n$ 阶竞赛图。
      • 正则图：度数均为 $k$ 的无向图称为 $k$-正则图。
    • 图的关系
      • 同构：对于图 $G_1=\langle V_1,E_1\rangle,G_2=\langle V_2,E_2\rangle$，存在双射 $f:V_1\to V_2$，满足 $(v_1,v_2)\in E_1 \iff (f(v_1),f(v_2))\in E_2$，且对应边重数相同，则 $G_1,G_2$ 同构，记作 $G_1\cong G_2$。
      • 子图：已知 $G=\langle V,E\rangle,G'=\langle V',E'\rangle$，若 $V'\subseteq V,E'\subseteq E$，则 $G'$ 为 $G$ 的子图，记作 $G'\subseteq G$，$G$ 为 $G'$ 的母图。
      • 真子图：$G=\langle V,E\rangle \supseteq G'=\langle V',E'\rangle$，若 $V' \ne V$ 或 $E'\ne E$，则 $G'$ 为 $G$ 的真子图。
      • 生成子图：$G=\langle V,E\rangle \supseteq G'=\langle V',E'\rangle$，若 $V'=V$，则 $G'$ 为 $G$ 的生成子图。
      • 导出子图：$G=\langle V,E\rangle \supseteq G'=\langle V',E'\rangle$
        • 若 $E' = \{(v_1,v_2) \mid v_1,v_2\in V' \land (v_1,v_2)\in E\}$，则 $G'$ 为 $G$ 的 $V'$ 导出的子图，记作 $G[V']$。
        • 若 $V' = \{v \mid \exists v' (v'\in V \land (v,v') \in E')\}$，则 $G'$ 为 $G$ 的 $E'$ 导出的子图，记作 $G[E']$。
      • 补图：$G=\langle V,E\rangle$，令 $\overline E = \{ (u,v) \mid u,v \in V \land (u,v) \notin E\}$，则 $\overline G = \langle V,\overline E\rangle$ 为 $G$ 的补图。
      • 自补图：若 $G \cong \overline G$，则 $G$ 为自补图。
  • 性质
    • 度数
      • 握手定理：
        • 对 $G=\langle V,E\rangle$，$\displaystyle\sum d_G(v_i) = 2|E|$。
        • 对 $D=\langle V,E\rangle$，$\displaystyle\sum d_D(v_i) = 2|E|$，$\displaystyle\sum d^+_D(v_i) = \sum d^-_D(v_i) = |E|$。
      • 可图化：
        • 已知度数列 $(d_1,d_2,\dots,d_n)$，若存在 $G=\langle V=\{v_1,v_2,\dots,v_n\},E\rangle$，满足 $d_i=d_G(v_i)$，则度数列可图化。
        • 若 $G$ 可以为简单图，则度数序列简单可图化。
        • 对有向图可以有出度列和入度列。
        • $(d_1,d_2,\dots,d_n)$ 可图化 $\iff (d_1,d_2,\dots,d_n)$ 满足 $\displaystyle\sum_{i=1}^n d_i$ 为偶数。
        • 简单可图化必要条件：$\Delta(G) \le n - 1$。
• 图的连通性
  • 通路和回路
    • 定义
      • 设 $G = \langle V,E\rangle$ 为无向标定图，结点与边的交替序列 $\mathcal\Gamma = v_{i_0}e_{j_1}v_{i_1}e_{j_2}v_{i_2}\dots e_{j_l}v_{j_l}$ 称为 $v_{i_0}$ 到 $v_{i_l}$ 的通路。
      • 若 $\mathcal\Gamma$ 中 $v_{i_0}=v_{i_l}$，则 $\mathcal\Gamma$ 称为回路。
      • 若 $\mathcal\Gamma$ 中边都不同，则 $\mathcal\Gamma$ 是简单通路，否则有边重复出现，$\mathcal\Gamma$ 为复杂通路。
      • 若 $\mathcal\Gamma$ 中边都不同且 $v_{i_0}=v_{i_l}$，则 $\mathcal\Gamma$ 是简单回路，否则有边重复出现，$\mathcal\Gamma$ 为复杂回路。
      • 若 $\mathcal\Gamma$ 中所有点和边都不同，则 $\mathcal\Gamma$ 是初级通路 / 路径。
      • 若 $\mathcal\Gamma$ 中除了 $v_{i_0}=v_{i_l}$ 所有点和边都不同，则 $\mathcal\Gamma$ 是初级回路 / 圈。
      • 定义长度为 $\mathcal\Gamma$ 边的个数。
      • 对于有向图有类似定义。
    • 性质
      • 在 $n$ 阶图中，若 $u\ne v$ 且存在 $u$ 到 $v$ 的通路，则存在 $u$ 到 $v$ 的长度小于等于 $n-1$ 的初级通路 / 路径。
      • 在 $n$ 阶图中，若存在 $v$ 到自身的回路，则存在 $v$ 到自身的长度小于等于 $n$ 的回路。
      • 在 $n$ 阶图中，若存在 $v$ 到自身的简单回路，则存在 $v$ 到自身的长度小于等于 $n$ 的初级回路 / 圈。
  • 无向图连通性
    • 基本定义
      • 设 $G = \langle V,E\rangle$ 为无向图，若 $u,v\in V$ 之间存在通路，则 $u,v$ 连通，记作 $u\sim v$。
      • 若 $G$ 是平凡图或任意两个结点都是连通的，则 $G$ 是连通图，否则为非连通图。
      • 连通关系 $\sim$ 是一个等价关系，$V_i$ 是 $V$ 的一个等价类，则 $G[V_i]$ 是一个连通分支。
      • $G$ 的连通分支数记作 $p(G)$。$n$ 阶图中，$K_n$ 有最小 $p=1$，$N_n$ 有最大 $p=n$。
      • $u,v$ 之间最短路径的长度为距离 $d(u,v)$，若 $u\not\sim v$，则 $d(u,v)=\infty$。
    • 连通程度
      • 对 $G = \langle V,E\rangle$
        • 若 $V'\subset V$ 使得 $p(G-V')>p(G)$，且任意 $V'' \subset V'$ 满足 $p(G-V'')=p(G)$，则 $V'$ 为点割集。
        • 若 $|V'|=1$，则 $V'$ 中的唯一元素 $v$ 称为割点。
        • 若 $E'\subset E$ 使得 $p(G-E')>p(G)$，且任意 $E'' \subset E'$ 满足 $p(G-E'')=p(G)$，则 $E'$ 为边割集。
        • 若 $|E'|=1$，则 $E'$ 中的唯一元素 $e$ 称为割边 / 桥。
      • 点连通度：已知 $G$ 为连通图，定义 $\kappa(G) = \min |V'|$，其中 $V'$ 为 $G$ 的点割集。
        • 规定 $\kappa(K_n) = n - 1$，非连通图的 $\kappa = 0$。
        • 若 $\kappa(G) \ge k$，则 $G$ 是 $k$-连通图。$k$-连通图至少需要删除 $k$ 个点才可能使其不连通。
      • 边连通度：已知 $G$ 为连通图，定义 $\lambda(G) = \min |E'|$，其中 $E'$ 为 $G$ 的边割集。
        • 规定非连通图的 $\lambda=0$。
        • 若 $\lambda(G) \ge k$，则 $G$ 是 $k$ 边-连通图。$k$ 边-连通图至少需要删除 $k$ 条边才可能使其不连通。
      • 已知 $G_1,G_2$ 为连通图
        • 若 $\kappa(G_1)>\kappa(G_2)$，则 $G_1$ 的点连通程度高。
        • 若 $\lambda(G_1)>\lambda(G_2)$，则 $G_1$ 的边连通程度高。
      • 对任意无向图 $G$，有 $\kappa(G) \le \lambda(G) \le \delta(G)$。
  • 有向图连通性
    • 基本定义
      • 设 $D=\langle V,E\rangle$ 为有向图，若从 $u$ 到 $v$ 存在通路，则 $u$ 到 $v$ 可达，记作 $u \to v$。
        • 若 $u\to v$ 且 $v \to u$，则 $u,v$ 相互可达，记作 $u \leftrightarrow v$。
        • 规定 $u \to u$。
      • $\to$ 和 $\leftrightarrow$ 都是二元关系，其中 $\leftrightarrow$ 是等价关系。
      • $u$ 到 $v$ 的最短路径的长度为距离 $d\langle u,v\rangle$。$d\langle u,v\rangle$ 相比 $d(u,v)$ 没有对称性。
    • 性质
      • 对 $D=\langle V,E\rangle$
        • 若 $D$ 的基图是连通图，则 $D$ 是弱连通图，简称连通图。
        • 若任意 $u,v \in V$ 有 $u\to v$ 或 $v \to u$，则 $D$ 是单向连通图。
        • 若任意 $u,v \in V$ 有 $u \leftrightarrow v$，则 $D$ 是强连通图。
        • 强连通图是单向连通图，单向连通图是弱连通图。
      • $D=\langle V,E\rangle$ 是强连通图 $\iff$ $D$ 中存在经过每个结点至少一次的回路。
      • $D=\langle V,E\rangle$ 是单向连通图 $\iff$ $D$ 中存在经过每个结点至少一次的通路。
  • 二分图
    • 定义
      • 设 $G = \langle V,E\rangle$ 为无向图，若可以划分 $V$ 为 $V_1,V_2$，且 $E$ 中任意的边的端点分别在 $V_1,V_2$，则 $G$ 为二分图。
      • 二分图记作 $\langle V_1,V_2,E\rangle$。
      • 若 $V_1$ 中任意结点都与 $V_2$ 中结点相邻，则 $G$ 为完全二分图，记作 $K_{r,s}$，其中 $|V_1|=r,|V_2|=s$。
    • 性质
      • $n\ (n\ge 2)$ 阶无向图 $G$ 是二分图 $\iff$ $G$ 中无奇圈。
• 图的矩阵表示
  • 无向图的关联矩阵
    • 定义
      • 已知无向图 $G=\langle V,E\rangle$，$V = \{v_1,v_2,\dots,v_n\}$，$E=\{e_1,e_2,\dots,e_m\}$。
      • 定义 $G$ 的关联矩阵 $M(G) = (m_{ij})_{n\times m}$，其中 $m_{ij}$ 为 $v_i$ 与 $e_j$ 的关联次数。
    • 性质
      • $M(G)$ 中一列对应一条边，每一列的和 $\displaystyle\sum_{i=1}^n m_{ij} = 2$。
      • $M(G)$ 中一行对应一个点，每一行的和 $\displaystyle\sum_{j=1}^m m_{ij} = d_G(v_i)$。
      • 握手定理：$\displaystyle\sum_{i=1}^n\sum_{j=1}^m m_{ij} = 2m$。
      • $e_i$ 与 $e_j$ 是平行边 $\iff$ $M(G)$ 中第 $i$ 列与第 $j$ 列相同。
  • 有向图的关联矩阵
    • 定义
      • 已知有向图 $D=\langle V,E\rangle$，$V = \{v_1,v_2,\dots,v_n\}$，$E=\{e_1,e_2,\dots,e_m\}$。
      • 定义 $D$ 的关联矩阵 $M(D) = (m_{ij})_{n\times m}$，其中 $m_{ij}$ 按照如下取值：
        • 若 $v_i$ 是 $e_j$ 的始点，则 $m_{ij}=1$。
        • 若 $v_i$ 是 $e_j$ 的终点，则 $m_{ij}=-1$。
        • 否则 $m_{ij}=0$。
    • 性质
      • $M(G)$ 中每一列的和 $\displaystyle\sum_{i=1}^n m_{ij} = 0$，恰好分别存在一个 $1,-1$。
      • $M(G)$ 中每一行有 $\displaystyle\sum_{j=1}^m 1\{m_{ij}=1\} = d^+_G(v_i)$，$\displaystyle\sum_{j=-1}^m 1\{m_{ij}=-1\} = d^-_G(v_i)$。
      • 握手定理：$\displaystyle\sum_{i=1}^n\sum_{j=1}^m 1\{m_{ij}=1\} = \displaystyle\sum_{i=1}^n\sum_{j=-1}^m 1\{m_{ij}=-1\} = d^-_G(v_i) = m$
      • $e_i$ 与 $e_j$ 是平行边 $\iff$ $M(G)$ 中第 $i$ 列与第 $j$ 列相同。
  • 邻接矩阵