将凸五边形ABCDE的5条边和5条对角线染色,且满足任意有公共顶点的两条线段不同色,求颜色数目的最小值.

1个回答

  • 解题思路:由于顶点A是4条线段AB,AC,AD,AE的公共点,因此至少需要4种颜色,若只有4种颜色,不妨设为红、黄、蓝、绿,则每个顶点引出的4条线段的颜色包含红、黄、蓝、绿各一种,因此,红色的线段共有[5/2]条,矛盾.所以,至少需要5种颜色.

    由于顶点A是4条线段AB,AC,AD,AE的公共点,因此至少需要4种颜色.

    若只有4种颜色,不妨设为红、黄、蓝、绿,则每个顶点引出的4条线段的颜色包含红、黄、蓝、绿各一种,因此,红色的线段共有[5/2]条,矛盾.所以,至少需要5种颜色.

    下面的例子说明5种颜色可以将这10条线段染为满足条件的颜色.将AB,CE染为1号颜色;将BC,DA染为2号颜色;将CD,EB染为3号颜色;将DE,AC染为4号颜色;

    将EA,BD染为5号颜色,则任意有公共顶点的两条线段不同色.

    综上所述,颜色数目的最小值为5.

    点评:

    本题考点: 染色问题.

    考点点评: 本题主要考查染色问题的知识点,解答本题的关键是熟练掌握染色原理,此题难度不大,需要假设进行证明.