作业帮 > 数学 > 作业

证明题 当且仅当连通图的每条边均为割边时,该连通图才是一棵树

来源:学生作业帮 编辑:拍题作业网作业帮 分类:数学作业 时间:2024/04/28 20:36:21
证明题 当且仅当连通图的每条边均为割边时,该连通图才是一棵树
当连通图的每条边均为割边时,显然没有回路(圈),因为倘若有回路的话去掉回路上的一条边仍能保持连通,也就是说回路上的边都不是割边.所以此连通图为树.
当连通图为树时,因为没有回路,去掉任何一条边都会造成不连通,所以当然每条边是割边.
以上是证明概要.要看仔细的证明,随便找本好的教科书都有.比如耿素云的书应该会有的.