图论:证明树是二分图如题.

来源:学生作业帮助网 编辑:作业帮 时间:2024/11/14 22:17:29

图论:证明树是二分图如题.
图论:证明树是二分图
如题.

图论:证明树是二分图如题.
证明:
无向图G为二分图的充分必要条件是,G至少有两个顶点,且其所有回路的长度均为偶数.
而树中无回路,故树是二分图

很简单,从一个叶子顶点开始数,单号的放在一部分里,双号的放在另一部分里
也可以对图的顶点数用归纳法