树

• 无向树
  • 定义
    • 无向树：连通无回路的无向图。
    • 平凡树：平凡图。
    • 森林：至少由两个树组成。
    • 树叶：度数为 $1$。
    • 分支结点：度数大于 $2$ 的结点。
  • 性质
    • 无向树 $T=\langle V,E\rangle$ 的等价定义：
      • $T$ 中任意结点之间存在唯一路径。
      • $T$ 中无回路且 $|E| = |V| - 1$。
      • $T$ 连通且 $|E| = |V| - 1$。
      • $T$ 连通且任何边都是桥。
      • $T$ 中无回路，在任意两个不同的顶点之间加一条边，得到唯一一个含新边的圈。
    • 如果 $T$ 是非平凡树，则 $T$ 有至少两个树叶。
• 生成树
  • 定义
    • 生成树：图的生成子图且是树。
    • 树枝：生成树中的边。
    • 弦：不在生成树中的边。
    • 余树：所有弦的集合的导出子图，记作 $\overline T$。
  • 性质
    • 余树不一定连通，可能含回路。
    • 连通图 $G$ 至少存在一个生成树 $T$。
      • $G$ 为 $n$ 阶 $m$ 条边的连通图，则 $m\ge n-1$。
      • $|E(\overline T)| = m - n + 1$。
      • $C$ 为 $G$ 中的圈，则 $C$ 与 $\overline T$ 有公共边。
  • 基本回路
    • $T$ 为无向连通图 $G$ 的生成树，$e'$ 为 $T$ 的弦：
      • $T\cup e'$ 中含有一个只有一个弦 $e'$ 且其他边都是树枝的圈。
      • 不同弦对应的圈不同。
    • 基本回路：生成树 $T$ 添加弦 $e'_r$ 后产生的圈，记作 $C_r$。
    • 基本回路系统：$G$ 所有弦的基本回路的集合 $\{C_1,C_2,\dots,C_{m-n+1}\}$。
    • 圈秩：弦的个数、基本回路系统的大小，记作 $\xi(G)=m-n+1$。
    • 基本回路系统与生成树的选取有关，圈秩则无关。
    • 任何简单回路都可以表示为若干基本回路的异或和。
  • 基本割集
    • $T$ 为无向连通图 $G$ 的生成树，$e$ 为 $T$ 的树枝：
      • 存在边割集分割 $e$ 的两个端点所在的子树 $T_1,T_2$。
      • 割集中除 $e$ 以外的边的端点分别在 $T_1,T_2$ 中。
    • 基本割集：上述 $e$ 对应的割集，记作 $S_i$。
    • 基本割集系统：所有树枝对应的基本割集的集合 $\{S_1,S_2,\dots,S_{n-1}\}$。
    • 割集秩：树枝的个数、基本割集系统的大小，记作 $\eta(G)=n-1$。