作业帮 > 数学 > 作业

怎么证明一棵无向树是二部图?

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/05/23 22:51:36
怎么证明一棵无向树是二部图?
要具体证明啊,
无向树先找一个根结点(根顶点),然后与根节点距离为偶数的结点归为一个点集合,与根节点距离为奇数的结点归为另外一个点集合,那么这两个点集合就构成了图中所有顶点集合的划分,而且无向树中所有的边两端的顶点分别属于这两个集合,所以无向树是一个二部图.