作业帮 > 数学 > 作业

证明:非平凡图的连通图G是树的充分必要条件是G的每条边是桥

来源:学生作业帮 编辑:大师作文网作业帮 分类:数学作业 时间:2024/11/11 15:04:14
证明:非平凡图的连通图G是树的充分必要条件是G的每条边是桥
证明:非平凡图的连通图G是树的充分必要条件是G的每条边是桥
先证明必要条件:如果G是树,那么G的每条边是桥
任何一棵树满足边数=顶数-1
对于G的任意一条边,去掉它之后,边数=顶数-2,因此它不再是树,又因为原来的图没有圈,因此得到的图也没有圈,因此它不连通.所以这条边是桥,可知树的任意一条边都是桥
再证明充分条件:如果G的每条边是桥,那么G是树
假设G不是树,那么它有圈或不连通:如果有圈,圈上任意一边都不是桥;如果不连通,也不满足“每条边都是桥”的条件,所以G是树.
可能有些地方有错误,欢迎追问