定义 | nan2inf.cn

定义

无环的 (acyclic).

森林 (forest): 无环图.

树 (tree): 连通的无环图.

生成子图 (spanning subgraph): 点集为 $V(G)$ 的子图.

生成树 (spanning tree): 形态为树的生成子图.

引理

任意至少有两个节点的树至少含有两个叶子.

从 $n$ 个点树中删除一个叶子及其边可以得到一个 $n-1$ 个点的树.

定理

对于 $n$ 个点的图, 下述命题等价.

命题

若 $T,T'$ 是连通图 $G$ 的两棵生成树, 对任意 $e\in E(T)-E(T')$ , 存在边 $e'\in E(T')-E(T)$ 使得 $T-e+e'$ 仍是生成树.

命题

若 $T,T'$ 是连通图 $G$ 的两棵生成树, 对任意 $e\in E(T)-E(T')$ , 存在边 $e'\in E(T')-E(T)$ 使得 $T+e-e'$ 仍是生成树.

命题

对于任意 $k$ 条边的树, 和任意满足 $\delta(G)\geqslant k$ 的简单图 $G$ . 一定存在一个 $G$ 的子图 $H$ , 有 $H\cong T$ .

证明

对 $k$ 归纳, 考虑任意删除一个叶子之后再将其连上.

定义

距离 (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)$ .

定理

对于简单图 $G$ , 若 $\text{diam} G\geqslant 3$ , 则有 $\overline{G}\leqslant 3$ .

定义

中心 (center): 离心率最小的顶点.

定理

树的中心最多两个.

证明

数学归纳法, 考虑删除所有叶子后的树中心维持不变.

定义