作业帮 > 数学 > 作业

证明:连通的无圈图称为树,图T是树当且仅当对T的任意两个顶点xy之间有恰有一条路连接xy

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/07/13 19:56:27
证明:连通的无圈图称为树,图T是树当且仅当对T的任意两个顶点xy之间有恰有一条路连接xy
用反证法证明:
设T是一个树,则T是连通的.因此T的每2个顶点之间都会连接一条路.假设T的某2个顶点之间连接了2条不同的路,则可由这2条路的全部或者部分边产生一个圈,导致矛盾.
现在证明充分性:设T的每2个不同顶点之间都被唯一的路连接.显然,T是连通的.建设T含有一个圈C.x,y是C的2个不同的顶点,因此C就确定了2条不同的x-y路,导致矛盾.所以T是无圈的,从而T是树.
证毕
最后提醒下楼主 这是图论 不是离散数学