スポーツ、乗換案内、SNS～点と線で考えるグラフ理論の奥深さ～

スポーツスケジューリング

部活動の対外試合で、リーグ戦で優勝を競う大会があるとします。いくつかのグラウンドを使って総当たりで戦っていくとき、どういう順番で試合を組めばいいでしょうか。学校ごとに試合数が同じであるのは当然ですが、試合と試合との間隔もなるべく均等にならなければなりません。こうしたスケジュールを素早く正確に導き出す際に使われるのが「グラフ理論」です。グラフといっても棒グラフや関数のグラフではなく、「点」とそれらをつなぐ「線」からなる図形を用いて、その構造や性質などを抽象的に議論する学問です。スマートフォンの乗換案内アプリの経路計算も、このグラフ理論が用いられています。

巡回セールスマン問題

グラフ理論は数学の中でも少し特異な分野です。例えば、微分積分は微分を学んで積分に進みますが、グラフ理論にはその順番がありません。どこから手をつけていいかわからない難しさもありますが、同時に問題をどのように解くのかを自分で考えながら進められるのが醍醐（だいご）味です。
グラフ理論を有名にした問題に「巡回セールスマン問題」があります。あるセールスマンが複数の地点を一度ずつ訪問して自社に戻ってくる際、移動距離が最小になる経路を求めるという問題です。この問題に対する効率的なアルゴリズムはまだ見つかっておらず、現在も多くの数学者が挑戦しています。

ビッグデータの処理にも

人間同士のネットワークの解析にもグラフ理論がよく用いられます。現在、SNS利用者が世界で急増しています。既にFacebookだけで24億人(2019年)が利用しており、将来は100億人まで増えるとされています。SNSの仕組みを維持するためには、10の10乗もの人たちの複雑なつながり＝ビッグデータを高速に処理する必要がありますが、現在のコンピュータの能力では限界に近付いています。人を「点」に、つながりを「線」とした数式を通して、より複雑で多様なつながりを処理できるグラフ理論が、このSNSの危機を救う可能性があるのです。

※夢ナビ講義は各講師の見解にもとづく講義内容としてご理解ください。

※夢ナビ講義の内容に関するお問い合わせには対応しておりません。

先生情報 / 大学情報

熊本大学工学部機械数理工学科教授千葉周也先生

興味が湧いてきたら、この学問がオススメ！

離散数学、応用数学、情報科学、数理工学

先生が目指すSDGs

メッセージ

私の専門である数学に限らず、何かを研究している人は、ものごとを粘り強く考え抜き、ある時点に達したときに「これだ！」とひらめくことがあり、そうした瞬間には強い感動を覚えます。あなたも、何かに興味をもち「なぜだろう？」という疑問をみつけ、その答えを考え続けるという経験を大切にしてください。
なんにでも興味をもつということは難しいので、自分の得意科目や、好きなことからでも構いません。とにかく好奇心を抱き、疑問をもち、考え抜く力こそが、大学以降の学びには欠かせない要素なのです。

先生への質問

先生の学問へのきっかけは？
先輩たちはどんな仕事に携わっているの？

熊本大学に関心を持ったあなたは

熊本大学は、「総合大学として、知の創造、継承、発展に努め、知的、道徳的、及び応用的能力を備えた人材を育成することにより、地域と国際社会に貢献する」という理念に基づき、地域のリーダーとしての役目を果たしています。かつ、世界に向け様々な情報を発信しながら、世界の学術研究拠点、グローバルなアカデミックハブとして、その存在感を高める努力をし、教育においては、累計30件にも及ぶ「特色ある教育プログラム」が優れた取り組みとして文部科学省から認定され、その教育力の高さと質の高い教育内容は定評のあるところです。