(3)→(4):在T是连通图,且e=n-的条件下, 证明T是无回路图且在T的任两个不相邻 的顶点之间添加一边,恰得到一条回路。 1)首先证明T是无回路的。 对顶点数n采用归纳法, n=2时e=1,且连通,只能是下图 显然T是无回路的
(3)→(4):在T是连通图,且e=n-1的条件下, 证明T是无回路图,且在T的任两个不相邻 的顶点之间添加一边,恰得到一条回路。 1)首先证明T是无回路的。 对顶点数n采用归纳法, n=2时e=1,且连通, 只能是下图 显然T是无回路的
假设n=k-1时结论成立,考察n=k时,由于T是连通 的,所以每个顶点度数≥(e=k-1)。可以证明至少 存在一个顶点u,使d(u)=1。Why?
假设n=k-1时结论成立,考察n=k时,由于T是连通 的,所以,每个顶点度数1(e=k-1)。可以证明,至少 存在一个顶点u,使 d(u)=1。Why?
2)再证明如果在连通图T的任两个不相邻 顶点之间添加一边,记为{vp,则该边与T 中从v到v的一条路 iyvi1…, Vissr 构成一条回路vpv"…,vs,vv) 若这条回路不唯一,由于T无回路,而 TU{,v}得到了回路,因此另一条回路C 也含有边{v,}
2)再证明如果在连通图T的任两个不相邻 顶点之间添加一边,记为{vi ,vj },则该边与T 中从vi到vj的一条路 (vi ,vi1 ,…, vis,vj ) 构成一条回路(vi ,vi1 ,…, vis,vj ,vi )。 若这条回路不唯一，由于T无回路，而 T∪{vi ,vj }得到了回路，因此另一条回路C' 也含有边{vi ,vj }
(4)→(5):在T是无回路图且在T的任两个 不相邻的顶点之间添加一边,恰得到一条 回路的条件下证明T是连通图,但删去任 一边后,便不连通。 若T不连通,则存在顶点v和v,在v与v之 间没有路。显然若加一边vv不会产 生回路,与假设矛盾。 又由于T无回路则删去任一边便不连通
(4)→(5): 在T是无回路图,且在T的任两个 不相邻的顶点之间添加一边,恰得到一条 回路的条件下证明T是连通图,但删去任 一边后,便不连通。 若T不连通, 则存在顶点vi和vj ,在vi与vj之 间没有路。显然,若加一边{vi ,vj },不会产 生回路,与假设矛盾。 又由于T无回路,则删去任一边,便不连通
(5)(6):在T是连通图但删去任一边后, 便不连通的条件下证明T的每一对不同的 顶点之间有唯一的一条路。 由于T是连通的任两点之间有一条路 如果某两个顶点之间多于一条路,则T中 必含有回路,Why?)删去该回路上任一边, 图仍连通与假设矛盾。 (6)→(1):在T的每一对不同的顶点之间有 唯一的一条路的条件下,证明T是无回路 的连通图。显然图是连通的。若有回路, 则回路上任两点之间有两条路,从而导致 矛盾
(5)→(6): 在T是连通图,但删去任一边后, 便不连通的条件下证明T的每一对不同的 顶点之间有唯一的一条路。 由于T是连通的,任两点之间有一条路。 如果某两个顶点之间多于一条路,则T中 必含有回路,(Why?) 删去该回路上任一边, 图仍连通,与假设矛盾。 (6)→(1): 在T的每一对不同的顶点之间有 唯一的一条路的条件下，证明T是无回路 的连通图。显然图是连通的。若有回路, 则回路上任两点之间有两条路, 从而导致 矛盾