环形染色问题(CSP初赛数学) | 您所在的位置:网站首页 › 环形排列公式怎么理解 › 环形染色问题(CSP初赛数学) |
本文转载自知乎 环形染色问题 原作者: 知乎 雨浥星辰 本文改动:将原文中的公式图片使用LaTeX重制 如图所示,一个圆环被分成 块,用 种不同颜色给每一块染色,要求相邻两块的颜色不相同。此类问题称之为环形染色问题。 环形染色问题可以分为两种,一类是圆环中心区域要染色,一类是圆环中心区域不染色。中心区域染色问题在给中心涂色之后,剩余部分即为中心区域不染色的问题,本文重点讲解中心区域不染色问题。 本文先针对m=4、m=5以分类与分步的做法解决,而后给出此类问题的通解。 n=4,m=4,中心区域不染色如图,环形区域被分成4块,用4种不同的颜色给这4块区域染色,要求相邻区域颜色不同。 解: 我们先给四块区域标注为A、B、C、D。先给A染色,则有4种颜色,而后B有三种,C也是有三种,但是D则需要分类来讨论。因为D与A、C都相邻,且A、C都已经涂好颜色,则A、C若同色,则D有三种颜色可选,A、C不同色,则D只有两种颜色可以选择,如下图所示 则共有 种染色方式; m=5,n=4,中心区域不染色如图,环形区域被分成5块,用4种不同的颜色给这5块区域染色,要求相邻区域颜色不同。 解: 同上,给五块区域标注为A、B、C、D、E。依旧是按顺序给5块区域染色。则在考虑A、D同色问题时,需考虑到AC是否同色。若A、C同色,则则A、D必定不同色。只有A、C不同色,才有可能出现A、D同色。 因此有以下分类: 1.AC同色:则A、D必定不同色,则五块区域依次有4、3、1、3、2种涂法,共有 种染色方式 。 2.AC不同色: (1) A、D同色:则五块区域依次有4、3、2、1、3种涂法,共有 种染色方式。 (2)A、D不同色,则五块区域一次有4、3、2、2、2种涂法,共有 种染色方式。 合计共有72+72+96=240种染色方式。 任意 m≥2、n≥2记当有m块区域时,染色方法有 种;则当m取1、2、3、4、……时,分别有 、、、……种染色方式。 首先考虑直线型染色:如下图所示,有m块区域,n种颜色,要求相邻区域不同色。 则除了第一块有n种涂法,其余各块都是n-1种。则共有 种染色方式。 现在把直线型的两端对接,拼成一个环形。 当两端颜色相同时,首尾对接则会出现有两块相邻区域颜色相同。其余相邻区域颜色则均不同。此时若把相邻颜色相同的区域合并为一个区域,则此时的环形有m-1块区域,任意相邻区域颜色均不相同,对应 种染色方式 当两端颜色不同时,首尾对接,则任意相邻区域颜色均不相同,此时的环形有m块区域,对应 种染色方式。 因此有 ——① 由此公式,对于没有学习过数列的同学,可以求出 之后,依次递推求出所需 而对于学过数列的同学,我们可以求出 的通项公式。 对①式稍作变形,有 移项可得: (1) 即 ,考虑 ,与之矛盾,故不合题意,舍去; (2) 令 ,则有 ,为等比数列 则 代入 有 代入 有 验证时刻: 1:代入m=4,n=4,有 2:代入m=5,n=4,有 中心区域染色圆环有m块区域,再加上中心区域共有m+1块区域;有n+1种颜色 由于中心区域与外环所有区域均相邻,则先涂中心区域,有n+1种涂色方法; 此时余下m块区域与n种颜色,即为中心不染色时m块区域和n种颜色的环形染色问题,代入上述公式, 共有 种。 合计共有 种染色方法。 |
CopyRight 2018-2019 实验室设备网 版权所有 |