このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

グラフとツリーと余反映的部分圏

よく知られた事実でも、圏論的に考えると少し面白い(かもしれない)という話。


グラフ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 というルート付きグラフの準同型写像を次のように定義します。

  1. fNode:Node(G)→Node(H) は写像である。
  2. fEdge:Edge(G)→Edge(H) は写像である。
  3. 任意の e∈Edge(G) に対して、fNode(src(e)) = src(fEdge(e))、fNode(trg(e)) = trg(fEdge(e)) 。
  4. fNode(r) = s
  5. このような組 f = (fNode, fEdge) をルート付きグラフの準同型写像とする。

ルート付きグラフと準同型写像の全体は圏となります。この圏をRootedGraphとします。ツリーとそのあいだの準同型写像の全体も圏となるので、Treeとします。もちろん、TreeRootedGraphの部分圏(充満部分圏)です。

いま、ルート付きグラフ 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:RootedGraphTree に拡張できます。


TreeをそのままRootedGraphに埋め込む関手を Incl:TreeRootedGraph とすると、InclとUnfoldは随伴対 Incl -| Unfold となります。これは、Tree(T, Unfold(G)) と RootedGraph(Incl(T), G) が自然な同型となることですが、その同型はfの後結合(post-composition)で与えられます。

一般に、圏の充満部分圏が、自然な埋め込み関手の右随伴関手を持つとき余反映的部分圏coreflective subcategory)と呼びます。Treeは、RootedGraphの余反映的部分圏だったわけです。