コンピュータから人との繋がりまで、グラフ理論で探索
Q:千葉先生の研究内容を教えてください。
『グラフ理論』を研究しています。これは図形の構造や性質などを抽象的に議論する数学です。コンピュータネットワークを例にとって説明しましょう。各端末やスイッチを“点”、それらをつなぐケーブルを“辺”と考えると、ネットワーク構造をグラフで表現できるんです。表現できるということは、ネットワーク構造の問題をグラフ理論で考察・解析できるということ。また、鉄道路線図や交通網もわかりやすい例ですね。各駅が“点”だとすると線路は“辺”。都市が“点”で道路が“辺”。グラフ理論を用いて鉄道路線や交通網の探索を求めることができるんです。
それ以外にも関係性、例えば人との関係性もグラフ理論を用いることができます。人自体を“点”、知り合い同士が“辺”と考えると、その関係性をグラフで表現できる。人と人とのマッチングなどをグラフ理論で見つけることができるんです。
グラフ理論には、グラフの構造や性質を明らかにしたいという数学的な興味と、グラフで表現される事象や現象の解析を行いたいという工学的な必要性のふたつがあります。学問としての歴史は浅いかもしれませんが、時代の変化とともに研究が発展している分野です。
世界をスムーズにストレスフリーにするための議論を
Q:グラフ理論を用いることで解決できることは？
効率化・最適化でしょうか。経路探索で言うと、もっとも移動時間が短いものはどれかというのがグラフの構造を解析することでわかります。例えば私は“グラフの詰込み・分割問題” “巡回セールスマン問題” “ハミルトン閉路問題”の理論的研究を中心に行なっています。それらを考察し解決することで、レイアウト設計への応用に繋がりますし、経路探索の効率化・最適化がより進みます。また、スケジューリング作成にも用いることができるんです。
Q：それらの問題を考察することで、どのようなことが起こるのでしょうか。
グラフの詰込み・分割問題についてですが、まず好きな構造をひとつ決めるとします。次に、与えられた別のグラフにそれと同じものが部分的にあるかを探す。ただしひとつだけ見つけるのではなく、なるべくたくさん見つけていきます。つまり、ある構造をある構造の中から見つける問題なのですが、この問題をうまく言い換えることでスケジュールの組み方にも応用できるんです。
例えば、スポーツ。プレイヤーがいて、いくつかコートがあり、そのコートを使って各プレイヤーが総当たりの試合をしますよね。その試合順を考えたときに、ある人は等間隔で試合をしているのに、ある人は連続して試合をすることになると、体力的にも不平等です。なるべくみんなが均等間隔で休めるようなスケジュールをグラフの詰込み・分割問題を用いて導くことができます。
巡回セールスマン問題は、経路問題の解決を導くために用いられます。ある地点からある地点までの移動コスト最小のコースを見つけるとします。そのなかでも特に、途中の地点をすべて経由するコースを探す……となるとかなり難しいんですよ。ハミルトン閉路問題はそれの特殊ケースで「全部を通ってスタート地点に戻ってくる」というもの。問題を制限しているけれども、全部を通りながら一番いいものを探すというのは非常に大変です。現実的な時間で探索できるアルゴリズムが見つかっていないというのが現状なので、これはまだ研究の途中段階なんですよ。近似的なアルゴリズムで「まあ、これでいいだろう」という経路を妥協して探すことはもちろんできます。しかし、我々はより的確に効率的なものをグラフ理論を用いて提供していく。それが課題となっています。
Q：ハードからソフトまで、わたしたちの生活に密着した分野なのですね。
そうですね。最近は、ビッグデータの処理の研究も考えています。SNSは現在10億人の人が使用していると言われ、そのデータを一気に処理しなくてはいけないという課題があるのです。近い将来は現在の10倍のデータ量になると予想されています。それをどう処理するかが問題になっているんです。現在、その問題をグラフ理論的に解析しようという研究が活発化しています。私の研究もそういうことに役に立つのではないのかと思っています。時代の発展とともに、グラフ理論も新しいものを常に見つけていかないといけないので、そこが大変ですね。
ひとつの命題から、まったく別の命題の解決になることも。それがグラフ理論の魅力！
Q：グラフ理論の面白さとは？
実は私は学部の卒業研究からグラフ理論を初めて学んだんですよ。そこで興味を持ちました。グラフ理論には「言い換えの面白さ」があるんです。ある定理があってそれを言い換えることによって、見かけ上全く関係のない定理や問題に繋がることがある。グラフの詰込み・分割問題からスケジューリング問題へというのがひとつの例ですよね。グラフ理論はある命題だけにとどまらずに、言い換えを考えることで別のことに利用できる。それを発見する楽しさがあります。数学的なアプローチで解いてそれで終わりではなくて、アプローチして解決する上で、その先にある新しい何かを発見するところが一番面白いですね。あらゆるものがヒントになり、スッと解決できるところが面白くもあるし、難しいところでもあります。
Q：最後に学生さんにメッセージをお願いします。
物事をじっくり考えることを厭わないようにしてください。数学は、じっくり考えることでそこから生まれる展開があることが面白いと思うのです。考えても出ないかもしれない、けれど考えないと出ないもの。最近は社会全体においても、すぐ答えを求めがちな傾向にありますよね。でもじっくり考えて、そこから生まれる新しいものを大事にしてほしいと思います。