第297回　グラフ理論：壁の中、壁の外（前編）

$ \newcommand{\HIRANO}{\unicode[sans-serif,STIXGeneral]{x306E}} \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\TRUE}{\textbf{true}} \newcommand{\FALSE}{\textbf{false}} \newcommand{\SET}[1]{\{\,#1\,\}} \newcommand{\EMPTYSET}{\{\,\}} $

屋上にて

テトラ「ここしばらく雨が続いていましたから、久しぶりに晴れると《外に出た！》という気持ちになります」

僕「そうだね」

テトラ「……それにしても、グラフって不思議です」

僕「え？」

テトラ「いえ、グラフが不思議というか、表現が不思議というか……」

僕「何の話なんだろう」

テトラ「村木先生の封筒のことを思い出していたんです。地図で国境を越える回数を考えること（第293回参照）、 センサーを配置すること（第294回参照）、 機材を予約すること（第295回参照）……そんな、 まったく関係がないように見える問題なのに、 とても深い関係があるのが、不思議です」

僕「ああ、三つの封筒の話だね。確かに不思議といえば不思議だよね」

テトラ「はい。グラフを使って表現すると、 無関係だと思っていた問題に同じグラフが現れてきて、実は同じ問題だったんだ……とわかる」

僕「そうだね。それからグラフを使って表すと、問題が直観的にわかりやすくなったり、考えやすくなったりすることもあるよね。 頂点をつなぐことや、辺の両端を違う色で塗ることも、 考えを進める役に立つし」

テトラ「はいはい、そうですね。目の前にあるグラフに対して、具体的に根気よく試していくことができますし……あたしが、特に不思議だと思うのは表現の役割です」

僕「表現の役割って？」

テトラ「あのですね。地図でも、センサー配置でも、機材予約でも、それぞれ問題は与えられているわけじゃないですか。 でも、それをグラフで表現したからといって、意味が変わるわけじゃないですよね」

僕「そりゃそうだね。問題の意味を変えるような表現をしちゃまずい」

テトラ「それなのに、もとの問題よりも考えやすくなる……というのが不思議です。意味は変えていない。変えたのは見映えだけ、見え方だけ、表し方だけ……つまり表現だけを変えたのに、 考えやすさが変わるのが不思議です。 表現って、どんな役割を果たしているんでしょう。 問題の意味は変わらなくても、問題の何かは変わっているはずですよね。 あ、あたし、当たり前のことを不思議がってます？」

僕「いやいや。いかにもテトラちゃんらしい疑問だね。とても根源的で、考えさせられてしまう」

テトラ「先輩は、どう思いますか」

僕「うーん……どんな役割かはわからないけど、グラフに限らず、数学では『どのように表現するか』が重要なのは確かだね。 テトラちゃんが考えている表現とは違うかもしれないけど、僕は方程式のことを思い出していた」

テトラ「それは、どういうことでしょう」

僕「たとえば二次方程式が実数解を持つかどうかを考えたいとする。判別式が$0$以上になっているかを調べるなら、それは式という表現で考えている。 でも、二次関数が作る放物線が$x$軸と交わるかどうかを考えることもある。 そこでは放物線という表現で考えている。 もちろん答えは同じなんだけど、 問題の設定によっては、片方が解きやすくなることはあるね」

テトラ「なるほどです。実は数学のあちこちに出てくる話なんですね」

僕「式で表現するときでも、わかりやすいときとわかりにくいときがあるよね。$x$に関する二次方程式を$ax^2 + bx + c = 0$という式で表すときは、その解はすぐにはわからない。もちろん解けばわかるけど。 でも、二次方程式を$a(x - \alpha)(x - \beta) = 0$という式で表すなら、解はすぐにわかる」

テトラ「そうですね。もう$\alpha$と$\beta$が見えてますから。考えてみますと、分数もそうですね」

僕「分数？」

テトラ「わかりやすさの度合い、ややこしさの度合いです。$3141/6282$と表現したときと、$1/2$と表現したときでは、表している値は同じですがややこしさは違います」

僕「なるほどね……うん、そうだ。《表現》は《操作》と結びついているのかも」

テトラ「操作？　表現を操作するんですか？」

僕「そうだよ。いまのテトラちゃんの例でいうと、$3141/6282$という分数に対して《約分》という操作を行う。そうすると$1/2$という分数になって、ややこしくなくなる」

テトラ「《操作》というか《計算》でしょうか」

僕「うん、いまは数の例を出したから《計算》の方がいいかもしれないけど、もっと一般化していえるなと思ったから。それでね、単純にするだけが操作じゃないんだよ。 分数という表現については、《通分》という操作もできる。 $$ \frac12 + \frac13 = \frac36 + \frac26 = \frac{3+2}{6} = \frac56 $$ ここでは、分母を揃えるために分子と分母を大きくして、足し合わせやすくしている。 自分の目的に合うように表現を変形させる《操作》が大事なんだなあ……と思うんだ」

テトラ「あっ、それはうまく表現すると考えやすくなるという話ですねっ！　つながりましたっ！」

僕「そうだね」

テトラ「分数の話は以前も先輩からうかがったことがあります（第265回参照）。約分することの意味も……（第177回参照）」

テトラちゃんのパズル

僕「テトラちゃんは根源的な問いをしてくれるから、とても勉強になるよ」

テトラ「きょ、恐縮です……あっ、そうだ。先輩、こんなパズル知ってますか？」

僕「なるほど。これはテトラちゃんが考えたの？」

テトラ「いえ、違います。中学生のころにクイズの本で読んだんです。三軒の家と、水・ガス・電気という三つの設備があって、 各家を三つの設備と結ばなくちゃいけない。 でもその九本の線はどれも交差してはいけません……というパズルでした」

僕「なるほどね」

テトラ「でも、あたし、水道と電気が交差してもいいんじゃないかしら……などと思ったんです。なので、さきほどの《パズル》では、平面上の頂点の話にしちゃいました」

僕「テトラちゃんは、このパズルを解いたの？」

テトラ「それがですね、先輩聞いてくださいよ。あたし、かなり時間を掛けてチャレンジしたんですが……あっ、だめです、探り入れないでくださいっ！」

​

図書室にて

テトラ「……先輩、いかがでしたか？」

僕「うん、何とか《証明》できたよ」

テトラ「え？」

僕「え？　テトラちゃんのパズルだよ。問題の条件を満たすようなグラフを平面上に描くことはできないことを証明したんだけど……もしかして、テトラちゃんは描けたの？」

テトラ「あ、いえ、そうではありません。あたしはもちろん描けてません。あたしがびっくりしたのは、先輩が証明なさったからです」

僕「うん、だって、できなそうだとわかったら、証明したくなるよね」

テトラ「そう、そうですよね、そうすべきですよね……あたしは『ああ、このグラフを描くことはできない』で終わらせてしまいました。テトラ、反省です。証明できるんですね」

僕「もちろん、何回か試行錯誤したんだけど、ああ、これはできそうもないなと思ったんだ。いくつか見せるね。たとえば（１）」

僕「（１）では、$A$と$1,2,3$とを結んで、$B$と$1,2,3$とを結んで、最後に$C$を結ぼうとしたんだけど、辺$C1$が結べなかった」

テトラ「はい」

僕「（２）では、最初に三つの辺$A1$と$B2$と$C3$を直線で結んでから始めたんだけど$A3$で失敗。最後の一本がどうしても描けないんだ」

テトラ「そうなんですよ！　もうちょっと！というところで失敗するんです」

テトラ「いろいろ試したんですね」

僕「でもね、（３）を描きながら、グラフが作れないことの証明ができることに気付いたんだ」

テトラ「といいますと」