图论与组合 / 树 / 定义

迁移来源

旧站标题：定义

新站标题：图论与组合 / 树 / 定义

旧站路径：/math/课程/图论与组合/chapters/树/定义/

旧页面 ID：344

定义 #

definition

无环的 (acyclic).

森林 (forest): 无环图.

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

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

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

tip

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

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

tip

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

tip

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

tip

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

tip

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

note

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

definition

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

tip

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

definition

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

tip

树的中心最多两个.

note

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