离散数学课件：第七章树的等价定义的证明

1、给定无向图给定无向图T, 以下关于树的定义是等价的：以下关于树的定义是等价的：(1)无回路的连通图无回路的连通图.(2)无回路且无回路且e=v-1, 其中其中e是边数，是边数，v是结点数是结点数.(3)连通且连通且e=v-1.(4)无回路，但增加任一新边，得到且仅得到一个无回路，但增加任一新边，得到且仅得到一个回路回路.(5)连通，但删去任一边后便不连通连通，但删去任一边后便不连通.(6)每一对结点之间有且仅有一条路每一对结点之间有且仅有一条路.证明思路证明思路(1)(3) (4) (5) (6) (2) 证证： (1)无回路的连通图无回路的连通图.(2)无回路且无回路且e=v-1. 用数学归

2、纳法证明，对结点数作归纳：用数学归纳法证明，对结点数作归纳： 当当v=1时，时，假设假设v=k时命题成立时命题成立,因图因图T连通而无回路连通而无回路,e=0, , 所以所以e=v-1成立成立. .若不然，则各点皆连通且度数大于等于若不然，则各点皆连通且度数大于等于2, 当当v=k+1时时,所以至少有一个度数为所以至少有一个度数为1的结点的结点u.在在T中删去中删去u及其关联边，及其关联边， 从某结点从某结点ui出发，可达另一结点出发，可达另一结点wi, 再继续，可经由一些结点后返再继续，可经由一些结点后返回结点回结点ui, 这样就产生了回路，这样就产生了回路，得得k个结点的连通子图个结点的连

3、通子图T,e=v-1, 设设T的结点数和边数分别为的结点数和边数分别为v和和e,则则即即整理得整理得e=v-1.e-1=(v-1)-1, 与已知条件矛盾与已知条件矛盾. (2)无回路且无回路且e=v-1. (3)连通且连通且e=v-1.证证： （反证法）（反证法）e1+e2+ek这与条件这与条件e=v-1矛盾矛盾.ei=vi-1,假设假设T不连通，有不连通，有k个连通分支个连通分支T1, T2,Tk(k 2),设设Ti的结点数和边数分别为的结点数和边数分别为 vi,ei, i=1,2,k, 因每因每个连通分支是无回路连通图，由个连通分支是无回路连通图，由(1)(2)可得可得所以所以 e= (v

4、1-1)+ (v2-1)+ (vk-1) =v-k. (3)连通且连通且e=v-1.(4)无回路，但增加任一新边，得到且仅得到一无回路，但增加任一新边，得到且仅得到一个回路个回路.证证：a)证明证明T无回路，对结点数作归纳：无回路，对结点数作归纳： 因因T连通且连通且e=v-1，设结点数为设结点数为v=k时无回路，时无回路， 当当v=k+1时，时，e=v-1=0, 故当故当v=1时，时，无回路无回路.因因T连通，故所有结点连通，故所有结点u有有deg(u) 1. 因因e=v-1, 故至少故至少有一个结点有一个结点u0, 使使deg(u0)=1. 若不然，则所有结点若不然，则所有结点u有有deg

5、(u) 2, 从而从而2e 2v, 即即e v, 与假设与假设e=v-1矛盾矛盾. 删去删去u及其关联边得及其关联边得k个结点的连通子图个结点的连通子图T, 由归纳由归纳假设，假设，T无回路无回路. 再加入再加入u及关联边得图及关联边得图T, 则则T也无回路也无回路. 在连通图在连通图T中，任取结点中，任取结点vi, vj,增加新边增加新边 (vi, vj), (3)连通且连通且e=v-1.(4)无回路，但增加任一新边，得到且仅得到一无回路，但增加任一新边，得到且仅得到一个回路个回路.证证：因为因为T连通，连通，所以图所以图T中中vi, vj之间本已存在一条路，之间本已存在一条路， 故增加故增

6、加新边后得一回路，新边后得一回路，且该回路是唯一的且该回路是唯一的. 否则否则, 若删去此新边若删去此新边, 路径中必有回路路径中必有回路, 与与a)矛盾矛盾.b)证明在证明在T中增加任一新边，得到且仅得到一个回路中增加任一新边，得到且仅得到一个回路. (4)无回路，但增加任一新边，得到且仅得到一个无回路，但增加任一新边，得到且仅得到一个回路回路.(5)连通，但删去任一边后便不连通连通，但删去任一边后便不连通.证证：(a) 证明图证明图T是连通的（反证法）：是连通的（反证法）：(b)证明删去任一边后图证明删去任一边后图T便不连通：便不连通：假设图假设图T不连通，不连通， 则存在结点则存在结点v

7、i, vj, 在在vi与与 vj之间没有路之间没有路. 显然若增加边显然若增加边不产生回路，不产生回路，与已知条件矛盾与已知条件矛盾.因图因图T无回路，无回路， 故删去任一边后便不连通故删去任一边后便不连通. (5)连通，但删去任一边后便不连通连通，但删去任一边后便不连通. (6)每一对结点之间有且仅有一条路每一对结点之间有且仅有一条路.证证： (a)证明每一对结点间有一条路证明每一对结点间有一条路: (b)证明每一对结点间仅有一条路（反证法）：证明每一对结点间仅有一条路（反证法）：因为图因为图T连通，连通， 故每一对结点间有一条路故每一对结点间有一条路.假设存在两结点，在它们之间有多于一条的路，假设存在两结点，在它们之间有多于一条的路，则则T中必有回路，中必有回路， 删去该回路上任一边，图仍连通，删去该回路上任一边，图仍连通，与已知条件矛盾与已知条件矛盾. (6)每一对结点之间有且仅有一条路每一对结点之间有且仅有一条路.(1)无回路的连通图无回路的连通图.证证：(b)证明图证明图T无回路