“四色定理”在实际中有什么应用
2个回答
展开全部
四色定理是图的着色问题的一个结果。图的着色本质是给图中的顶点贴标签（labeling），但是要满足一定的条件。「色」只是一种标签。
四色定理的描述虽然提到了地图，但是地图绘制并不需要四色定理：他只要着色，不需要用最少的颜色。实际画地图时一般不用四种颜色。
着色问题的应用，主要排程和分配问题上。
比如我有几个任务，每个任务都需要一天。而我知道其中几样任务是冲突的，不能安排在同一天完成。现在我希望四天完成。这就是四色问题了：所用的图以任务为顶点，冲突的任务间连边，用日期做颜色，对图着色。
再比如我有一些员工，我希望把他们分成四个小组。但是我知道其中几个员工互相之间有矛盾，不能安排在同一组。那么这又是四色问题：所用的图以员工为顶点为，矛盾的员工间连边，用组做颜色，对图着色。
四色定理说：如果上面提到的图是平面图（有高效算法判定），那么可能四天完成／可能分成四组。
四色定理的描述虽然提到了地图，但是地图绘制并不需要四色定理：他只要着色，不需要用最少的颜色。实际画地图时一般不用四种颜色。
着色问题的应用，主要排程和分配问题上。
比如我有几个任务，每个任务都需要一天。而我知道其中几样任务是冲突的，不能安排在同一天完成。现在我希望四天完成。这就是四色问题了：所用的图以任务为顶点，冲突的任务间连边，用日期做颜色，对图着色。
再比如我有一些员工，我希望把他们分成四个小组。但是我知道其中几个员工互相之间有矛盾，不能安排在同一组。那么这又是四色问题：所用的图以员工为顶点为，矛盾的员工间连边，用组做颜色，对图着色。
四色定理说：如果上面提到的图是平面图（有高效算法判定），那么可能四天完成／可能分成四组。
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
