定义
📝定义 3.2.1
无环的 (acyclic).
森林 (forest): 无环图.
树 (tree): 连通的无环图.
生成子图 (spanning subgraph): 点集为 $V(G)$ 的子图.
生成树 (spanning tree): 形态为树的生成子图.
💡引理 3.2.2
任意至少有两个节点的树至少含有两个叶子.
从 $n$ 个点树中删除一个叶子及其边可以得到一个 $n-1$ 个点的树.
💡定理 3.2.3
对于
$n$ 个点的图, 下述命题等价.
- A 连通且无环.
- B 连通且有
$n-1$ 条边.
- C 无环且有
$n-1$ 条边.
- D 任意两点之间有且仅有一条路径.
💡命题 3.2.4
若 $T,T'$ 是连通图 $G$ 的两棵生成树, 对任意 $e\in E(T)-E(T')$, 存在边 $e'\in E(T')-E(T)$ 使得 $T-e+e'$ 仍是生成树.
💡命题 3.2.5
若 $T,T'$ 是连通图 $G$ 的两棵生成树, 对任意 $e\in E(T)-E(T')$, 存在边 $e'\in E(T')-E(T)$ 使得 $T+e-e'$ 仍是生成树.
💡命题 3.2.6
对于任意 $k$ 条边的树, 和任意满足 $\delta(G)\geqslant k$ 的简单图 $G$. 一定存在一个 $G$ 的子图 $H$, 有 $H\cong T$.
📝证明
对 $k$ 归纳, 考虑任意删除一个叶子之后再将其连上.
📝定义 3.2.7
距离 (distance): 设存在
$u,v$-path, 则定义
$d_G(u,v)$ 为最短的
$u,v$-path 的长度. 若不存在
$u,v$-path, 则定义
$d(u,v)=\infty$.
直径 (diameter): $\max\limits_{u,v\in V(G)} d(u,v)$.
离心率 (eccentricity): $\varepsilon(u)=\max\limits_{v\in V(G)}d(u,v)$, 即最远点距离.
半径 (radius): $\text{rad} G=\min\limits_{u\in V(G)}\varepsilon(u)$.
💡定理 3.2.8
对于简单图 $G$, 若 $\text{diam} G\geqslant 3$, 则有 $\overline{G}\leqslant 3$.
📝定义 3.2.9
中心 (center): 离心率最小的顶点.
💡定理 3.2.10
树的中心最多两个.
📝证明
数学归纳法, 考虑删除所有叶子后的树中心维持不变.