最近話題になったこの記事。 qiita.com この記事は主に次の事実を扱ったものです。 有向グラフの辺の重みを並べた行列のトロピカルな 乗の第 -成分は, 番目の頂点から 番目の頂点への道のうち,最小の重みを持つものの重みに等しいという話です。 ここで,トロピカル演算は次のように定義されるものです。 トロピカル加法 トロピカル乗法 トロピカル加法の単位元 この話を聞いて,似た話を知っていると思った人もいたのではないでしょうか。それは次の定理です。 有向グラフの隣接行列の 乗の第 -成分は, 番目の頂点から 番目の頂点への道の数に等しい。 辺の重みを並べた行列は,隣接行列に見た目がよく似ています。 この2つの似た事実は成り立つ理由もよく似ていますが,隣接行列をうまく一般化するとこの2つの事実を同時に示すことができるというのが今日のお話です。この話を通して,トロピカル演算の正体が見えてきます