お久しぶりです。D2の星です。

突然ですが、「グラフ理論」というものをご存じでしょうか。

グラフといえば、例えば座標平面における曲線などをイメージするかと思いますが、ここで言うグラフは少し違います。

簡単に言うと、”ある物を「頂点」、物どうしの繋がりを「辺」で表した図形” ですが、いまいちピンと来ないかもしれません。

以下の図は、頂点が5個、辺が6個の簡単なグラフです。辺が矢印になっているということは向きがあり、これを「有向辺」と言います。そして、有向辺で構成されているグラフのことを「有向グラフ」と呼びます。

よく挙げられる具体例としては、例えば電車の路線図もグラフです。駅が頂点、路線が辺というわけです。

一般には同じ路線で駅間を行ったり来たりできますので、どちらにでも行ける「無向辺」ですね。路線図自体は「無向グラフ」となります。

しかし、これと化学にどんな関係があるのでしょうか。勘の良い読者はお気づきかもしれません。

すなわち、化学物質を頂点、化学反応を(有向)辺とすれば、化学変換をグラフ理論に落とし込めるということです。

特に有機化学の分野ではあまり浸透していない気がしますが、このような考え方を「化学反応ネットワーク理論」と呼ぶようです。

少し前の話ですが、実はこの考え方、卒業生の楢山くんがFPで紹介してくれました。彼は路線図などもかなり好きだったようですので、そこからグラフ理論にも興味を持ったのかもしれません。当時はグラフ理論については概念くらいしか知りませんでしたが、化学と繋がることに感銘を受けました。しかし、そういう見方もできるかもね、程度で終わってしまっては非常にもったいないと感じたので、もう少し深掘りしていきます。

このシリーズでは、有機化学をグラフ理論と繋げることでどんな良いことがあるのか？あるいはどんな可能性が見えてくるのか？について、グラフ理論でよく用いられている考え方(アルゴリズム)を紹介しながら追っていこうと思っています。

長くなってしまうので今回はグラフ理論の紹介にとどめますが、今後「この化合物を最短で何工程で合成できるのか？」「この出発原料からこの化合物を合成できる経路は何通りあるのか？」などの問題を考えます。たとえ膨大な種類の化合物や反応があったとしても、コンピュータが処理しやすいような形に落とし込み、瞬時に答えを導く鮮やかなアルゴリズムたちを解説していきます。

それでは今回はこの辺で。

The following two tabs change content below.

• この記事を書いた人
• 最新の記事

星貴之

D3 ： 早稲田大学山口研究室

D3。ボードゲームやプログラミングなど、頭を使うことが好き。

最新記事 by 星貴之 (全て見る)

• 有機化学×グラフ理論(3) - 2022年8月3日
• 有機化学×グラフ理論(2) - 2021年9月30日
• 有機化学×グラフ理論(1) - 2021年7月12日