yokobuttonの不定期で競技プログラミングをするブログ

不定期で解けた競技プログラミングコンテストの問題を載せています。

リスト彩色とリスト彩色予想②

2,リスト彩色予想

 リスト彩色予想

  任意の単純グラフGは、ch1(G)=χ1(G)である。

 (証明)

  1つ反例を示すことで、予想を否定する。

  完全グラフKpの位数が奇数の場合を考える。Kpのサイズqはp(p-1)/2である。

  完全グラフKpに対してχ1(Kp)=p(pが奇数)、p-1(pが偶数)であるので、予想が成り立つならば、ch1(Kp)=pである。

  グラフに許される色の数をm、各辺に許される色の数をkとすると、k=pである。

  m=k+1=p+1の場合を考える。

 

  p=1の場合、頂点v1があり、サイズは1(1-1)/2=0である。

 

  p=3の場合、頂点v2、v3を加えることを考える。増える辺はp(p-1)/2-(p-2)(p-3)/2=2p-3=6-3=3本である。この辺はv2、v3からv1への各1本とv2とv3を結ぶ1本である。e3,1=(v1、v2)、e3,2=(v1、v3)、e3,3=(v2、v3)とする。

   許される色の数はm=p+1=4、k=p=3である。

   それぞれの辺が許される色のリストをc3,jで表す。このとき、c3,1、c3,2、c3,3が①すべて同じ、②1つだけ違う、③3つとも違う、の3通りが考えられる。どの場合でも、それぞれの辺に互い異なる色を塗ることができるので、それをe3,1=0、e3,2=1、e3,3=2として本質的に問題ない。

 

  p=5の場合、頂点v4、v5を加えることを考える。増える辺の本数は2p-3=10-3=7本である。この7本はv4、v5からv1、v2、v3への各3本とv4とv5を結ぶ1本である。e5,1=(v1、v4)、e5,2=(v2、v4)、e5,3=(v3、v4)、e5,4=(v1、v5)、e5,5=(v2、v5)、e5,6=(v3、v5)

、e5,7=(v4、v5)とする。

   許される色の数はm=p+1=6、k=p=5である。

   それぞれの辺が許される色のリストをc5,jで表す。これら増える辺の最悪の場合を考える。

   e5,1について考える。

   e5,1の最悪の場合は、v1に接続する辺で確定している色(0、1)がc5,1に入っている場合である。他の3色は①P=3のときに使われた色が入っている、②p=3のときに使われた色が入っていない、の2通りに分けられる。今②の場合を考える。e5,1をP=3のときに使われていない色で塗り、それを色3として本質的に問題ない。

   e5,2について考える。

   e5,2の最悪の場合は、v2に接続する辺で確定している色(0、2)とv4に接続している辺で確定している色(3)がc5,2に入っている場合である。他の2色は①P=3のときに使われた色が入っている、②p=3のときに使われた色が入っていない、の2通りに分けられる。今②の場合を考える。e5,2をP=3のときに使われていない色で塗り、それを色4として本質的に問題ない。

   e5,3について考える。

   e5,3の最悪の場合は、v3に接続する辺で確定している色(1、2)とv4に接続している辺で確定している色(3、4)がc5,3に入っている場合である。他の1色は①P=3のときに使われた色が入っている、②p=3のときに使われた色が入っていない、の2通りに分けられる。今①の場合を考える。そうすると、e5,3は色0で塗られることになる。

--------------------------------------------------------------------------------------------------

   e5,4について考える。

   e5,4の最悪の場合は、v1に接続する辺で確定している色(0、1、3)がc5,4に入っている場合である。他の2色は①P=3のときに使われた色が入っている、②p=3のときに使われた色が入っていない、の2通りに分けられる。①の場合、色(2、4)、色(2、5)のどちらか、②の場合、色(4、5)である。

   今②の場合だったとして、色5をe5,4に塗るとする。

   

   e5,5について考える。

   e5,5の最悪の場合は、v2に接続する辺で確定している色(0、2、4)とv5に接続している辺で確定している色(5)がc5,5に入っている場合である。他の1色は①P=3のときに使われた色が入っている、②p=3のときに使われた色が入っていない、の2通りに分けられる。①の場合、色(1)で、②の場合、色(3)である。今、②の場合だったとして、色3をe5,5に塗る。

   

   e5,6について考える。

   e5,6の最悪の場合は、v3に接続している辺で確定している色(0、1、2)とv5に接続している辺で確定している色(3、5)がc5,6に入っている場合である。

   このとき、c5,6=(0、1、2、3、5)はもうすでに5色許されている。この許されている5色では彩色不可能である。

--------------------------------------------------------------------------------------------------

   e5,4に戻って、e5,4を色4で塗るとする。

   

   e5,5について考える。

   e5,5の最悪の場合は、v2に接続する辺で確定している色(0、2、4)とv5に接続している辺で確定している色(4)がc5,5に入っている場合である。他の2色は①P=3のときに使われた色が入っている、②p=3のときに使われた色が入っていない、の2通りに分けられる。①の場合(1、3)、(1、5)のどちらかであり、②の場合(3、5)である。

   今②の場合だったとして、色3をe5,5に塗る。

 

   e5,6について考える。

   e5,6の最悪の場合は、v3に接続している辺で確定している色(0、1、2)とv5に接続している辺で確定している色(3、4)がc5,6に入っている場合である。

   このとき、c5,6=(0、1、2、3、4)はもうすでに5色許されている。この許されている5色では彩色不可能である。

--------------------------------------------------------------------------------------------------

   e5,5に戻って、e5,5を色5で塗るとする。

 

   e5,6について考える。

   e5,6の最悪の場合は、v3に接続している辺で確定している色(0、1、2)とv5に接続している辺で確定している色(4、5)がc5,6に入っている場合である。

   このとき、c5,6=(0、1、2、4、5)はもうすでに5色許されている。この許されている5色では彩色不可能である。

--------------------------------------------------------------------------------------------------

   これで、完全グラフがp=5のときに5-リスト辺彩色可能ではないことが証明された。

   よって、リスト彩色予想は否定される。(証明終わり)

リスト彩色とリスト彩色予想①

(注意)この記事はディーステル「グラフ理論」の内容をお借りしている部分が多いです。

 

1、リスト彩色

 グラフGとその各頂点に対して、塗ることが許される色のリストが与えられている。このとき、そのリストから選んだ色を頂点に割り当てて、Gを彩色することをリスト頂点彩色という。すべての頂点にどんなk色のリストを与えても、Gがリストを用いた彩色を持つとき、Gはk-リスト頂点彩色可能、または、k-頂点選択可能であるという。Gがk-頂点選択可能であるような最小のkを、Gのリスト頂点染色数、または、頂点選択数と呼び、ch(G)で表す。

 同様に、辺に対するリスト辺彩色も定義できる。要素数がkのどんなリストを用いても、グラフGを辺彩色できる最小のkを、Gのリスト辺染色数ch1(G)とよぶ。線グラフをL(G)とすれば、ch1(G):=ch( L(G) )である。

 同様に、頂点と辺に対するリスト全彩色を定義できる。要素数がkのどんなリストを用いても、グラフGを全彩色できる最小のkを、Gのリスト全染色数ch2(G)と呼ぶ。全グラフをT(G)とすれば、ch2(G):=ch( T(G) )である。

 原理的に、与えられたグラフがk-選択可能であることを示すことは、k-彩色可能であることを示すことよりも難しい。なぜなら、k-彩色可能は、すべてのリストが(1、2、・・・、k)である場合とみなせるからである。従って、すべてのグラフGに対して、ch(G)≧χ(G)、ch1(G)≧χ1(G)、ch2(G)≧χ2(G)である。

17人で3つの話題

漫画「数学ゴールデン」の1巻に次のような問題が出てくる。それを解いてみた。

「17人それぞれが他の全員と互いに手紙のやりとりをしている。

 その手紙では3つの話題のみがやりとりされている。

 そして、同じ2人組の間でなされる話題は常に同じ1つのやりとりである。

 このとき、互いに同じ話題の手紙のやりとりをした3人組が存在することを証明せよ」

 (証明)

  3つの話題をA、B、Cとする。

  17人のうち1人をxとして、そのxと残りの16人との手紙のやりとりを考える。

  天井関数をceil()で表す。

  ceil(16/3)=6人以上のやりとりをする話題が1つは存在する。その話題をAとする。

  その6人以上の中の2人が話題Aで手紙をやりとりしていたら、xとその2人が求める3人組である。

  その6人以上の中での手紙のやりとりが話題Aではされていないとする。

  その6人以上の中の1人をyとして、そのyと残りの5人以上との手紙のやりとりを考える。

  ceil(5/2)=3人以上やりとりする話題が1つは存在する。その話題をBとする。

  その3人以上の中の2人が話題Bでやりとりしていたら、yとその2人が求める3人組である。

  その3人以上の中での手紙のやりとりが話題Bでされていないとする(もちろん話題Aでもない)。

  すると、その3人以上の中での手紙のやりとりは話題Cでのみされているので、任意の3人を選ぶと話題Cで手紙のやりとりをしている3人組となる。

  よって、必ず、互いに同じ話題の手紙のやりとりをした3人組が存在する。(証明終わり)

完全グラフと全彩色予想④

4,全彩色

  グラフGの全彩色とは、Gの隣接するどの2元、または接続するどの2元も異なる色を持つようなGの元(頂点と辺)に色を付けることである。k個の色を用いる全彩色をk-全彩色という。グラフGに対して、k-全彩色が存在するときGはk-全彩色可能であるという。グラフGがk-全彩色可能であるようなkの最小値をGの全染色数といい、χ2(G)で表す。

  グラフGの頂点彩色について、k-頂点彩色可能であるようなkの最小値をGの頂点染色数といい、χ(G)で表す。

 

  定理4・1

   χ2(Kp)=p(pが奇数のとき)、p+1(pが偶数のとき)

   (証明)

    完全グラフKp+1の線グラフをL(Kp+1)で表す。このとき、命題2・1より

     T(Kp)=L(Kp+1)

    であるから、

     χ2(G)=χ( T(G) )

    より、

     χ2(Kp)=χ( T(Kp) )=χ( L(Kp+1) )

    となる。一般に任意の単純グラフGに対して、χ1(G)=χ( L(G) )が成立するから、

     χ1(Kp+1)=χ( L(Kp+1) )

    である。定理3・1より、

     χ1(Kp+1)=p(pが奇数)、p+1(pが偶数)

    となるから、

     χ2(Kp)=p(pが奇数)、p+1(pが偶数)

    が得られる。(証明終わり)

 

  命題4・2

   完全グラフKpがk-全彩色可能ならば、それから辺をi本(0≦i≦p(p-1)/2)取り除いた単純グラフGiはk-全彩色可能である。

   (証明)

    (0)Kpから辺を0本取り除いたグラフG0は、Kpであり、k-全彩色可能である。

     このとき、2頂点の色と辺の色の辺の組み合わせ数はkC3=k!/( (k-3)!3! )個ある。組み合わせをc1、c2、、cmax(max=k!/( (k-3)!3! ) )とすると、Kpのときそれぞれの数はc(j、m)となる。

    (1)Kpから辺を1本取り除いた単純グラフG1は、2頂点の色と辺の色の組み合わせの辺の色cjのそれぞれの数は0以上c(j、m)以下となるので、k-全彩色可能である。

    (2)Kpから辺をi(i≠p(p-1)/2)本のとき、命題が成り立つとする。

     Kpから辺をi+1本取り除いた単純グラフGi+1は、2頂点の色と辺の色の組み合わせcjのそれぞれの数が0以上c(j、m)以下となるので、k-全彩色可能である。

    (3)Kpから辺をp(p-1)/2本取り除いたグラフGp(p-1)/2は2頂点の色と辺の色の組み合わせcjがすべて0なので、k-全彩色可能である。

    よって、命題は成り立つ。(証明終わり)

 

  全彩色予想

   任意の単純グラフGに対して、最大次数をΔGとする。

    χ2(G)≦ΔG+2

   である。

   (証明)

    定理4・1と完全グラフKpの最大次数ΔKpがp-1より、

     χ2(Kp)=ΔKp+1(pが奇数)、ΔKp+2(pが偶数)

    命題4・2より、

     χ2(Gi)≦ΔGi+1(位数が奇数)、ΔGi+2(位数が偶数)

    よって、任意の単純グラフGはχ2(G)≦ΔG+2である。(証明終わり)

完全グラフと全彩色予想③

3,辺彩色

  グラフGの隣接する辺が異なる色になるように、グラフGの各辺に色をつけることを、Gの辺彩色といい、k個の色が使われているとき、それをk-辺彩色という。グラフGに対して、k-辺彩色が存在するときGはk-辺彩色可能であるという。Gがk-辺彩色可能であるが(k-1)-辺彩色可能でないとき、kをGの辺染色数といいχ1(G)で表す。

 

  定理3・1

   完全グラフKpに対して、

    χ1(Kp)=p(pが奇数)、p-1(pが偶数)

   である。

   (証明)

    (1)pが偶数の場合、Kpは定理1・1より、p-1個の1-因子Fi(i=1、2、・・・、p-1)に分解できる。各因子Fiに色iを付ければ、Kpのp-1色による辺彩色が得られる。よって、χ1(Kp)≦p-1。一方、Kpの最大次数はp-1であるからχ1(Kp)≧p-1。したがって、χ1(Kp)=p-1となる。

    (2)pが奇数の場合、Kpのp頂点を正p角形の頂点になるように配置し、正p角形の境界上のp個の辺をp色で塗る。そして、正p角形の内部の各辺を、その辺と平行な位置にある境界上の辺と同じ色を塗る。このようにして、χ1(Kp)≦pを得る。次に、Kpの辺彩色においては同色の辺が隣接せず、1本の辺が2頂点と接続していることより、(p-1)/2本の辺以下しか同じ色をつけることができない。ところで、Kpの辺の本数はp(p-1)/2本であるから、χ1(Kp)≧pが得られる。よって、χ1(Kp)=pとなる。(証明終わり)

完全グラフと全彩色予想②

2、線グラフと全グラフ

  グラフGにおいて、頂点集合E(G)を持ち、その中の2頂点は、G内の隣接する2辺であるとき、かつそのときに限って隣接するようなグラフをGの線グラフといいL(G)で表す。

  グラフGの全グラフT(G)とは、集合V(G)⋃E(G)と1対1対応する頂点集合を持ち、T(G)の2頂点が隣接するのは対応するGの2つの要素(頂点と辺)が隣接しているか、接続しているとき、かつそのときに限るグラフのことである。

  命題2・1

   T(Kp)=L(Kp+1)

   (証明)

    完全グラフKpの性質より、L(Kp)もT(Kp)も正則グラフになる。r-正則グラフのサイズは握手補題より、rp/2になる。

    完全グラフKpの位数pk=p、サイズqk=p(p-1)/2である。

    よって、線グラフL(Kp)の位数pLはp(p-1)/2である。

    全グラフT(Kp)の位数pTはpk+qk=p+p(p-1)/2=(p+1)p/2である。

 

    線グラフL(Kp)の正則数rLを考える。p-1の完全グラフに頂点を1つ加えると、辺はp-1個加えることになる。p-1個の辺のうち1つに着目すると、加えた辺p-2個と元々あるグラフの1個の頂点に接続されているp-2個の辺と隣接している。よって、rL=2(p-2)である。

 

    全グラフT(Kp)の正則数rTを考える。p-1の完全グラフに頂点を1つ加えると、辺はp-1個加えることになる。加えた頂点1つに着目すると、接続されている辺はp-1個、隣接されている頂点はp-1個で、2(p-1)である。加えた辺1つに着目すると、隣接されている辺は2(p-2)個、接続されている頂点は2個で、2(p-2)+2=2(p-1)である。よって、rT=2(p-1)である。

 

    完全グラフKp+1の線グラフL(Kp+1)について考える。

    Kp+1の位数pk=p+1、サイズqk=(p+1)p/2であるから、L(Kp+1)の位数pLは(p+1)p/2、L(Kp+1)は2(p+1-2)=2(p-1)の正則グラフである。これは、T(Kp)と同形である。よって、T(Kp)=L(Kp+1)である。(証明終わり)

完全グラフと全彩色予想①

(注意)完全グラフと全彩色予想の内容や定理の証明は「グラフ理論序説」からお借りしている部分が多いです。

 

1,因子分解

  グラフHがグラフGの部分グラフであるとは、Hが

   V(H)がV(G)の部分集合 かつ E(H)がE(G)の部分集合

  を満たすグラフのことである。特に、V(H)=V(G)のとき、HをGの全域部分グラフという。グラフGの全域部分グラフのうち、木であるものを全域木という。

  各頂点の次数(頂点に接続する辺の数)がすべて等しいグラフを正則グラフといい、各頂点の次数がkの正則グラフをk-正則グラフという。

  グラフGの空でない全域部分グラフを因子といい、Gのr-正則な因子をr-因子という。

  グラフGが因子の辺和として表されるとき、この和をGの因子分解という。すなわち、グラフGの因子Fi(i=1、2、・・・、n)があって、

   V(Fi)=V(G)、E(Fi)≠0 (i=1、2、・・・、n)

   E(Fi)⋂E(Fj)=0 (i≠j、i、j=1、2、・・・、n)

   ⋃{n,i=1}E(Fi)=E(G)

  が成り立っているとき、{F1、F2、・・・、Fn}をグラフGの因子分解という。特に、F1、F2、・・・、Fnがすべてr-因子のとき、r-因子分解という。Gにr-因子分解があるとき、Gはr-因子分解可能という。

  位数pのグラフで、そのどの2頂点も隣接しているとき、位数pの完全グラフといい、Kpであらわす。完全グラフKpは(p-1)-正則グラフであり、サイズはp(p-1)/2である。

  定理1・1

   完全グラフK2pは1-因子分解可能である。

   (証明)

    p=1のとき明らかであるから、P≧2と仮定してよい。

    K2pの点をv1、v2、・・・、v2pとし、正(2p-1)角形上の点に、反時計回りにv1、v2、・・・、v2p-1を配置する。正(2p-1)角形の中心をv2pとする。すべての頂点対を辺で結べばK2pとなっている。

    このとき、K2pの各1-因子Fi(i=1、2、・・・、2p-1)を、v2pvi及びそれに垂直な辺全体と定義する。そうすると、FiとFj(i≠j)はE(Fi)⋂E(Fj)=0で、F1、F2、・・・、F2p-1の返和がK2pとなっている。

    よって、{Fi}(i=1、2、・・・、2p-1)によるK2pの1-因子分解が得られた。(証明終わり)