カッコのつかない話。

あのね、たまにはこういうエントリがあってもいいんだよね。

ん？
誰と話してるの？
ハハハ・・・
気にしない、気にしない。
ところで、さ。
何？
ちょっと思ったんだけど、鍵括弧が一つも存在しない小説とかってないよね？
まぁ、たぶんね。
絶対に会話は出てくるわけだし。
うん。
けどさ、別に鍵括弧がなくてもどこが会話で、しかもどの文が誰の発言なのかも分かるような気がするんだ。
というと？
例えばね、次みたいな感じはどうかなぁ。
ちょっと待ってね、鍵括弧を全部無くしたのを書いてみるから。
・・・出来た。
ほら。
ハンニ先生はひっつめ髪に鋭角的な縁なし眼鏡をかけた三十歳になる女性教師で、過剰な悲嘆癖と抜き打ちテストの趣味さえなければとても善良で敬虔な信仰者だ。
敬虔な信仰者というのはキーリの中では褒め言葉ではないが。
ああキーリ、まったくあなたったらなんていうことかしら。
まったくなんていうことなのかしら。
ああ神よ。
まあどうしましょう。
ハンニ先生はさっきからその程度の種類の少ない言葉で嘆いては、大げさな仕草で天井を仰ぎ、眼鏡をはずしてハンカチを目頭にあてるというのを繰り返している。
練習に遅刻したうえにその格好。
まさか今日の礼拝のことを知らなかったわけじゃないでしょう。
すみませんハンニ先生。
知らなかったんですハンニ先生、と言いたいのをこらえてキーリは素直に謝った。
下手に理由を並べ立てて先生と不毛な問答をするのは避けたい。
誰も教えてくれませんでしたなんて言い訳をするのもなんだか格好が悪いし（それは実際、正当な理由ではあったけど）。
・・・どう？
んー、どうって・・・まぁ、読めなくはない、かな。
でしょ。
たださ、やっぱり読みにくいんじゃないかなぁ。
なんか知らないけど、読点もやけに少ないし。
それはこの作者の癖というかなんというかだからねぇ。
そんなもんなの？
ま、いいや。
で、鍵括弧を全部無くしても読めなくないのは分かった。
じゃあそれで何が言いたいの？
まさか。
だから鍵括弧なんて飾りです。
偉い人にはそれが分からんのです。
がオチとか、そんなことは言ったり・・・
ギクッ！
・・・あ、当たり前じゃん。
さすがにそんなこと言ったりはしないよ。
ハハ、ハハハハハ・・・
・・・思いっきり動揺してるじゃん。
ゴホン！
それはおいといて。
ここで問題にしなければならないのは、どうして鍵括弧を取ってしまってもそれが会話だと分かるのか、ってこと。
しかもそのセリフを言ったのが誰かってことまで分かるわけで。
なるほど。
確かにそれは不思議だねぇ。
でしょ？
何でだと思う？
一応最初に聞いておきたいんだけど。
何？
これって正解ってあるの？
さぁ？
さぁ、って・・・正解があるのかどうかも分からない状態で聞くなよ。
とは言ってもねぇ。
いろんな意見を聞いてみたかった、っていうのもあるからねぇ。
で、何でだと思う？
なんかいい考え、ない？
そうだなぁ・・・

（ごめんなさい、実はここから先はまだ考察している途中で、考えがまとまっていません。口調、改行、それらに対する反論（これはこの文章自体でメタ的に）、ＡＩだとどうか、経験、規則、という考察。そして、文章における「状態変化の期待」の存在によるもの（←これが今のところ本命）、と論を進めていく予定。オチは・・・本命で考えがまとまれば予定通りで。まぁ、せっかくなので読んでいる人がいれば読んでいる人も考えてみてください。）

---

っていう短編小説（？）でした。

ちなみに文章中の引用は『キーリ　死者たちは荒野に眠る』の第１章、冒頭部分からのものです。
（にしても、キーリ、いいですねぇ。オススメです。）
この引用の「内容」ではなく、引用「それ自体」も実はこの話題と関係があって、ここが引用なんだ、というのが印をつけなくても分かるというのは、なぜそこが会話なのかが分かる、というのと同じ理由が隠されていると考えられます。

カット消去定理。

LKのカット消去定理に関しての疑問。

今『入門数学基礎論』を使って基礎論の初歩を勉強中。

で、やっとLKの基本定理のカット消去定理の証明をじっくりと読んでいって一通り納得がいく形になったのですが、その証明『自体』を眺めて疑問に思うことが、（というか、証明論における定理の証明全般でだけど）「帰納法」を当然のように使って証明しているということ。

ヒルベルトのHにしろゲンツェンのLKにしろ、その公理（あるいは推論の形式）に「帰納法」は含まれていない（「帰納法」の公理は自然数論に含まれている。よくよく考えれば、「任意の自然数について」というのを証明するものなのだから、論理の体系自体には含まれないのは当然）のにそれを使って定理を証明するっていうのはＯＫなのかなぁ・・・？

LKの定理がLKでは証明できない、というのであれば、LKの定理を証明するために使った「体系」が本当に無矛盾なのかが問題となるわけです。
んで、それじゃ困るからと「帰納法」もLKに含めたとしたら、新しい推論の形式がLKに付け加わるわけだけれども、それを付け加えたときにもともとあったLKの性質は変わってしまわないのか、というのも気になるところ。

後者の場合、LKの推論の形式というものを「論理式」として扱っていく（表現する）必要が出てくるわけだけれども、それは可能なのか、という問題もあるし。

まぁ、ここらへんが二階の述語論理っていうのに関係して来るんだと思うので、もうちょい勉強してみたいと思います。

ロボットは敵意を持つか？。

公開セミナー「敵か味方か―ロボットをめぐる文化」に参加して。

なんかポスターで見かけて面白そうだったので参加してきました。

ケルン大学のハンス・エッセルボルン教授による講演「ロボットとコンピュータは敵となり得るのか？」がまずあり、そのあとに文学部の巽先生と理工学部機械工学科の前野先生がコメント（補足？）をするという構成で、面白い内容でした。

講演はドイツ語でだったのですが、当然分かるわけもなくひたすら日本語訳された内容を読む（スライドが表示された）しかなかったのがちょっと残念。
読むのにいっぱいいっぱいでメモを取れませんでした。
あと、やはり「聞きながら」だと熟考することが出来ないのがやはり痛いですよねぇ。こう、疑問に思ったことを手放さないようにする間もなく次に進んでしまいますから。

で、自分が数学をやっている人間のせいか、「敵意」や「善悪」、「理性」に関する議論があまりに先入観にとらわれている気がしました。ある意味、すごく西洋的というか、ここまで思想（思考）というのは文化や歴史に影響を受けるものなのかと。

当然ですけれど、本来的に「物」である機械に「敵意」は生まれませんし、「善悪」や「理性」というのも人間社会や人間個人、あるいは西洋史観の中で生まれた「幻想」あるいは「願望」に過ぎないわけですから、「物」にそれを理解することは出来ません。
あるとすれば、「物」に「感情」を見出すことが出来るという人間の「心」（あるいは機能）によるものです。

例えば、プログラムが暴走して人間に危害を加えた、人間を支配しようとした、ということが起きたとします。
これは、人間から見たらロボットが人間に敵意を向けてきたように「見えます」が、“ロボットに心がないのであれば”ロボットはあくまで人間に対して盲目なまでに従順に従っているだけです。
進化的プログラムによってロボットが「暴走」と見られるようなことを行ったとしても同じです。
それを「敵意が生じた」とか「暴走した」と見るのは、人間の視点があって初めて成り立ちます。

ただし、“ロボットに心が生じたのであれば”――すなわち単なる計算の結果が人間によって「敵意」と解釈されるのでなく、ロボットが「敵意」を「敵意」として実感（クオリア？）をもって抱くようになったのであれば、当然話が変わってきます。
もちろん、抱いた「敵意」を実際に行ってしまえるという「自由決定権」を持つことも条件とされますが、そこで行われた「敵意のある行為」というのは先の述べたプログラムの暴走などとは本質的に異なります。
なぜならそれは、ロボットによって「回避することも可能であった」からです。
（自由決定権を持たない場合は、２つの場合が考えられ、「敵意は持ったけれど実行することは出来ない」という場合と「敵意はなかったのだけれど避けることが出来なかった」という場合です。後者の場合は悲惨ですね。）

だから、単純に「敵意」とかを扱うのでなく、ロボットに心がない場合と生じた場合にきちんと場合分けして論ずる必要があるわけです。

けれど、ここで一つ疑問が湧きます。
ロボットに心があるのかないのかを、果たして本当に調べることが出来るのか？
それこそ「心」があると感じている自分の「心」すら本当にあるのかどうかが怪しいわけですから。（※ここでいう“自分の「心」”というのは＜私＞という概念のことです）
結局「心」というのはあくまで「私の心」（これは＜私＞を包む私の意識のことです）に見出されるものであって、その実在を調べることは出来ないと考えられます。

となれば、ロボットに心があるのかどうかは本質的でなく、そしてこの議論を踏まえるからこそなおさらに、「敵意」云々は人間がロボットをどう見るのか、ということが本質であることが見えてくるわけです。

そのうえで、次のような疑問を問いかけます：
「なぜ人は、ロボットが敵意を抱くのではないかと危惧するのか？」
これを考えてみれば、そもそもこのような危惧を抱く理由というのが、自分自身がもし人間を超えるような力を得たときに、自分がこういう行動をとるのではないのか、という「自分自身」の影があればこそだというのが分かります。
アメリカが「自分自身の『影』」を仮想敵国に投影するのに似ていますね。
あそこの国は自分の国の自由を脅かそうとしているのではないか――それは心の奥で自分たちが自分たちの自由のために他人の自由を奪っていっているという「影」があればこそです。

だからか、日本のマンガやアニメにおいてロボットが人間を支配するというような構造はあまり見かけません。
対等な、けれど人間とは違う存在、あるいはもっと単純に、人間に奉仕する存在、であり、反乱を起こしたりはしません。
あるいは、反乱とみなされるようなことを行ったとしても「敵意」をもってそれを行ったとみなされることは少なく、あくまでも（人間から見て）「暴走」してしまった、という描画になることが多いように思われます。（だからロボットを「やっつけよう」とするのではなく、「元の状態に戻そう」とするわけです。）
日本において問題とされるのは、むしろ人間ーロボット間の恋愛が可能であるのかといった「人」と「物」における関係性の問題でしょう。
これは、「自己」と「他者」とのコミュニケーションや関係性といったものをを投影したものになっていると考えられます。
（なんか、書いているうちに考えがまとまってきた感じ・・・その場でこのような西洋とは違ったロボットの描かれ方もあるんだということを言えればよかったのですが。）

えぇっと。
長く自論を展開してしまったけれど、講演会の話に戻って。
まぁ、質疑応答での受け答えを見ていると「敵意」といったものを熟慮もなく扱っているというのは誤解で、ちゃんとエッセルボルン教授も「敵意」が人間視点によるものであることをおっしゃってました。
ただし、やはり「善悪」や「理性」といったもの、あるいは（確認は出来なかったけれどやはり）「自由意志」の存在というものは疑うべくもなく当然として存在するものである、といった感じはしました。そこはもう少し哲学的に考えていかないところではないのかな、と思います。（まぁ、キリスト教の影響圏の人には難しいと思いますが）

で、せっかくの機会なので自分も質問をしてみたのですが、やはり考えがまとまっていなかったせいでうまく質問することが出来なかったですねぇ・・・
西洋的な見方とはちがうロボットの見方は出来ないのか、というので『ちょびっツ』を挙げようかとも思ったのですが、結局考えがまとまらず、「エッセルボルン教授の話を聞いていて、やはり支配ー被支配の関係や階級といった西洋的な見方が強いと思ったのですが、人間とロボットが対立するという存在ではなく、人間の意識がロボットに移植され、人間がロボットに進化する、という見方をすることは出来ないのですか？」みたいな質問をしたのですが（って、進化っていうのも西洋的な進歩主義の見方で、今思うとすごく微妙なんですよね）、巽先生・エッセルボルン教授ともにそのような考えが表れた作品もあるよ、という感じで、じゃあそれをどう思うのか、という本質に答えてもらえなかったのがちょっと残念。
（ちなみに巽先生が挙げてくれた作品の一つが『ディアスポラ』）
問題が提起されている、という事実があるとして、それを認識するのも大切だとは思うのですが、じゃあそれをどう考えるのか、ということの方が大切だと思うわけです。
個人的には、この考えには否定を示して欲しかったのですが・・・
（詳しくは後述します）

ちょっと話はそれますが、この『ちょびっツ』のレビュー、すごくいいですね。
載せておきます。

　ちょびっツでは、人と、人同様に振舞う人型パソコンとの交流が描かれる。そこでは、文明、科学批判や現代特有の問題ではなく、物と心、愛とはなにかといった、人がこれまで、そしてこれからも無関心ではありえない事柄が扱われている。
　愛とは、その人（あるいはその存在）だから愛するということ、人間以外のものでも、「私」がそれを心あるものとみれば、それは心あるもの、そうではないのか。相手が人間であっても、「私」は自分以外の人の気持ちを直接感じることはできないのだから、人型パソコンと変わらないではないか。相手に心があるとどうして言えるのか。「私」が彼、彼女を心あるものとしてみているからではないか。そうであれば、人型パソコンであっても同じことであろう。
　相手を心あるものとして付き合うことによって愛がうまれる。愛によって、相手を心あるものとする。ちょびっツは、２つのテーマを向き合わせることで、互いに一方が他方を鮮明に照らしだす。それらは、主人公秀樹と「パソコン」ちぃやその他様々な人とパソコンとの関係として豊かな彩りをもって浮き彫りにされる。
　科学的なものの見方が一般的になったいま、物と心という非常に重要でありながら敬遠されがちな問題が、科学の進歩によってうまれた身近な問題として鮮やかに描かれている。そしてそれは愛と切り離しえないのである。
　ちょびっツの世界はいまにも実現されそうなもの、現実でありうるものとして私には感じられ、この作品の隅々まで血が通っているように思われる。
（Amazonカスタマーレビューより。著者：柳絢さん）

さて、先ほどの話に戻って。
どうして否定して欲しかったのか。
それは、＜私＞を身体を超えて移動することが出来るのか、という問題との関わりからです。

どういうことかというと、例えば技術が進んで本当にロボットに人間の心を移植するということが出来るようになったとします。（あるいは、出来るようになったと仮定してください）
このとき、一見すれば人間が生身の肉体を捨ててロボットの身体に移ることが出来るようになったように見えますが、実際に移植することを考えてみれば、そうとは言えないことが分かります。

ロボットに心を移植してみましょう。
ロボットには＜私＞が生まれ、そしてその＜私＞は、あぁ、ロボットに心が移植されたんだなぁ、と思うでしょう。
ここだけ見れば、何の問題もないように思われます。
でも、注目しなければならないのは元々の肉体の方です。
心を移植したときに、元々身体にいた＜私＞がどうなったのかを考えれば、次の２つの場合が考えられます。

1. ＜私＞は依然として身体に存在している



2. ＜私＞は既に身体に存在していない

前者の場合、＜私＞は依然として身体に存在しているのだから、身体にいる＜私＞とロボットに生じた＜私＞は別の＜私＞です。だから、＜私＞は移植できていません。
後者の場合、＜私＞のいない身体はいわゆる哲学的ゾンビか、あるいは生きていない状態になります。このいずれにしても、そうなる「瞬間」というものを「内側から」体験してみれば、それは今の＜私＞を失われるということに他なりません。
ロボットには確かに“＜私＞だったもの”から連続している＜私＞が渡されているかもしれませんが、それはもはや“今、「私が私である」と感じている＜私＞”とは別のものになってしまい、“＜私＞だったもの”は既に元の身体の方で失われてしまっているわけです。（伝えにくいですね。。。）
つまり、たとえロボットに心を移植しても、もはやその＜私＞は身体にある今の＜私＞とは別の＜私＞です。

結局、＜私＞を意識することの出来るロボットが「私」のパーソナリティ？を受け継いでいるだけに過ぎず、今まさに「私」が「私」であると感じている＜私＞は依然として肉体に存在するか、あるいは肉体から消去されて――殺されて――しまっています。
つまり、“今の＜私＞”を身体を超えて移植することは出来ないわけです。
（これは、＜私＞が魂でも肉体でもなく、「機能」であることによります。昔のエントリとも絡んで、そのうち思考実験を書きたいと思います。）

つづきはまた今度。

・前野先生に上の質問をして

・リベット博士の実験に関する質問をして、それに対する答え
（『マインド・タイム』）

・懇親会での話

・プラグマティズムの考え方、ルネサンス期の哲学について聞いて

・自然言語処理の研究の仕方について聞いて

彩色問題（２）。

以前取り上げたウェルシェ・パウエルのアルゴリズムについて補足。

その後の有限数学の授業で、
（１）ウェルシェ・パウエルのアルゴリズムで塗ると、彩色数より大きくなってしまう例を挙げよ。
（２）さらに、彩色数で塗れるようにアルゴリズムを改良せよ。
という問題が出されたんですよ。

まず（１）の例を見つけるのが結構大変だったのですが、例えば次のような例があります。

G:単純グラフ
V(G)={a,b,c,d,e,f}
E(G)={ac,cd,db,be,ef,fa}
（ようは、a-c-d-b-e-f-aと一周するグラフです。）

このとき、a,c,d,b,e,fの順に塗っていけば２色で塗り分けられるのですが、a,b,c,d,e,fの順に塗っていくと３色必要になってしまいます。
（実際、まずaを1で塗った後、bは周りに使われている色がないので1で塗られ、続いてcは2、dはcとbに隣接しているので、3で塗られます。）

つまり、同じ次数内で塗る順序をきちんと指定してやらないと余分に色を使ってしまうことがあると予想できます。

なら、そもそも高い次数から塗っていくのは後から塗るとより条件が厳しくなるから、というところに注目して、同じ次数の点でも、その隣接している点で既に塗られている点の数が多い順に塗っていけば大丈夫なんじゃないかな、と考えたわけです。
先ほどのグラフも、この考え方を導入すればちゃんと塗れますしね。

ということで、実装したのが以下のColGraph2。

---

package ColGraph2;

#--------------------------------------------------
# ColGraph2
#
# =スーパークラス=
# ColGraph
#
# =フィールド=
# color
# 色の配列へのリファレンス
#
# matrix
# グラフを意味する２次元配列へのリファレンス
#
# painted
# 隣接する点で既に塗られている点の数の配列
# へのリファレンス
#
# =メソッド=
# new();
# インスタンスを作成する。
# 引数はフィールドの配列のリファレンス。
#
# input_new();
# インスタンスを作成する。
# 標準入力からフィールドを作る。
#
# talk_new();
# インスタンスを作成する。
# 対話型でフィールドを作る。
#
# check();
# グラフの行列になっているかをチェックする。
# なっていないときには0を返す。
#
# num();
# グラフの点の数を返す。
#
# dim(line)
# グラフの行の次数を返す。
#
# get_line(line);
# グラフの行の配列のリファレンスを返す。
#
# print();
# グラフの行列を表示する。
#
# set_color(num, color);
# numの点の色をcolorにする。
#
# get_color(num);
# numの点の色を取得する。
#
# add_painted(num);
# numの点のpaintedを1増やす。
#
# get_painted(num);
# numの点のpaintedの値を得る。
#
# print_color();
# colorの配列を出力する。
#
# paint();
# 改良版のウェルシェ・パウエルのアルゴリズムで
# 彩色していく。
#
#--------------------------------------------------

use ColGraph;

@ISA = 'ColGraph';

#----------------------------------------
# メソッドの実装
#----------------------------------------
sub new{

    my ($class, $ref) = @_;

    my $painted;

    my $obj = $class-＞SUPER::new($ref);

    foreach(1..$obj-＞num()){

        push @$painted, 0;

    }

    $obj-＞{painted} = $painted;

    return $obj;

}

sub add_painted{

    my ($self, $num) = @_;

    ++($self-＞{painted}-＞[$num-1]);

}

sub get_painted{

    my ($self, $num) = @_;

    return $self-＞{painted}-＞[$num-1];

}

sub paint(){

    my $class = shift @_;

    my %struct;

    #次数をキーとするハッシュに点を振り分ける

    foreach(1..$class-＞num()){

        my $dim = $class-＞dim($_);

        #キーが存在しない場合は空の配列リファレンスを作成

        unless(exists $struct{$dim}){

            $struct{$dim} = [];

        }

        #点をハッシュの指す配列に入れる

        push @{$struct{$dim}}, $_;

    }

    #次数の高い順に塗っていく

    foreach my $num (sort {$b＜=＞$a} keys %struct){

        my $nums = $struct{$num};

        #paintedの高い順に塗っていく

        while(1){

            my $color = 1;

            my $flag = 0;

            my $line;

            #塗っていないのがなければループを抜ける

            unless(@$nums){

                last;

            }

            #あれば、paintedの一番高いものを取得

            else{

                @$nums = sort {

                    $class-＞get_painted($b) ＜=＞ $class-＞get_painted($a)

                } @$nums;

                $line = shift @$nums;

            }

            #色を探す

            while(1){

                #隣接している点で同じ色がないかチェック

                foreach(1..$class-＞num()){

                    if($class-＞get_line($line)-＞[$_-1] == 1){

                        if($class-＞get_color($_) == $color){

                            $flag = 1;

                            last;

                        }

                    }

                }

                #同じ色があった場合次の色で試す

                if($flag){

                    ++$color;

                    $flag = 0;

                    next;

                }

                #なかった場合ループを抜ける

                else{

                    last;

                }

            }

            #見つけた色をセット

            $class-＞set_color($line, $color);

            #隣接している点のpaintedを1増やす

            foreach(1..$class-＞num()){

                if($class-＞get_line($line)-＞[$_-1] == 1){

                    $class-＞add_painted($_);

                }

            }

        }

    }

}

1;

---

ちょっと解説すれば、paintedというフィールドを加え、そこに自分と隣接する点で既に塗られているものが何個あるのか、という情報を加えてあります。
それで、塗る頂点の順番を次数だけで決めるのでなく、まず次数別の配列にした後、その配列内でさらにpaintedの大きい順に塗る、というアルゴリズムにしました。

このアルゴリズムでさっきのグラフはちゃんと塗れるようになったんですけれど、これでもうまく塗れないグラフが実験をするうちに現れてきました。
次のようなヤツです。（グラフの行列で表します。）

0 1 1 0 0 0 1 1
1 0 1 1 0 0 0 1
1 1 0 1 1 0 0 0
0 1 1 0 1 1 0 0
0 0 1 1 0 1 1 0
0 0 0 1 1 0 1 1
1 0 0 0 1 1 0 1
1 1 0 0 0 1 1 0

なんかきれいな行列ですよね（＾＾）
８つの頂点をまずa-b-c-d-e-f-g-h-aと結び、そのあとa-c-e-g-aと一つ飛ばしで結んだのと、b-d-f-h-bとやはり一つ飛ばしで結んだものとを加えたのになっています。（うまく並べると平面グラフになっています。）

で、これを先ほどのColGraph2を使ったプログラムに入れてやると、５色で塗り分けられます。
けれど、このグラフは平面グラフですから、４色で塗れるわけで、彩色数よりも多い数を使ってしまっています。
（ちなみにColGraphを使ったものだと４色で塗り分けられます。なんとも不思議なことに、Perlのハッシュのキーの整列の仕方はこの塗り方にちょうどよくなっていました。）

そんなこんなで、どうにかうまい具合に改良できないかなぁ、とここ数日悶々と考えていたのですが、そのうちにそもそも次数の高い順に塗っていけばOKという思い込みを壊す例が出てきました。
どんなのかというと、次のようなヤツです。

0 1 1 1 0 0 0 0
1 0 0 0 1 0 0 0
1 0 0 0 0 1 0 0
1 0 0 0 0 0 1 0
0 1 0 0 0 0 0 1
0 0 1 0 0 0 0 1
0 0 0 1 0 0 0 1
0 0 0 0 1 1 1 0

これもなかなかきれいですｗ
頂点a,b,c,d,e,f,g,hで、aとhを結ぶように
a-b-e-h
a-c-f-h
a-d-g-h
となっているグラフです。

このグラフは２部グラフなので（a,e,f,gとb,c,d,hに分かれる）、２色で塗り分けられるのですが、次数の高い順に塗っていこうとすると、まずaとhが次数3なのでそれぞれが1で塗られ、その後b,c,dは2で塗られますが、e,f,gはすでに1と2が使われてしまっているので3で塗られてしまいます。

この例が出てきたので、もはや次数の高い順に塗っていき、あとは同じ次数内でどういった順番で塗ればいいのか、という問題では済まなくなってしまっています。
それこそ全部の点を相手にして、どういった順番で塗っていくのが正しいのか、という問題になってしまってますから、「グラフをどういった順序で塗っていくべきか」という問題と同じレベルになってしまい、このアルゴリズムを使っても問題が簡単になっていません。

ということで、ウェルシェ・パウエルのアルゴリズムじゃない方法で塗れないかなぁ、というのがここ数日ずっと考えていることです。
上で見たとおりウェルシェ・パウエルのアルゴリズムで問題となるのが閉路を含む場合であるのは明らかなので、最小の閉路をまず探し、その閉路の中で彩色をしていくのがいいんじゃないかなぁ、と考えています。
その方法をとった場合、問題となるのは、ではそういった閉路をどういった順番で塗っていくのか（奇サイクル（小）→奇サイクル（大）→偶サイクルの順、長さの順など）ということと、その閉路内で、どういった順番に塗っていくようにすればいいのか、ということです。
この２つについていろいろなパターンを今考えているのですが、なかなかうまい解決策が見つかっていないのが現状です。

一応、どの頂点の次数も２以上のグラフにおいて、任意の点で、その点をスタート＆ゴールとする最小の閉路を見つけるアルゴリズムは思いついたので（まぁ、再帰呼び出しみたいなことをオブジェクトにおいてやるわけですが）、あとは上の２つの点を解決できればうまく行きそうな気がします。

---

余談。
例で一番最後に出したグラフ、確かに平面グラフだけれど、この平面グラフを持つような地図ってホントに存在するのかなぁ、と考えると、これが結構難しい。
答えを言ってしまえば存在するのだけれど（なんとなれば、円の直径を３等分して、そのそれぞれを直径とするような円を作図すればいい）、地図⇒平面グラフに表せる、は正しいとしても、平面グラフ⇒対応する地図が存在する、というのはちょっと怪しいかも。もう少し条件を厳しく出来そうな気もします。

正方形の７等分。

以前書いた７の７乗の７乗の…。といっしょに『高校への数学』の裏に載っていた問題について。

問題の概要は以下。

正方形をコンパスを使わずに二点を結ぶ直線を引くだけで7等分する方法を求めよ

実はですね、自分はこれが解けなかったんですよ。
コンパスを使わない、ということは、線分を２等分することさえままならないんですよね。


もちろん、その正方形が折り紙で、折ることが出来る、というのであれば、２n等分することが出来るので、以前に（というか中学生のときに）自分が発見していた「折るだけで（＝２等分と直線を引くという操作のみで）３等分出来る」（後述）という方法を用いて、まず３等分し、次にそれを２等分することで６等分し、先の３等分する方法と同等のことをすれば７等分することが出来るんですよ。

けれど、これじゃたぶんダメなんですよね。
おそらく、正方形の中心と、どこか１つの頂点から任意定数aの長さの点を取り、有限回線を引くという作業をすることでこの任意定数aをなくすことが出来ないといけないわけです。
バイトの合間に喫茶店にこもって２～３時間この任意定数のaをなくすために連立方程式を解きまくった（※座標軸に正方形を入れて計算していたので）のですが、結局aはなくならず、解くのを断念してしまいました。

そしたら、ネットは広いですねぇ。
同じ問題を質問している人がいて、しかも解いている人までいる！
以下、解答。

「直線○△と直線●▲の交点を□とする」ことを
「□=○△×●▲」と表します。
正方形ABCDにおいて、
(1) O=AC×BD
(2) AB上の適当な場所に点Eをとる。
　（A寄りに取った方が作図しやすい）
(3) F=CE×DA, G=ED×AC
(4) H=FG×CD, I=HO×AB
　（HはCDの中点, IはABの中点）
(5) J=ID×AC, K=HJ×AB（KはAIの中点）
(6) L=KC×BH, M=AL×BC（MはBCを6：1に内分する）
(7) N=MD×IH, P=CN×AD（PはADを6：1に内分する）
(8) Q=MP×IH（長方形PMCDは正方形ABCDの1/7）
(9) R=DQ×BC, S=CQ×AD, T=SR×IH
(10) U=PT×BC, V=MT×AD
(11) m=MO×AD, r=RO×AD, u=UO×AD
(12) p=PO×BC, s=SO×BC, v=VO×BC
これでpm,sr,vu,UV,RS,MPにより7等分されます。
図は雑ですがこんな感じ
こちらより引用（Googleのキャッシュ）

いや、驚きましたよ。
まだこれで大丈夫なのかの検証はしてないんですけれど、たぶんあっているのでしょう。（後で検証したものを下に書きます。）
それにしても、線を正方形の外側まで伸ばす、というのは盲点。
最初に折る方法から考えていたせいか、「正方形＝折り紙」的な先入観が入ってしまって、外側まで線を引くというのはまったく考えていませんでした。
やはり数学において先入観が入ってしまうとろくなことがありませんね。

---

＝折るだけで長方形の紙を３等分する方法について＝
（時間がないので証明などはあとで書きます。）
長方形ABCDにおいて、ABの中点MとCDの中点Nを折ることで作図します。
次に、点Aと点C、点Dと点Mを結ぶように直線を引きます。
その交点をPとし、Pを通るようにABまたはADに平行になるように紙を折れば、３等分されています。
（より厳密にしたければ、点Bと点D、点Aと点Nを結ぶように直線を引き、その交点をQとし、直線PQを引けば、しっかりとADと平行になるようになります。）