2016图论讨论班（七) 树与荫度
定义1：如果图G中任何两点都有一条路相连，则称图G是连 通图，否则称为是非连通图
定义 1：如果图 G 中任何两点都有一条路相连，则称图 G 是连 通图，否则称为是非连通图
定义2：如果图G是一个无圈的连通图，则称图G是一个树 2 3 5 6
定义 2：如果图 G 是一个无圈的连通图，则称图 G 是一个树
定理1：设图G是一个具有n个顶点的连通图，则其边数 e≥n-1 证明：不妨设G是简单图（没有重边，没有环）。若n=1,则e=0, 结论成立！若G至少有2个顶点，则取V,={v,},则存在一条边e,∈ [V,V](边的一个端点属于V,另外一个端点属于V,的补)。记evV2, 则再取V2{v,V2}。 若V2是V(G)的真子集，则存在e2∈[V2,V2]。记ev2v3,则再取 V={v,V2,V}。按照这个过程继续下去，最后必定在取到n-1条边 e1,e,…,e1后得到集合V。={V1,V2,V3,…,Vn}=V(G),从而该迭代操作 终止。因此，图G至少有-1条边
定理 1：设图 G 是一个具有 n 个顶点的连通图，则其边数 e≥n-1 证明：不妨设 G 是简单图（没有重边，没有环）。若 n=1，则 e=0， 结论成立！若 G 至少有 2 个顶点，则取 V1 ={v1},则存在一条边 e1∈ [V1,V1]（边的一个端点属于 V1，另外一个端点属于 V1的补）。记 e1 =v1v2, 则再取 V2={v1,v2}。 若 V2是 V(G)的真子集,则存在 e2∈[V2,V2]。记 e2=v2v3,则再取 V3 ={v1,v2,v3}。按照这个过程继续下去，最后必定在取到 n-1 条边 e1,e1,…,en-1后得到集合 Vn ={v1,v2,v3,…,vn}=V(G)，从而该迭代操作 终止。因此，图 G 至少有 n-1 条边
定理2：设图T是一个具有n个顶点的树，则其边数e=-1, 证明：对n作数学归纳：当n=1时，T=K,从而e=0,结论成立！ 假设当n=k时结论成立，下面考虑具有k+1个顶点的树T。 因为T不含有圈，并且连通，所以T的最小度恰好为1（为什 么？)。于是设T中有一条边uv,其中u的度数为1。 现将u从图T中删去，得到图T-u.容易看出，T-u必定无圈， 并且是连通的（为什么？)。也就是说，T-u是一个具有k+1-1=k个 顶点的树，从而由归纳假设，T-u有k-1条边。 因此，T有k-1+1=k条边！
定理 2：设图 T 是一个具有 n 个顶点的树，则其边数 e=n-1. 证明：对 n 作数学归纳：当 n=1 时，T=K1，从而 e=0，结论成立！ 假设当 n=k 时结论成立，下面考虑具有 k+1 个顶点的树 T。 因为 T 不含有圈，并且连通，所以 T 的最小度恰好为 1（为什 么?）。于是设 T 中有一条边 uv，其中 u 的度数为 1。 现将 u 从图 T 中删去，得到图 T-u.容易看出，T-u 必定无圈， 并且是连通的（为什么？）。也就是说，T-u 是一个具有 k+1-1=k 个 顶点的树，从而由归纳假设，T-u 有 k-1 条边。 因此，T 有 k-1+1=k 条边！
定理1：设图G是一个具有n个顶点的连通图，则其边数 e≥n-1 推论1：如果图G是一个具有n个顶点的连通图，并且其边数 e=n1,则图G不含圈，即G是一个树. 证明：（反证法）如果图G含有一个圈，则任意删去圈上的一条边， 图依然连通（为什么？)。但是该图有n个顶点，n-1-1=n-2条边， 与定理1矛盾！
定理 1：设图 G 是一个具有 n 个顶点的连通图，则其边数 e≥n-1 推论 1：如果图 G 是一个具有 n 个顶点的连通图，并且其边数 e=n-1，则图 G 不含圈，即 G 是一个树. 证明：（反证法）如果图 G 含有一个圈，则任意删去圈上的一条边， 图依然连通（为什么？）。但是该图有 n 个顶点，n-1-1=n-2 条边， 与定理 1 矛盾！
定理2：设图T是一个具有n个顶点的树，则其边数e=-1, 推论2：如果图G是一个具有n个顶点的无圈图，并且其边数 e=n-1,则图G连通，即G是一个树. 证明：（反证法）如果图G不连通，则不妨设G有两个连通分支G 与G2,它们都是树。设G,与G2分别有n与n2个顶点，根据定理2， G,与G2分别有n,-1与n2-1条边。因此，图G有n,+n=n个顶点， n,-1+n2-1=n-2条边，与已知条件矛盾！
定理 2：设图 T 是一个具有 n 个顶点的树，则其边数 e=n-1. 推论 2：如果图 G 是一个具有 n 个顶点的无圈图，并且其边数 e=n-1，则图 G 连通，即 G 是一个树. 证明：（反证法）如果图 G 不连通，则不妨设 G 有两个连通分支 G1 与 G2，它们都是树。设 G1与 G2分别有 n1与 n2个顶点，根据定理 2， G1 与 G2 分别有 n1-1 与 n2-1 条边。因此，图 G 有 n1+n2 =n 个顶点， n1-1+n2-1=n-2 条边，与已知条件矛盾！
因此，下列三个结论等价！ (1) 图T连通且无圈（图T是树）； (2) 图T连通，且e(T)=v(T)-1; (3)图T无圈，且e(T)=v(T)-1
因此，下列三个结论等价！ (1) 图 T 连通且无圈（图 T 是树）； (2) 图 T 连通，且 e(T)=v(T)-1; (3) 图 T 无圈，且 e(T)=v(T)-1
定义3：因为树是无圈连通图，其最小度必定等于1，即其包含一个 度数恰好为1的点，我们称这个点为树的叶子。 定理3：设图T是树，则T至少有2个叶子 证明：（反证法）如果T有n个顶点，其中只有一个叶子，则T 中有一个顶点的度数为1，其余顶点的度数至少为2.因此，根据定 理2，得到： 2n-2=2(n-1)=2e=∑d(m)≥1+2(n-1)=2n-1 vEV(G) 矛盾！
定义 3：因为树是无圈连通图，其最小度必定等于 1，即其包含一个 度数恰好为 1 的点，我们称这个点为树的叶子。 定理 3：设图 T 是树，则 T 至少有 2 个叶子. 证明：（反证法）如果 T 有 n 个顶点，其中只有一个叶子，则 T 中有一个顶点的度数为 1，其余顶点的度数至少为 2.因此，根据定 理 2，得到： 矛盾！ ( ) ( ) ( ) ( ) v V G 2n 2 2 n 1 2e d v 1 2 n 1 2n 1
定义4：如果图G的每个连通分支都是树，则称G为森林 定义4'：如果图G不含圈，则称G为森林 上述两个定义等价！ 具有n个顶点的森林 n=1,2,3,4,5,6
定义 4：如果图 G 的每个连通分支都是树，则称 G 为森林. 定义 4’ ：如果图 G 不含圈，则称 G 为森林. 具有 n 个顶点的森林 n=1,2,3,4,5,6 上述两个定义等价！