モノイドと有向グラフから圏を構成する - 檜山正幸のキマイラ飼育記 (はてなBlog)事情があって、モノイドと有向グラフから圏を構成する方法を考えたので書いておきます。 自由圏（道の圏、パスの圏） Gが有向グラフのとき、Gから作られる自由圏（free category）はよく知られています。復習しておきます。記号法は圏論のものを用います； |G|, dom, cod はそれぞれ、グラフの頂点集合、辺の始点、辺の終点です。 A0, A1, ... , An が頂点の列、f1, ... , fn が辺の列で、次の条件を満たすとします。 dom(fi) = Ai-1 cod(fi) = Ai このとき、[A0, f1, A1, ... , An-1, fn, An] を、G上の長さnの道と呼びます。n = 0, 1 のときは次のような形です。 [A, A] （Aは頂点） [A, f, B] （dom(f) = A, cod(f) = B） 道に対しても dom, cod を定義し
