こんにちは．15のmaruxです．

この記事は rogy Advent Calender 2020 3日目の記事です.
唐突にアドカレを書きたくなったものの，以降の日程はすべて埋まっていたため時を遡ることにしました．

さて，皆さんは二人三脚というものを知っていますか？
勿論ご存知かとは思いますが，一応説明をしようと思います．
二人三脚とは，2人の人間A,Bが組になり，Aの右足とBの左足を纏めて縛った状態でゴールまでの速さを競う競技です．
運動会ではおなじみですね．

ただ，この二人三脚，人数も足の縛り方も限定されていて少し寂しいです．
掛け声も1,2,1,2の連続で少し味気ないですしね．
そこで，本記事では二人三脚を拡張していき，二人三脚に自由度を与えていこうと思います．
特に，どんな掛け声にすれば自由度を上げても進めるか，というところに興味があります．

まず，二人三脚がどうしてｲｯﾁﾆｲｯﾁﾆの掛け声で進めるかを考えようと思います．そのために人間の脚をグラフにモデル化しましょう．

これが人間です．

丸(以後頂点と呼びます) が1本の脚を表していて，緑色の線分(以後辺) により2本の脚を同時に動かすことはできないという拘束条件を表すことにします．

この人間を基にして二人三脚をグラフで表現すると下図のようになります．

ここで赤色の辺は，縛られていて同時に動かさなければならないという拘束条件を表します．

これらの頂点に色を割当て，その色に従って進むことにしましょう．
つまり，「赤！」と言われたら赤を割当てられた脚を前に出すということです．
まず，きちんと進むためには緑の辺で結ばれた頂点の組は異なる色が割当てられる必要があります．
もし同じ色が割当てられていると，その人は2本の足を同時に出す必要が出てきてしまいます．
また，赤の辺で結ばれた頂点の組には同じ色を割り当てる必要があります．
2本の脚は結ばれているため，別々に動かすことが不可能であるからです．

ここで，赤の辺で結ばれた頂点に関しては同じ色が割当てられるので，1つの頂点とみなしてしまってもいいことが分かります．(縮約と言います)

この操作を行うと上図のようにグラフは分かりやすくなり，隣接する頂点には同じ色を割当ててはならないという条件のみが残ります．

下図を見てわかる通り，二人三脚の場合では2色あれば適切に割当が可能です．
1色では不可能なので，二人三脚は2種類の記号による掛け声であれば進めるということを理解することができました．

 

次に，よく知られた二人三脚の拡張について触れたいと思います．

まずはn人n+1脚について話そうと思います．
たまにテレビの企画とかでやってる30人31脚みたいなやつですね．
それを先ほどの形で記述するとこうなります．
これを縮約してやると，

このようになるので，

こんな感じで2色で適切な割当にすることができます．
つまりn人n+1脚は2種類の記号による掛け声であれば進めます．

次にムカデ競争について見てみると，

上図のように記述できるので，縮約すると

という形になり，

ムカデ競争についても2種類の記号による掛け声であれば進めることが分かります．

さて，ここまで非常に限定的な拡張について見てきましたが，ここから更に拡張していきましょう．
n人m脚を考えていきたいと思います．

例えば，上図のように繋いでみた場合はどうでしょうか．
(長い赤い辺はムカデ競争の板のようなプレートで繋がっていると思ってください)
これも縮約を繰り返して色を割当ると，と，なり3色で適切に割当が可能なことが分かります．
したがってこの結び方の場合，3つの記号の掛け声で前に進むことができます．

では，一般には何色あれば色の適切な割当が可能なのでしょうか？
ここで考えるグラフには2つ条件を付けたいと思います．

まず1つ目の条件は割当不可能なグラフではないということです．

つまり，上図の上側の人のような，片方の脚から赤い辺を辿るともう片方の脚にたどり着けるような人は居ないということです．
こうした人が居た場合，赤の辺の拘束により両足を同時に動かす必要がありますが，緑の辺の拘束により同時に動かすことができず，適切な割当が存在しません．
逆も同様に成り立ちます．

次に2つ目の条件は，辺は平面上で交差しないということです．

上図で人間がどんな様子になっているかを考えると，紐のような拘束が空中で交差していることになり非常に危険です．
また，緑の辺と他の辺が交差している場合，人間の股下を何かが通っていることになりやはり危険です．
したがってここでは考えないことにします．

この2条件を満たすグラフを考えると，そのグラフは平面上で辺の交差なく描かれていることが分かります．
つまり平面的グラフ(平面上に描くことのできるグラフ)であります．
有名な4色定理 から4色で適切に割当が可能であることが分かり，4つの記号つまり1,2,3,4,1,2,3,4,…の掛け声でn人m脚は進行可能であると分かります．

逆に，下図のような例で4色必要なため，4色は必要である例があることも分かります．

これで二人三脚の拡張が少しできました．
いやでもしかし，まだ拡張できそうではありませんか？

そう！二人三脚の”人”の部分です．
いまやペットを飼うのは当たり前の時代，犬や猫と一緒に二人三脚したいという人も少なくないはずです．

そこで4足歩行の動物も含めて考えてみましょう．
まず，四足歩行の動物はどの脚も同時には動かしてはならないものとします．
つまり，下図のように表現されるわけですね．

こうして表現すると，出来るグラフはどの辺も高々1度しか交差しないようなグラフになります．
こうしたグラフは1-平面グラフと呼ばれ，6色あれば色の割当てができることが知られています．
また，下図の例で6色は必要であるので，6色が下限であることも分かります．

よって4足歩行の動物とともに二人三脚したいとき，1,2,3,4,5,6,1,2,3,4,5,6,…の掛け声で進むことができます．

 

これで一般化二人三脚の話はおしまいです．
最後まで読んでいただきありがとうございました．