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

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

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

参照用 記事

ラベル付き有向グラフが関手であること

ラベル付き有向グラフは関手とみなせます。

有向グラフの基本的概念

Gを有向グラフとします。Gには特に制限を設けず、多重辺もループ(同じ頂点に戻る有向辺)も許しましょう。Gの頂点の集合をNode(G)、辺の集合をEdge(G)とします。e∈Edge(G) に対して、辺eの始点(source)を src(e)、辺eの終点(target)を trg(e) と書くことにします。

A, Bはなんらかの集合だとして、写像 a:Node(G)→A を頂点ラベリング、b:Edge(G)→B を辺ラベリングと呼びます。有向グラフGと頂点ラベリングaを一緒にした構造 (G, a) を頂点ラベル付き有向グラフ、辺ラベリングbを付けた (G, b) を辺ラベル付き有向グラフと呼びます。もちろん、頂点にも辺にもラベルが付いた (G, a, b) もあります。

「ラベル」というと“文字列”のような印象がありますが、値の集合A, Bは何でもかまいません。数値でも複雑なデータ構造でもラベルの値に使えます。「ラベル」という言葉の代わりに、習慣や応用により「色」「重さ」「コスト」「属性」「流量」「電圧」などと呼ぶこともあります。

GとHが有向グラフとして、fnode:Node(G)→Node(H)、fedge:Edge(G)→Edge(H) の組 f = (fnode, fedge) が次の条件を満たすとき、fは有向グラフの準同型写像と呼びます。

  • 任意の e∈Edge(G) に対して、fnode(src(e)) = src(fedge(e)) かつ fnode(trg(e)) = src(ftrg(e)) 。

辺ラベリングから作る関手

b:Edge(G)→B を、有向グラフGの辺ラベリングとします。頂点ラベリングは定義されてない状況で、1 = {*} = (単元集合) として、a:Node(G)→1 という自明な写像を頂点ラベリングだとします。こうすると、Gには頂点ラベリングaと辺ラベリングbが付いていることになります。

ここで、辺ラベルの集合Bから有向グラフHを作ります。

  • Node(H) = 1 = {*} (頂点は1つだけ)
  • Edge(H) = B
  • e∈Edge(H) に対して、src(e) = *、trg(e) = * 。

a:Node(G)→1、b:Edge(G)→B は、a:Node(G)→Node(H)、b:Edge(G)→Edge(H) なので、(a, b) は有向グラフの準同型写像となります。準同型である条件を満たすことはほぼ自明でしょう(が要確認)。

有向グラフGとHから自由生成により自由圏((パスの圏)を作ると、グラフ準同型写像 (a, b) は、FreeCat(G)→FreeCat(H) という関手に持ち上がります。

有向グラフHには頂点が1つしかなかったので、FreeCat(H)はBから生成された自由モノイドになります。形式言語理論の言葉では、アルファベットBから生成された語(文、列)の連接モノイドです。Bでラベルされた有向グラフGは、オートマトンの表現とみなせるので、関手 FreeCat(G)→FreeCat(H) はオートマトンから形式言語(語の集合)を作るメカニズムを与えています。

頂点ラベリングから作る関手

今度は、頂点ラベリング a:Node(G)→A があって、辺ラベリングは定義されてない状況を考えましょう。ここでもまた、GもAも圏と考えたいのです。

単なる集合Aを圏と考える標準的な方法は離散圏を作ることです; 集合Aを圏の対象類とみて、射は恒等射だけとします。それとは別な方法として、余離散圏(codiscrete category)を作ることもできます。集合Aに対する余離散圏とは次のような圏Cです。以下では、A×Aの要素を [x, y](x, y∈A)のように書くことにします。

  1. Obj(C) = |C| = A
  2. Mor(C) = A×A
  3. dom([x, y]) = x、cod([x, y]) = y
  4. [x, y];[y, z] = [x, z]

別な言い方をすると、圏Cは、集合Aを頂点集合とする完全有向グラフを作って、射の結合を経路のバイバスで定義した圏です。集合Aに対する余離散圏を Codisc(A) と書くことにします。

頂点ラベリング a:Node(G)→A があると、e∈Edge(G) に対して b(e) = (src(e), trg(e)) と定義すると、b:Edge(G)→A×A となります。A×A は Codisc(A) の射の集合なので、a:Node(G)→|Codisc(A)|、b:Edge(G)→Mor(Codisc(A)) となります。ちょっと定義を付け足せば、FreeCat(G)→Codisc(A) という関手ができます。

つまり、頂点ラベリング a:Node(G)→A から出発しても、関手が構成できるわけです。

ラベル付き有向グラフは関手

頂点ラベリング a:Node(G)→A と、辺ラベリング b:Edge(G)→B があるときも、自由圏と余離散圏の手法を組み合わせると適切な圏Cが作れて、FreeCat(G)→C という関手が自然に構成できます。自由生成関手FreeCatと忘却関手Uとの随伴性から、FreeCat(G)→C は G→U(C) という有向グラフ準同型写像だと思っても同じことです。

ラベル付き有向グラフが関手なのだと分かれば、ラベル付き有向グラフによって表現される状態遷移系や回路図も関手だということになります。関手だからウレシイとは限りませんが、新しい視点を提供する可能性もあるでしょう。