よく知られた事実でも、圏論的に考えると少し面白い(かもしれない)という話。
グラフGとその頂点(ノード)rの組 (G, r) をルート付きグラフ(rooted graph)と呼びます。ここでは有向グラフだけを考えて、さらに次の条件を付けます。
- ルートrから任意の頂点xへの有向パスが存在する。
ツリーはルート付きグラフの特殊なもので、次の、もっと強い条件を付けます。
- ルートrから任意の頂点xへの有向パスがただ1つだけ存在する。
ツリーはサイクルを持てず、異なる辺が同一頂点に合流することもできません。結果的に、お馴染みのツリーの形状となります。
グラフの頂点や辺の個数は無限個でもいいとします。例えば、自然数 {0, 1, 2, ...} の隣り合う2個 n, n+1 を辺で結んだようなグラフ {0→1→2→ ...} も認めます。
Gを有向ラフとして、Node(G) をGの頂点(ノード)の集合、Edge(G) をGの辺の集合、辺eの始点ノードを src(e)、終点ノードを trg(e) としましょう。src, trg:Edge(G)→Node(G) です。
G = (G, r) と H = (H, s) をルート付き(有向)グラフとして、G→H というルート付きグラフの準同型写像を次のように定義します。
- fNode:Node(G)→Node(H) は写像である。
- fEdge:Edge(G)→Edge(H) は写像である。
- 任意の e∈Edge(G) に対して、fNode(src(e)) = src(fEdge(e))、fNode(trg(e)) = trg(fEdge(e)) 。
- fNode(r) = s
- このような組 f = (fNode, fEdge) をルート付きグラフの準同型写像とする。
ルート付きグラフと準同型写像の全体は圏となります。この圏をRootedGraphとします。ツリーとそのあいだの準同型写像の全体も圏となるので、Treeとします。もちろん、TreeはRootedGraphの部分圏(充満部分圏)です。
いま、ルート付きグラフ G = (G, r) が与えられたとして、ツリー T = (T, r) (ルートを同じ記号rで表しました)と準同型写像 f:T→G が次の条件を満たしている状況を考えましょう。
- Gのルートrから出る任意の有向パスpに対して、ツリーT上のパスqがあって、パスqの写像fによる像がpに一致する。
最初に与えられたG上のパスpが、ツリーT上のパスqの写像fによる“影”になっているということです。Tはツリーなので、条件を満たすパスは1本しかありません。
ツリーTがGの上に“広がっている”と考えると、G上のパスは、上に広がった世界であるTにあるパスの影として表現できます。また、G上に落ちた影から、その影の正体であるT上のパスを特定もできます。
与えられたルート付きグラフGに対して今説明したようなツリーTと準同型fは(同型の差を除いて)一意的に構成できます。さらに、G |→ T という対応は関手 Unfold:RootedGraph→Tree に拡張できます。
TreeをそのままRootedGraphに埋め込む関手を Incl:Tree→RootedGraph とすると、InclとUnfoldは随伴対 Incl -| Unfold となります。これは、Tree(T, Unfold(G)) と RootedGraph(Incl(T), G) が自然な同型となることですが、その同型はfの後結合(post-composition)で与えられます。
一般に、圏の充満部分圏が、自然な埋め込み関手の右随伴関手を持つとき余反映的部分圏(coreflective subcategory)と呼びます。Treeは、RootedGraphの余反映的部分圏だったわけです。