05-02 23:35 发布于广东
关注
2025.牛客五一集训H
我们令，二进制表示中 1 的个数为偶数的顶点的属性为 ‘0’，反之为 ‘1’，便可以实现：
对于任意一个顶点 A ，与其相邻的顶点必与其属性不同
证明如下：
假设 A顶点、B顶点 相邻，且 A、B 的属性相同
不妨令，A 二进制表示中 1 的个数为 x ，B 二进制表示中 1 的个数为 y
那么 x 和 y 的奇偶性，必不同，因此 A、B的属性也必不同，这与假设矛盾
所以可证：此时，对于任意一个顶点 A ，与其相邻的顶点必与其属性不同
对于任意一个顶点 A ，与其相邻的顶点必与其属性不同
证明如下：
假设 A顶点、B顶点 相邻，且 A、B 的属性相同
不妨令，A 二进制表示中 1 的个数为 x ，B 二进制表示中 1 的个数为 y
那么 x 和 y 的奇偶性，必不同，因此 A、B的属性也必不同，这与假设矛盾
所以可证：此时，对于任意一个顶点 A ，与其相邻的顶点必与其属性不同
全部评论
相关推荐
点赞 评论 收藏
分享
睿联技术公司福利 32人发布 点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
04-16 20:57
点赞 评论 收藏
分享
韶音科技开奖40人在聊 点赞 评论 收藏
分享