四色定理吧 关注:90贴子:1,234

自由度浅论

只看楼主收藏回复

自由度是着色时需要考虑的一个关键问题,下面将会详细说到。


回复
1楼2011-12-25 10:07

    对于此图来说,单从“颜色不定性”以及控制着色的数量是不能完全使此图的演变图实现4着色的。因此,必须从另外的角度来对此图进行分析,那就是将要谈到的“着色自由度”问题。


    回复
    2楼2011-12-25 10:11
      为了说得更具体一点,这里先给出一个此图的演变图:


      回复
      3楼2011-12-25 10:15
        对于这个演变图来讲,如果按照“颜色不定性”的顺序进行着色,则必须先使“2楼”的图进行3着色,否则演变图是无法完成4着色的。


        回复
        4楼2011-12-25 10:22
          那么,什么是“着色自由度”呢,这里可以从“2楼”的实例图说起。

          在未着色前,ABCDEF的着色自由度相同,拿A点来讲,与A相邻的有BCD,而BCD都是未着色的,这时我们就认为A点的自由度为3。


          回复
          5楼2011-12-25 10:28
            一旦BCD中有一个点,如B点进行了着色,那么,此时我们则认为A点的自由度为2.


            回复
            6楼2011-12-25 10:29
              当然,也可以认为这里所说的“自由度”就是“颜色不定性”的增减问题。也就是说,在着色过程中,颜色不定性是有所变化的!


              回复
              7楼2011-12-25 10:37
                认识到了颜色不定性的变化问题,下面我们来对2楼中的图进行着色,先给出2楼的图:

                首先,我们知道ABCDEF的颜色不定性相同。着色顺序为ABCDEF(只是其中的一种),于是任选一个着上第一种颜色。
                如A着1色。
                此时,与A相邻的BCD其颜色不定性会减少,而EF的颜色不定性保持不变。


                回复
                8楼2011-12-25 15:58
                  于是着色顺序变为:EFBCD(只是其中的一种)。此时需要对E进行着色。E的着色按照域着色法,应该着上1色,即与A相同。


                  回复
                  9楼2011-12-25 16:01
                    此时BDF的颜色不定性会减少。可以由以下方式进行计算:
                    A 3,清零
                    B 3,-1,-1
                    C 3,-1,
                    D 3,-1,-1
                    E 3,清零
                    F 3,-1


                    回复
                    10楼2011-12-25 16:09
                      A,E着色之后,可以看出C、F的颜色不定性最低(当然这里的最低实际上就是数值最大,必须注意!)
                      那么此时的着色顺序变为:CFBD(只是其中的一种)


                      回复
                      11楼2011-12-25 16:17
                        此时在C、F中选一个进行着色,如C,按照域着色法,C着2色。
                        对C着色后,颜色不定性变为:
                        A 3,清零
                        B 3,-1,-1,-1
                        C 3,-1,清零
                        D 3,-1,-1
                        E 3,清零
                        F 3,-1,-1


                        回复
                        12楼2011-12-25 16:37
                          此时的着色顺序为DFB(只是其中的一种),选D进行着色,按照域着色法,D着2色。
                          此时的颜色不定性变为:
                          A 3,清零
                          B 3,-1,-1,-1
                          C 3,-1,清零
                          D 3,-1,-1,清零
                          E 3,清零
                          F 3,-1,-1,-1


                          回复
                          13楼2011-12-25 16:42
                            最后在BF中选择着色,如B着3色,F着3色。


                            回复
                            14楼2011-12-25 16:43
                              当然,上面的最后着色顺序实际上是:AECDBF。另外需要说的是,对于已着色块面,可能用“清零”二字不妥,可以用“已着色”三字来代替。
                              如13楼的可以写成:
                              A 3,已着** 3,-1,-1,-1
                              C 3,-1,已着色
                              D 3,-1,-1,已着色
                              E 3,已着色
                              F 3,-1,-1,-1


                              回复
                              15楼2011-12-25 16:49
                                当然,上面的最后着色顺序实际上是:AECDBF。另外需要说的是,对于已着色块面,可能用“清零”二字不妥,可以用“已着色”三字来代替。
                                如13楼的可以写成:
                                A 3,已着** 3,-1,-1,-1。
                                C 3,-1,已着色。
                                D 3,-1,-1,已着色。
                                E 3,已着色。
                                F 3,-1,-1,-1。



                                回复
                                16楼2011-12-25 16:51
                                  当然,上面的最后着色顺序实际上是:AECDBF。另外需要说的是,对于已着色块面,可能用“清零”二字不妥,可以用“完”三字来代替,表示的是“已着色”。
                                  如13楼的可以写成:
                                  A 3,完。
                                  B 3,-1,-1,-1。
                                  C 3,-1,完。
                                  D 3,-1,-1,完。
                                  E 3,完。
                                  F 3,-1,-1,-1。



                                  回复
                                  17楼2011-12-25 16:53
                                    晕倒,“完”是一个字,不是三个字。


                                    回复
                                    18楼2011-12-25 16:54
                                      注意,这里“与A相邻的BCD其颜色不定性会减少”是错的,应该是“增加”而不是“减少”,在其他楼层里都出现了类似的错误,就不一一指出了。


                                      回复
                                      19楼2011-12-25 17:02
                                        上面的最后着色效果图为:


                                        回复
                                        20楼2012-01-01 08:43
                                          接下来将对颜色不定性的着色顺序进行一些细分,使某些块面的着色有先后顺序。


                                          回复
                                          21楼2012-01-01 08:45
                                            另外还将对下面这个“简单”图的颜色定位问题进行说明:

                                            由于按照“着色顺序+着色原则”还不能对这个简单图进行“最少颜色着色”,因此,着色时的定位选择就尤为重要。


                                            回复
                                            22楼2012-01-01 09:05
                                              可能在"直线"上少画了点,使得“着色顺序+着色原则”可以对这个图进行最少颜色,因此可以多加几个点,这样就能说明问题了。


                                              回复
                                              23楼2012-01-01 09:19
                                                在对这个简单图的着色中可以发现一个问题,要使颜色最少,还得考虑中间间隔的块面数的奇偶问题。


                                                回复
                                                24楼2012-01-01 09:20
                                                  也就是说,必须定位选择块面(点)进行着色,这样才能只用4色就行了。


                                                  回复
                                                  25楼2012-01-01 10:25
                                                    下面这个图反映了前面讲的“着色顺序+着色原则”还不能对所有的图进行“最少颜色着色”:

                                                    从着色顺序来讲,A和D的颜色不定性最大,因此A和D先着色,这里A和D都着为颜色1.
                                                    这时会发现,这个图中,A和D之间的所有“相邻关系路径”都是偶数,而没有奇数,所以此时的着色会使这个图的最终着色数为3色,而不是2色。这也就是说,“着色顺序+着色原则”将会使某些图不能成为“最少着色”。


                                                    回复
                                                    26楼2012-01-01 14:20
                                                      所以,我现在认为,着色法首先要优先照顾这种情况,当然如何照顾这种情况就需要“整合”了。


                                                      回复
                                                      27楼2012-01-01 14:54
                                                        接下来将会讲解一种“新的”着色法,这种着色法将首先考虑奇偶问题。


                                                        回复
                                                        28楼2012-01-01 15:04
                                                          在下面这个图中,奇点和偶点同时存在,这样的图称之为“奇偶混合图”,下面这个图的着色数最少为3色:



                                                          回复
                                                          29楼2012-01-03 09:27
                                                            由于奇偶定色的存在,使得我们在着色时必须同时考虑奇偶定色问题。


                                                            回复
                                                            30楼2012-01-03 10:10

                                                              扫二维码下载贴吧客户端

                                                              下载贴吧APP
                                                              看高清直播、视频!