最短距離と自由豊穣圏 - 論理とか計算機とか数学とか

距離空間は豊穣圏であるという Lawvere の論文(http://www.tac.mta.ca/tac/reprints/articles/1/tr1abs.html)がありますが，それに似た感じで重みつきグラフから自由に生成された豊穣圏を考えると hom-object が最短経路になるらしいことに気付いて面白いと思ったので書いてみます．（よく見たら Lawvere の論文にも書いてありましたが，まあいいでしょう．）

R の monoidal structure

R は非負実数の集合に∞を追加した集合とする．これに普通と逆の順序を入れて圏とみなす．実数の普通の足し算はこの圏でのモノイド積になる（0が単位元）．また，この圏における直和は inf で与えられる．特に始対象は∞である．モノイド積はすべての直和に対して分配律を満たす．

V-graph と重みつきグラフ

V を可算直和をもつモノイド圏で，分配律 $A \otimes \coprod_i B_i \simeq \coprod_i (A \otimes B_i)$ と $\left(\coprod_i A_i\right) \otimes B \simeq \coprod_i (A_i \otimes B)$ が成り立つものとする（Lawvere の論文には詳しい条件が書かれていないけど，後でこれくらい必要になる気がするので最初から仮定しておく）．

V-グラフ $\mathcal A$ は，集合 $\mathcal A_0$ と，各 $u, v \in \mathcal A_0$ に対する対象の割り当て $\mathcal A(u, v) \in V$ からなる．

特に V = R のときを考えると，V-グラフとは非負の重みつき単純有向グラフのことである．逆に非負の重みつき単純有向グラフ G が与えられたとき，辺がないところには重み ∞ の辺があると考えることで G を R-グラフとみなせる．

free V-category と最短距離

V-グラフ $\mathcal A$ に対して，V-category $\widetilde{\mathcal A}$ を対象が $\mathcal A_0$ の要素全体で，hom-objectが $\widetilde{\mathcal A}(u, v) = \coprod_{n \ge 0} \mathcal A^n(u, v)$ となるようなものとする（0は始対象，1はモノイド積の単位元）．ただし
$\mathcal A^0(u, v) = \begin{cases} 0 & u \ne v \\ 1 & u = v, \end{cases} \quad \mathcal A^{n+1}(u, v) = \coprod_{w \in \mathcal A_0} (\mathcal A^n(w, v)\otimes \mathcal A(u, w))$
とする．これは V-category になる（たぶん）．Lawvere によると，この構成は V-Cat から V-graph への忘却関手の左随伴になっているそうだ（いかにもなってそうである）．

重みつきグラフ G を R グラフとみなして上記の構成を行うと， $\widetilde G(u, v)$ は u から v への最短距離になる（ $\otimes$ が足し算で $\coprod$ がinfであることを思い出せばわかる）．