《离散数学课件：第七章树的等价定义的证明》由会员分享，可在线阅读，更多相关《离散数学课件：第七章树的等价定义的证明（9页珍藏版）》请在金锄头文库上搜索。
1、 树树 的的 等等 价价 定定 义义给定无向图给定无向图T, 以下关于树的定义是等价的：以下关于树的定义是等价的：(1)无回路的连通图无回路的连通图.(2)无回路且无回路且e=v-1, 其中其中e是边数，是边数，v是结点数是结点数.(3)连通且连通且e=v-1.(4)无回路，但增加任一新边，得到且仅得到一个无回路，但增加任一新边，得到且仅得到一个回路回路.(5)连通，但删去任一边后便不连通连通，但删去任一边后便不连通.(6)每一对结点之间有且仅有一条路每一对结点之间有且仅有一条路.证明思路证明思路(1)(3) (4) (5) (6) (2) 证证： (1)无回路的连通图无回路的连通图.(2)无
2、回路且无回路且e=v-1. 用数学归纳法证明，对结点数作归纳：用数学归纳法证明，对结点数作归纳： 当当v=1时，时，假假设v=k时命命题成立成立,因因图T连通而无回路通而无回路,e=0, ,所以所以e=v-1成立成立. .若不然，若不然，则各点皆各点皆连通且度数大于等于通且度数大于等于2, 当当v=k+1时,所以至少有一个度数所以至少有一个度数为1的的结点点u.在在T中中删去去u及其关及其关联边， 从某从某结点点ui出出发，可达另一，可达另一结点点wi, 再再继续，可，可经由一些由一些结点后返点后返回回结点点ui, 这样就就产生了回路，生了回路，得得k个个结点的点的连通子通子图T,e=v-1,
3、 设设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= (v1-1)+ (v2-1)+ (v
4、k-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(u) 2, 从而从而2e 2v
5、, 即即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不连通，不连通， 则存在结点则存在结点vi, vj, 在在vi与与 vj
7、之间没有路之间没有路. 显然若增加边显然若增加边不产生回路，不产生回路，与已知条件矛盾与已知条件矛盾.因图因图T无回路，无回路，故删去任一边后便不连通故删去任一边后便不连通. (5)连通，但删去任一边后便不连通连通，但删去任一边后便不连通. (6)每一对结点之间有且仅有一条路每一对结点之间有且仅有一条路.证证： (a)证明每一对结点间有一条路证明每一对结点间有一条路: (b)证明每一对结点间仅有一条路（反证法）：证明每一对结点间仅有一条路（反证法）：因为图因为图T连通，连通， 故每一对结点间有一条路故每一对结点间有一条路.假设存在两结点，在它们之间有多于一条的路，假设存在两结点，在它们之间有多于一条的路，则则T中必有回路，中必有回路， 删去该回路上任一边，图仍连通，删去该回路上任一边，图仍连通，与已知条件矛盾与已知条件矛盾. (6)每一对结点之间有且仅有一条路每一对结点之间有且仅有一条路.(1)无回路的连通图无回路的连通图.证证：(b)证明图证明图T无回路：无回路：因每一对结点间有一条路，因每一对结点间有一条路，(a)证明图证明图T连通：连通：故图故图T连通连通.假设图假设图T存在一条回路，存在一条回路， 则回路上任两点间有两条路，则回路上任两点间有两条路，与已知条件矛盾与已知条件矛盾.
