Blog

有機化学×グラフ理論(1)

2021.07.12

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

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

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

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

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

: 簡単な有向グラフの例

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

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

: JR東日本路線図より

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

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

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

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

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

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

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